An edition of Computer algorithms (1997)

Computer algorithms

by

  • 2 Want to read
Cover of: Computer algorithms by Ellis Horowitz, Ellis Horowitz
Preview
Borrow

My Reading Lists:

Create a new list
Notes
  • 2 Want to read
Notes

Check nearby libraries

Buy this book

Last edited by Drini
September 14, 2025 | History
Edit
An edition of Computer algorithms (1997)

Computer algorithms

by

  • 2 Want to read

This work doesn't have a description yet. Can you add one?

Publish Date
Publisher
Computer Science Press
Language
English
Pages
769

Check nearby libraries

Buy this book

Previews available in: English

Subjects

Computer algorithms, Pseudocode (Computer program language)
Edition Availability
Cover of: Computer algorithms
Computer algorithms
2008, Silicon Press
in English - 2nd ed.
Cover of: Computer algorithms
Computer algorithms
2008, Silicon Press
in English - 2nd ed.
Cover of: Computer algorithms
Computer algorithms
1998, Computer Science Press
in English
Cover of: Computer algorithms
Computer algorithms
1997, Computer Science Press
in English - [pseudocode version].

Add another edition?

Book Details

Table of Contents

Preface
Page XV
1. Introduction
Page 1
1.1. What Is an Algorithm?
Page 1
1.2. Algorithm Specification
Page 5
1.2.1. Pseudocode Conventions
Page 5
1.2.2. Recursive Algorithms
Page 10
1.3. Performance Analysis
Page 14
1.3.1. Space Complexity
Page 15
1.3.2. Time Complexity
Page 18
1.3.3. Asymptotic Notation (O, Ω, Θ)
Page 29
1.3.4. Practical Complexities
Page 37
1.3.5. Performance Measurement
Page 40
1.4. Randomized Algorithms
Page 53
1.4.1. Basics of Probability Theory
Page 53
1.4.2. Randomized Algorithms: An Informal Description
Page 57
1.4.3. Identifying the Repeated Element
Page 59
1.4.4. Primality Testing
Page 61
1.4.5. Advantages and Disadvantages
Page 65
1.5. References and Readings
Page 68
2. Elementary Data Structures
Page 69
2.1. Stacks and Queues
Page 69
2.2. Trees
Page 76
2.2.1. Terminology
Page 77
2.2.2. Binary Trees
Page 78
2.3. Dictionaries
Page 81
2.3.1. Binary Search Trees
Page 83
2.3.2. Cost Amortization
Page 89
2.4. Priority Queues
Page 91
2.4.1. Heaps
Page 92
2.4.2. Heapsort
Page 99
2.5. Sets and Disjoint Set Union
Page 101
2.5.1. Introduction
Page 101
2.5.2. Union and Find Operations
Page 102
2.6. Graphs
Page 112
2.6.1. Introduction
Page 112
2.6.2. Definitions
Page 112
2.6.3. Graph Representations
Page 118
2.7. References and Readings
Page 126
3. Divide-and-Conquer
Page 127
3.1. General Method
Page 127
3.2. Binary Search
Page 131
3.3. Finding the Maximum and Minimum
Page 139
3.4. Merge Sort
Page 145
3.5. Quicksort
Page 154
3.5.1. Performance Measurement
Page 159
3.5.2. Randomized Sorting Algorithms
Page 159
3.6. Selection
Page 165
3.6.1. A Worst-Case Optimal Algorithm
Page 169
3.6.2. Implementation of Select2
Page 172
3.7. Strassen's Matrix Multiplication
Page 179
3.8. Convex Hull
Page 183
3.8.1. Some Geometric Primitives
Page 184
3.8.2. The QuickHull Algorithm
Page 185
3.8.3. Graham's Scan
Page 187
3.8.4. An O(n log n) Divide-and-Conquer Algorithm
Page 188
3.9. References and Readings
Page 193
3.10. Additional Exercises
Page 194
4. The Greedy Method
Page 197
4.1. The General Method
Page 197
4.2. Knapsack Problem
Page 198
4.3. Tree Vertex Splitting
Page 203
4.4. Job Sequencing with Deadlines
Page 208
4.5. Minimum-Cost Spanning Trees
Page 216
4.5.1. Prim's Algorithm
Page 218
4.5.2. Kruskal's Algorithm
Page 220
4.5.3. An Optimal Randomized Algorithm (*)
Page 225
4.6. Optimal Storage on Tapes
Page 229
4.7. Optimal Merge Patterns
Page 234
4.8. Single-Source Shortest Paths
Page 241
4.9. References and Readings
Page 249
4.10. Additional Exercises
Page 250
5. Dynamic Programming
Page 253
5.1. The General Method
Page 253
5.2. Multistage Graphs
Page 257
5.3. All Pairs Shortest Paths
Page 265
5.4. Single-Source Shortest Paths: General Weights
Page 270
5.5. Optimal Binary Search Trees (*)
Page 275
5.6. String Editing
Page 284
5.7. 0/1-Knapsack
Page 287
5.8. Reliability Design
Page 295
5.9. The Traveling Salesperson Problem
Page 298
5.10. Flow Shop Scheduling
Page 301
5.11. References and Readings
Page 307
5.12. Additional Exercises
Page 308
6. Basic Traversal and Search Techniques
Page 313
6.1. Techniques for Binary Trees
Page 313
6.2. Techniques for Graphs
Page 318
6.2.1. Breadth First Search and Traversal
Page 320
6.2.2. Depth First Search and Traversal
Page 323
6.3. Connected Components and Spanning Trees
Page 325
6.4. Biconnected Components and DFS
Page 329
6.5. References and Readings
Page 338
7. Backtracking
Page 339
7.1. The General Method
Page 339
7.2. The 8-Queens Problem
Page 353
7.3. Sum of Subsets
Page 357
7.4. Graph Coloring
Page 360
7.5. Hamiltonian Cycles
Page 364
7.6. Knapsack Problem
Page 368
7.7. References and Readings
Page 374
7.8. Additional Exercises
Page 375
8. Branch-and-Bound
Page 379
8.1. The Method
Page 379
8.1.1. Least Cost (LC) Search
Page 380
8.1.2. The 15-Puzzle: An Example
Page 382
8.1.3. Control Abstractions for LC-Search
Page 386
8.1.4. Bounding
Page 388
8.1.5. FIFO Branch-and-Bound
Page 391
8.1.6. LC Branch-and-Bound
Page 392
8.2. 0/1 Knapsack Problem
Page 393
8.2.1. LC Branch-and-Bound Solution
Page 394
8.2.2. FIFO Branch-and-Bound Solution
Page 397
8.3. Traveling Salesperson (*)
Page 403
8.4. Efficiency Considerations
Page 412
8.5. References and Readings
Page 416
9. Algebraic Problems
Page 417
9.1. The General Method
Page 417
9.2. Evaluation and Interpolation
Page 420
9.3. The Fast Fourier Transform
Page 430
9.3.1. An In-Place Version of the FFT
Page 435
9.3.2. Some Remaining Points
Page 438
9.4. Modular Arithmetic
Page 440
9.5. Even Faster Evaluation and Interpolation
Page 448
9.6. References and Readings
Page 456
10. Lower Bound Theory
Page 457
10.1. Comparison Trees
Page 458
10.1.1. Ordered Searching
Page 459
10.1.2. Sorting
Page 459
10.1.3. Selection
Page 464
10.2. Oracles and Adversary Arguments
Page 466
10.2.1. Merging
Page 467
10.2.2. Largest and Second Largest
Page 468
10.2.3. State Space Method
Page 470
10.2.4. Selection
Page 471
10.3. Lower Bounds Through Reductions
Page 474
10.3.1. Finding the Convex Hull
Page 475
10.3.2. Disjoint Sets Problem
Page 475
10.3.3. On-line Median Finding
Page 477
10.3.4. Multiplying Triangular Matrices
Page 477
10.3.5. Inverting a Lower Triangular Matrix
Page 478
10.3.6. Computing the Transitive Closure
Page 480
10.4. Techniques for Algebraic Problems (*)
Page 484
10.5. References and Readings
Page 494
11. NP-Hard and NP-Complete Problems
Page 495
11.1. Basic Concepts
Page 495
11.1.1. Nondeterministic Algorithms
Page 496
11.1.2. The Classes NP-Hard and NP-Complete
Page 504
11.2. Cook's Theorem (*)
Page 508
11.3. NP-Hard Graph Problems
Page 517
11.3.1. Clique Decision Problem (CDP)
Page 518
11.3.2. Node Cover Decision Problem
Page 519
11.3.3. Chromatic Number Decision Problem (CNDP)
Page 521
11.3.4. Directed Hamiltonian Cycle (DHC) (*)
Page 522
11.3.5. Traveling Salesperson Decision Problem (TSP)
Page 525
11.3.6. AND/OR Graph Decision Problem (AOG)
Page 526
11.4. NP-Hard Scheduling Problems
Page 533
11.4.1. Scheduling Identical Processors
Page 534
11.4.2. Flow Shop Scheduling
Page 536
11.4.3. Job Shop Scheduling
Page 538
11.5. NP-Hard Code Generation Problems
Page 540
11.5.1. Code Generation With Common Subexpressions
Page 542
11.5.2. Implementing Parallel Assignment Instructions
Page 546
11.6. Some Simplified NP-Hard Problems
Page 550
11.7. References and Readings
Page 553
11.8. Additional Exercises
Page 553
12. Approximation Algorithms
Page 557
12.1. Introduction
Page 557
12.2. Absolute Approximations
Page 561
12.2.1. Planar Graph Coloring
Page 561
12.2.2. Maximum Programs Stored Problem
Page 562
12.2.3. NP-Hard Absolute Approximations
Page 563
12.3. ε-Approximations
Page 566
12.3.1. Scheduling Independent Tasks
Page 566
12.3.2. Bin Packing
Page 569
12.3.3. NP-Hard ε-Approximation Problems
Page 572
12.4. Polynomial Time Approximation Schemes
Page 579
12.4.1. Scheduling Independent Tasks
Page 579
12.4.2. 0/1 Knapsack
Page 580
12.5. Fully Polynomial Time Approximation Schemes
Page 585
12.5.1. Rounding
Page 587
12.5.2. Interval Partitioning
Page 591
12.5.3. Separation
Page 592
12.6. Probabilistically Good Algorithms (*)
Page 596
12.7. References and Readings
Page 599
12.8. Additional Exercises
Page 600
13. PRAM Algorithms
Page 605
13.1. Introduction
Page 605
13.2. Computational Model
Page 608
13.3. Fundamental Techniques and Algorithms
Page 615
13.3.1. Prefix Computation
Page 615
13.3.2. List Ranking
Page 618
13.4. Selection
Page 627
13.4.1. Maximal Selection With n^2 Processors
Page 627
13.4.2. Finding the Maximum Using n Processors
Page 628
13.4.3. Maximal Selection Among Integers
Page 629
13.4.4. General Selection Using n^2 Processors
Page 632
13.4.5. A Work-Optimal Randomized Algorithm (*)
Page 632
13.5. Merging
Page 636
13.5.1. A Logarithmic Time Algorithm
Page 636
13.5.2. Odd-Even Merge
Page 637
13.5.3. A Work-Optimal Algorithm
Page 640
13.5.4. An O(log log m)-Time Algorithm
Page 641
13.6. Sorting
Page 643
13.6.1. Odd-Even Merge Sort
Page 643
13.6.2. An Alternative Randomized Algorithm
Page 644
13.6.3. Preparata's Algorithm
Page 645
13.6.4. Reischuk's Randomized Algorithm (*)
Page 647
13.7. Graph Problems
Page 651
13.7.1. An Alternative Algorithm for Transitive Closure
Page 654
13.7.2. All-Pairs Shortest Paths
Page 655
13.8. Computing the Convex Hull
Page 656
13.9. Lower Bounds
Page 659
13.9.1. A Lower Bound on Average Case Sorting
Page 660
13.9.2. Finding the Maximum
Page 662
13.10. References and Readings
Page 663
13.11. Additional Exercises
Page 665
14. Mesh Algorithms
Page 667
14.1. Computational Model
Page 667
14.2. Packet Routing
Page 669
14.2.1. Packet Routing on a Linear Array
Page 670
14.2.2. A Greedy Algorithm for PPR on a Mesh
Page 674
14.2.3. A Randomized Algorithm With Small Queues
Page 676
14.3. Fundamental Algorithms
Page 679
14.3.1. Broadcasting
Page 681
14.3.2. Prefix Computation
Page 681
14.3.3. Data Concentration
Page 685
14.3.4. Sparse Enumeration Sort
Page 686
14.4. Selection
Page 691
14.4.1. A Randomized Algorithm for n = p (*)
Page 691
14.4.2. Randomized Selection For n > p (*)
Page 692
14.4.3. A Deterministic Algorithm For n > p
Page 692
14.5. Merging
Page 698
14.5.1. Rank Merge on a Linear Array
Page 698
14.5.2. Odd-Even Merge on a Linear Array
Page 699
14.5.3. Odd-Even Merge on a Mesh
Page 699
14.6. Sorting
Page 701
14.6.1. Sorting on a Linear Array
Page 701
14.6.2. Sorting on a Mesh
Page 703
14.7. Graph Problems
Page 708
14.7.1. An n x n Mesh Algorithm for Transitive Closure
Page 710
14.7.2. All Pairs Shortest Paths
Page 711
14.8. Computing the Convex Hull
Page 713
14.9. References and Readings
Page 718
14.10. Additional Exercises
Page 719
15. Hypercube Algorithms
Page 723
15.1. Computational Model
Page 723
15.1.1. The Hypercube
Page 723
15.1.2. The Butterfly Network
Page 726
15.1.3. Embedding of Other Networks
Page 727
15.2. PPR Routing
Page 732
15.2.1. A Greedy Algorithm
Page 732
15.2.2. A Randomized Algorithm
Page 733
15.3. Fundamental Algorithms
Page 736
15.3.1. Broadcasting
Page 737
15.3.2. Prefix Computation
Page 737
15.3.3. Data Concentration
Page 739
15.3.4. Sparse Enumeration Sort
Page 742
15.4. Selection
Page 744
15.4.1. A Randomized Algorithm for n = p (*)
Page 744
15.4.2. Randomized Selection For n > p (*)
Page 745
15.4.3. A Deterministic Algorithm For n > p
Page 745
15.5. Merging
Page 748
15.5.1. Odd-Even Merge
Page 748
15.5.2. Bitonic Merge
Page 750
15.6. Sorting
Page 752
15.6.1. Odd-Even Merge Sort
Page 752
15.6.2. Bitonic Sort
Page 752
15.7. Graph Problems
Page 753
15.8. Computing the Convex Hull
Page 755
15.9. References and Readings
Page 757
15.10. Additional Exercises
Page 758
Index
Page 761

Edition Notes

Includes bibliographical references and index.

Published in
New York

Classifications

Dewey Decimal Class
005.1
Library of Congress
QA76.9.A43 H67 1998, QA76.9.A43H67 1998

The Physical Object

Pagination
xxii, 769 p. :
Number of pages
769

Edition Identifiers

Open Library
OL674171M
Internet Archive
computeralgorith0000horo
ISBN 10
0716783169
LCCN
97020318
LibraryThing
3520612
Goodreads
1686084

Work Identifiers

Work ID
OL2676160W

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Loading indicator
Loading carousel
Loading indicator
Loading carousel

History

Download catalog record: RDF / JSON
September 14, 2025 Edited by Drini Edited without comment.
April 28, 2010 Edited by Open Library Bot Linked existing covers to the work.
February 6, 2010 Edited by WorkBot add more information to works
December 10, 2009 Created by WorkBot add works page