Normal view

# Computer algorithms : introduction to design and analysis

Material type: TextPublication details: New Delhi. : Pearson Education, c2000Edition: 3rd edDescription: xix, 688 pages : illustrationsISBN: 9788178081717; 8178081717Subject(s): Computer algorithms | Computer programming | AlgorithmsDDC classification: 005.1
Contents:
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.
Summary: "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."
Tags from this library: No tags from this library for this title.
Star ratings
Holdings
Item type Current library Collection Call number Status Date due Barcode Item holds
Lending Books Main Library
Stacks
Reference 005.1 BAA (Browse shelf(Opens below)) Available 015138
Reference Books Main Library
Reference
Reference 005.1 BAA (Browse shelf(Opens below)) Available 012390
Lending Books Main Library
Stacks
Reference 005.1 BAA (Browse shelf(Opens below)) Available 009623
Total holds: 0

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 --
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."

There are no comments on this title.