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