Computer algorithms : introduction to design and analysis
Baase, Sara
Computer algorithms : introduction to design and analysis - 3rd ed. - New Delhi. : Pearson Education, c2000. - xix, 688 pages : illustrations ;
Includes Index
1 .1 Analyzing Algorithms and Problems: Principles and Examples
1.2 Java as an Algorithm Language 3 --
1.3 Mathematical Background 11 --
1.4 Analyzing Algorithms and Problems 30 --
1.5 Classifying Functions by Their Asymptotic Growth Rates 43 --
1.6 Searching an Ordered Array 53 --
2 Data Abstraction and Basic Data Structures 69 --
2.2 ADT Specification and Design Techniques 71 --
2.3 Elementary ADTs--Lists and Trees 73 --
2.4 Stacks and Queues 86 --
2.5 ADTs for Dynamic Sets 89 --
3 Recursion and Induction 101 --
3.2 Recursive Procedures 102 --
3.3 What Is a Proof? 108 --
3.4 Induction Proofs 111 --
3.5 Proving Correctness of Procedures 118 --
3.6 Recurrence Equations 130 --
3.7 Recursion Trees 134 --
4 Sorting 149 --
4.2 Insertion Sort 151 --
4.3 Divide and Conquer 157 --
4.4 Quicksort 159 --
4.5 Merging Sorted Sequences 171 --
4.6 Mergesort 174 --
4.7 Lower Bounds for Sorting by Comparison of Keys 178 --
4.8 Heapsort 182 --
4.9 Comparison of Four Sorting Algorithms 197 --
4.10 Shellsort 197 --
4.11 Radix Sorting 201 --
5 Selection and Adversary Arguments 223 --
5.2 Finding max and min 226 --
5.3 Finding the Second-Largest Key 229 --
5.4 Selection Problem 233 --
5.5 A Lower Bound for Finding the Median 238 --
5.6 Designing Against an Adversary 240 --
6 Dynamic Sets and Searching 249 --
6.2 Array Doubling 250 --
6.3 Amortized Time Analysis 251 --
6.4 Red-Black Trees 253 --
6.5 Hashing 275 --
6.6 Dynamic Equivalence Relations and Union-Find Programs 283 --
6.7 Priority Queues with a Decrease Key Operation 295 --
Programs 309 --
7 Graphs and Graph Traversals 313 --
7.2 Definitions and Representations 314 --
7.3 Traversing Graphs 328 --
7.4 Depth-First Search on Directed Graphs 336 --
7.5 Strongly Connected Components of a Directed Graph 357 --
7.6 Depth-First Search on Undirected Graphs 364 --
7.7 Biconnected Components of an Undirected Graph 366 --
8 Graph Optimization Problems and Greedy Algorithms 387 --
8.2 Prim's Minimum Spanning Tree Algorithm 388 --
8.3 Single-Source Shortest Paths 403 --
8.4 Kruskal's Minimum Spanning Tree Algorithm 412 --
9 Transitive Closure, All-Pairs Shortest Paths 425 --
9.2 Transitive Closure of a Binary Relation 426 --
9.3 Warshall's Algorithm for Transitive Closure 430 --
9.4 All-Pairs Shortest Paths in Graphs 433 --
9.5 Computing Transitive Closure by Matrix Operations 436 --
9.6 Multiplying Bit Matrices--Kronrod's Algorithm 439 --
10 Dynamic Programming 451 --
10.2 Subproblem Graphs and Their Traversal 453 --
10.3 Multiplying a Sequence of Matrices 457 --
10.4 Constructing Optimal Binary Search Trees 466 --
10.5 Separating Sequences of Words into Lines 471 --
10.6 Developing a Dynamic Programming Algorithm 474 --
11 String Matching 483 --
11.2 A Straightforward Solution 485 --
11.3 Knuth-Morris-Pratt Algorithm 487 --
11.4 Boyer-Moore Algorithm 495 --
11.5 Approximate String Matching 504 --
12 Polynomials and Matrices 515 --
12.2 Evaluating Polynomial Functions 516 --
12.3 Vector and Matrix Multiplication 522 --
12.4 Fast Fourier Transform and Convolution 528 --
13 NP-Complete Problems 547 --
13.2 P and NP 548 --
13.3 NP-Complete Problems 559 --
13.4 Approximation Algorithms 570 --
13.5 Bin Packing 572 --
13.6 Knapsack and Subset Sum Problems 577 --
13.7 Graph Coloring 581 --
13.8 Traveling Salesperson Problem 589 --
13.9 Computing with DNA 592 --
14 Parallel Algorithms 611 --
14.2 Parallelism, the PRAM, and Other Models 612 --
14.3 Some Simple PRAM Algorithms 616 --
14.4 Handling Write Conflicts 622 --
14.5 Merging and Sorting 624 --
14.6 Finding Connected Components 628 --
14.7 A Lower Bound for Adding n Integers 641 --
A Java Examples and Techniques 649 --
A.2 A Java Main Program 651 --
A.3 A Simple Input Library 656 --
A.4 Documenting Java Classes 658 --
A.5 Generic Order and the "Comparable" Interface 659 --
A.6 Subclasses Extend the Capability of Their Superclass 663 --
A.7 Copy via the "Cloneable" Interface 667.
"This edition features an increased emphasis on algorithm design techniques such as divide-and-conquer and greedy algorithms, along with the addition of new topics and exercises. It continues the tradition of solid mathematical analysis and clear writing style: emphasizes the development of algorithms through a step-by-step process rather than by merely presenting the end result; stresses the importance of the algorithm analysis process - continuously re-evaluating, modifying, and perhaps rejecting algorithms until a satisfactory solution is attained; provides extensive treatment of recursion with a clear, student-friendly review of how it works and why it is a valuable programming technique; uses a Java-like pseudocode; and includes an appendix with java examples."
9788178081717 8178081717
Computer algorithms.
Computer programming.
Algorithms.
005.1 / BAA
Computer algorithms : introduction to design and analysis - 3rd ed. - New Delhi. : Pearson Education, c2000. - xix, 688 pages : illustrations ;
Includes Index
1 .1 Analyzing Algorithms and Problems: Principles and Examples
1.2 Java as an Algorithm Language 3 --
1.3 Mathematical Background 11 --
1.4 Analyzing Algorithms and Problems 30 --
1.5 Classifying Functions by Their Asymptotic Growth Rates 43 --
1.6 Searching an Ordered Array 53 --
2 Data Abstraction and Basic Data Structures 69 --
2.2 ADT Specification and Design Techniques 71 --
2.3 Elementary ADTs--Lists and Trees 73 --
2.4 Stacks and Queues 86 --
2.5 ADTs for Dynamic Sets 89 --
3 Recursion and Induction 101 --
3.2 Recursive Procedures 102 --
3.3 What Is a Proof? 108 --
3.4 Induction Proofs 111 --
3.5 Proving Correctness of Procedures 118 --
3.6 Recurrence Equations 130 --
3.7 Recursion Trees 134 --
4 Sorting 149 --
4.2 Insertion Sort 151 --
4.3 Divide and Conquer 157 --
4.4 Quicksort 159 --
4.5 Merging Sorted Sequences 171 --
4.6 Mergesort 174 --
4.7 Lower Bounds for Sorting by Comparison of Keys 178 --
4.8 Heapsort 182 --
4.9 Comparison of Four Sorting Algorithms 197 --
4.10 Shellsort 197 --
4.11 Radix Sorting 201 --
5 Selection and Adversary Arguments 223 --
5.2 Finding max and min 226 --
5.3 Finding the Second-Largest Key 229 --
5.4 Selection Problem 233 --
5.5 A Lower Bound for Finding the Median 238 --
5.6 Designing Against an Adversary 240 --
6 Dynamic Sets and Searching 249 --
6.2 Array Doubling 250 --
6.3 Amortized Time Analysis 251 --
6.4 Red-Black Trees 253 --
6.5 Hashing 275 --
6.6 Dynamic Equivalence Relations and Union-Find Programs 283 --
6.7 Priority Queues with a Decrease Key Operation 295 --
Programs 309 --
7 Graphs and Graph Traversals 313 --
7.2 Definitions and Representations 314 --
7.3 Traversing Graphs 328 --
7.4 Depth-First Search on Directed Graphs 336 --
7.5 Strongly Connected Components of a Directed Graph 357 --
7.6 Depth-First Search on Undirected Graphs 364 --
7.7 Biconnected Components of an Undirected Graph 366 --
8 Graph Optimization Problems and Greedy Algorithms 387 --
8.2 Prim's Minimum Spanning Tree Algorithm 388 --
8.3 Single-Source Shortest Paths 403 --
8.4 Kruskal's Minimum Spanning Tree Algorithm 412 --
9 Transitive Closure, All-Pairs Shortest Paths 425 --
9.2 Transitive Closure of a Binary Relation 426 --
9.3 Warshall's Algorithm for Transitive Closure 430 --
9.4 All-Pairs Shortest Paths in Graphs 433 --
9.5 Computing Transitive Closure by Matrix Operations 436 --
9.6 Multiplying Bit Matrices--Kronrod's Algorithm 439 --
10 Dynamic Programming 451 --
10.2 Subproblem Graphs and Their Traversal 453 --
10.3 Multiplying a Sequence of Matrices 457 --
10.4 Constructing Optimal Binary Search Trees 466 --
10.5 Separating Sequences of Words into Lines 471 --
10.6 Developing a Dynamic Programming Algorithm 474 --
11 String Matching 483 --
11.2 A Straightforward Solution 485 --
11.3 Knuth-Morris-Pratt Algorithm 487 --
11.4 Boyer-Moore Algorithm 495 --
11.5 Approximate String Matching 504 --
12 Polynomials and Matrices 515 --
12.2 Evaluating Polynomial Functions 516 --
12.3 Vector and Matrix Multiplication 522 --
12.4 Fast Fourier Transform and Convolution 528 --
13 NP-Complete Problems 547 --
13.2 P and NP 548 --
13.3 NP-Complete Problems 559 --
13.4 Approximation Algorithms 570 --
13.5 Bin Packing 572 --
13.6 Knapsack and Subset Sum Problems 577 --
13.7 Graph Coloring 581 --
13.8 Traveling Salesperson Problem 589 --
13.9 Computing with DNA 592 --
14 Parallel Algorithms 611 --
14.2 Parallelism, the PRAM, and Other Models 612 --
14.3 Some Simple PRAM Algorithms 616 --
14.4 Handling Write Conflicts 622 --
14.5 Merging and Sorting 624 --
14.6 Finding Connected Components 628 --
14.7 A Lower Bound for Adding n Integers 641 --
A Java Examples and Techniques 649 --
A.2 A Java Main Program 651 --
A.3 A Simple Input Library 656 --
A.4 Documenting Java Classes 658 --
A.5 Generic Order and the "Comparable" Interface 659 --
A.6 Subclasses Extend the Capability of Their Superclass 663 --
A.7 Copy via the "Cloneable" Interface 667.
"This edition features an increased emphasis on algorithm design techniques such as divide-and-conquer and greedy algorithms, along with the addition of new topics and exercises. It continues the tradition of solid mathematical analysis and clear writing style: emphasizes the development of algorithms through a step-by-step process rather than by merely presenting the end result; stresses the importance of the algorithm analysis process - continuously re-evaluating, modifying, and perhaps rejecting algorithms until a satisfactory solution is attained; provides extensive treatment of recursion with a clear, student-friendly review of how it works and why it is a valuable programming technique; uses a Java-like pseudocode; and includes an appendix with java examples."
9788178081717 8178081717
Computer algorithms.
Computer programming.
Algorithms.
005.1 / BAA