Computer Algorithms: Introduction to Design and Analysis / Edition 3by Sara Baase, Allen Van Gelder
Drawing upon combined decades of teaching experience, Professors Sara Baase and Allen Van Gelder have extensively revised this best seller on algorithm design and analysis to make it the most current and accessible book available. This edition features an increased emphasis on algorithm design techniques such as divide-and-conquer and greedy algorithms, along with… See more details below
Drawing upon combined decades of teaching experience, Professors Sara Baase and Allen Van Gelder have extensively revised this best seller on algorithm design and analysis to make it the most current and accessible book available. 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 that made it so popular in previous editions.
- Emphasizes the development of algorithms through a step-by-step process rather than merely presenting the end result
- Stresses the importance of the algorithm analysis processcontinuously 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; includes an appendix with Java examples
- Publication date:
- Edition description:
- Sales rank:
- Product dimensions:
- 7.40(w) x 9.10(h) x 1.60(d)
Table of Contents
1. Analyzing Algorithms and Problems: Principles and Examples.
Java as an Algorithm Language.
A Usable Subset of Java.
Java-Based Pseudocode Conventions.
Sets, Tuples, and Relations.
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.
Definitions and Notation.
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.
Priority Queue ADT.
Union-Find ADT for Disjoint Sets.
3. Recursion and Induction.
Activation Frames and Recursive Procedure Calls.
Hints for Recursion — Method 99.
Wrappers for Recursive Procedures.
What is a Proof?
Induction Proof Schema.
Induction Proof on a Recursive Procedure.
Proving Correctness of Procedures.
Definitions and Terminology.
Elementary Control Structures.
The Single-Assignment Paradigm.
Procedures with Loops.
Correctness Proofs as a Debugging Tool.
Termination of Recursive Procedures.
Correctness of Binary Search.
Divide-and-Conquer, General Case.
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 Quicksort Strategy.
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.
Decision Trees for Sorting Algorithms.
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.
Using Properties of the Keys.
5. Selection and Adversary Arguments.
The Selection Problem.
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 Divide-and-Conquer Approach.
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 Search Trees.
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.
Closed Address Hashing.
Open Address Hashing.
Dynamic Equivalence Relations and Union-Find Programs.
Dynamic Equivalence Relations.
Some Obvious Implementations.
Analysis of wUnion and cFind (*).
Priority Queues with a Decrease Key Operation.
The Decrease Key Operation.
7. Graphs and Graph Traversals.
Definitions and Representations.
Elementary Graph Definitions.
Graph Representations and Data Structures.
Overview of Depth-First Search.
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.
Articulation Points and Biconnected Components.
The Bicomponent Algorithm.
8. Graph Optimization Problems and Greedy Algorithms.
Prim’s Minimum Spanning Tree Algorithm.
Definition and Examples of Minimum Spanning Trees.
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.
The Transitive Closure of a Binary Relation.
Definitions and Background.
Finding the Reachability Matrix by Depth-First Search.
Transitive Closure by Short Cuts.
Warshall—s Algorithm for Transitive Closure.
The Basic Algorithm.
Warshall—s Algorithm for Bit Matrices.
Distances in Graphs.
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.
A Straightforward Solution.
The Knuth-Morris-Pratt Algorithm.
Pattern Matching with Finite Automata.
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.
The New Idea.
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.
Review of Standard Algorithms.
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.
P and NP.
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 First Fit Decreasing Strategy.
The Knapsack and Subset-Sum Problems.
Some Basic Techniques.
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.
The Problem and an Overview of the Algorithm.
Adleman’s Directed Graph and the DNA Algorithm.
Analysis and Evaluation.
14. Parallel Algorithms.
Parallelism, the PRAM, and Other Models.
Some PRAM Algorithms.
The Binary Fan-In Technique.
Some Easily Parallelizable Algorithms.
Handling Write Conflicts.
Boolean or on n Bits.
An Algorithm for Finding Maximum in Constant Time.
Merging and Sorting.
Finding Connected Components.
Strategy and Techniques.
PRAM Implementation of the Algorithm.
A Lower Bound for Computing a Function on n Bits.
A: Java Examples and Techniques.
A Java “Main Program.”
Library IntListLib Examples.
Generic Order and the “Comparable” Interface.
Copy via the “Clone” Interface.
Subclasses Extend the Capability of Their Superclass. 0201612445T04062001
and post it to your social network
Most Helpful Customer Reviews
See all customer reviews >