Drawing upon combined decades of teaching experience, Professors Sara Baase and Allen Van Gelder have extensively revised this best seller to make it the most current and accessible choice for any algorithms course. The new Third Edition features the addition of new topics and exercises and an increased emphasis on algorithm design techniques such as divide-and-conquer and greedy algorithms. It continues the tradition of solid mathematical analysis and clear writing style that made it so popular in previous editions.
NEW! Material on accelerated version of Heapsort, section on computing with DNA, chapter on Dynamic Sets.
NEW! Expanded treatment of recursion with a clear, student-friendly review of how it works, and why it is a valuable programming technique.
NEW! Expanded mathematical background emphasizes practical techniques, including solutions to recurrence equations.
NEW! Review of abstract data types, with Java class definitions for several commonly used ADTs such as list, tree, stack, and priority queue.
NEW! Pseudocode updated from Pascal-like to Java-like; includes an appendix with Java examples.
- More than 100 new exercises.
Java as an Algorithm Language.
Java-Based Pseudocode Conventions.
Algebra and Calculus Tools.
Elements of Logic.
Analyzing Algorithms and Problems.
Amount of Work Done.
Average and Worst-Case Analysis.
Lower Bounds and the Complexity of Problems.
Implementation and Programming.
Classifying Functions by their Asymptotic Growth Rates.
How Important Is Asymptotic Order?
Properties of O, Theta, and Omega.
The Asymptotic Order of Commonly Occuring Sums.
Searching an Ordered Array.
Worst-Case Analysis of Binary Search.
2. Data Abstraction and Basic Data Structures.
ADT Specifications and Design Techniques.
ADT Design Techniques.
Elementary ADTs — Lists and Trees.
The List ADT.
Binary Tree ADT.
The Tree ADT.
Stacks and Queues.
ADTs for Dynamic Sets.
Union-Find ADT for Disjoint Sets.
3. Recursion and Induction.
Hints for Recursion — Method 99.
Wrappers for Recursive Procedures.
What is a Proof?
Induction Proof on a Recursive Procedure.
Proving Correctness of Procedures.
Elementary Control Structures.
The Single-Assignment Paradigm.
Procedures with Loops.
Correctness Proofs as a Debugging Tool.
Termination of Recursive Procedures.
Correctness of Binary Search.
Chip and Conquer, or be Conquered.
Why Recursion Trees Work (*).
The Algorithm and Analysis.
Lower Bounds on the Behavior of Certain Sorting Algorithms.
Divide and Conquer.
The Partition Subroutine.
Analysis of Quicksort.
Improvements on the Basic Quicksort Algorithm.
Merging Sorted Sequences.
Optimality of Merge.
Lower Bounds for Sorting by Comparison of Keys.
Lower Bound for Worst Case.
Lower Bound for Average Behavior.
The Heapsort Strategy.
Implementation of a Heap and the Heapsort Algorithm.
Comparison of Four Sorting Methods.
Analysis and Remarks.
5. Selection and Adversary Arguments.
Finding max and min.
Finding the Second-Largest Key.
The Tournament Method.
An Adversary Lower-Bound Argument.
Implementation of the Tournament Method for Finding max and secondLargest.
The Selection Problem.
A Linear-Time Selection Algorithm (*).
Analysis of the Selection Algorithm (*).
A Lower Bound for Finding the Median.
Designing Against an Adversary.
6. Dynamic Sets and Searching.
Amortized Time Analysis.
Binary Tree Rotations.
Red-Black Tree Definitions.
Size and Depth of Red-Black Trees.
Insertion into a Red-Black Tree.
Deletion from a Red-Black Tree.
Open Address Hashing.
Dynamic Equivalence Relations and Union-Find Programs.
Some Obvious Implementations.
Analysis of wUnion and cFind (*).
Priority Queues with a Decrease Key Operation.
7. Graphs and Graph Traversals.
Elementary Graph Definitions.
Graph Representations and Data Structures.
Overview of Breadth-First Search.
Comparison of Depth-First and Breadth-First Searches.
Depth-First Search and Recursion.
Finding Connected Components with Depth-First Search.
Depth-First Search Trees.
A Generalized Depth-First Search Skeleton.
Structure of Depth-First Search.
Directed Acyclic Graphs and Topological Sort.
Strongly Connected Components of a Directed Graph.
A Strong Component Algorithm.
Biconnected Components of an Undirected Graph.
The Bicomponent Algorithm.
8. Graph Optimization Problems and Greedy Algorithms.
Prim's Minimum Spanning Tree Algorithm.
An Overview of the Algorithm.
Properties of Minimum Spanning Trees.
Correctness of Prim's MST Algorithm.
Managing the Fringe Efficiently with a Priority Queue.
Analysis (Time and Space).
Single-Source Shortest Paths.
Properties of Shortest Paths.
Dijkstra's Shortest-Path Algorithm.
Kruskal's Minimum Spanning Tree Algorithm.
9. Transitive Closure, All-Pairs Shortest Paths.
Definitions and Background.
Finding the Reachability Matrix by Depth-First Search.
Transitive Closure by Short Cuts.
The Basic Algorithm.
Warshall—s Algorithm for Bit Matrices.
Computing Transitive Closure by Matrix Operations.
Multiplying Bit Matrices — Kronrod's Algorithm.
Lower Bound (*).
10. Dynamic Programming.
Multiplying a Sequence of Matrices.
Constructing Optimal Binary Search Trees.
Separating Words into Lines.
Some Comments on Developing a Dynamic Programming Algorithm.
11. String Matching.
The Knuth-Morris-Pratt Algorithm.
The Knuth-Morris-Pratt Flowchart.
Construction of the KMP Flowchart.
Analysis of the Flowchart Construction.
The Knuth-Morris-Pratt Scan Algorithm.
The Boyer-Moore Algorithm.
And the “Old” Idea.
The Boyer-Moore Scan Algorithm.
Approximate String Matching.
12. Polynomials and Matrices.
Evaluating Polynomial Functions.
Lower Bounds for Polynomial Evaluation.
Preprocessing of Coefficients.
Vector and Matrix Multiplication.
Winograd's Matrix Multiplication.
Lower Bounds for Matrix Multiplication.
Strassen's Matrix Multiplication.
The Fast Fourier Transform and Convolution (*).
The Fast Fourier Transform.
Appendix: Complex Numbers and Roots of Unity.
13. NP-Complete Problems.
Some Sample Problems.
The Class P.
The Class NP.
The Size of the Input.
Some Known NP-Complete Problems.
What Makes a Problem Hard?
Optimization Problems and Decision Problems.
The Knapsack and Subset-Sum Problems.
Approximate Graph Coloring Is Hard.
Wigderson's Graph Coloring Algorithm.
The Traveling Salesperson Problem.
The Nearest Neighbor Strategy.
The Shortest Link Strategy.
How Good Are the TSP Approximation Algorithms?
Computing with DNA.
Adleman's Directed Graph and the DNA Algorithm.
Analysis and Evaluation.
14. Parallel Algorithms.
Some PRAM Algorithms.
Some Easily Parallelizable Algorithms.
Handling Write Conflicts.
An Algorithm for Finding Maximum in Constant Time.
Merging and Sorting.
Finding Connected Components.
PRAM Implementation of the Algorithm.
A Lower Bound for Computing a Function on n Bits.
A: Java Examples and Techniques.
Library IntListLib Examples.
Generic Order and the “Comparable” Interface.
Copy via the “Clone” Interface.
Subclasses Extend the Capability of Their Superclass. 0201612445T04062001
- Online Solutions Manual
See "CS Supplement List" on PIRL for more information.