Computer Algorithms: Introduction to Design & Analysid, 3/e
Sara Baase, Allen Van Gelder
- 出版商: Addison Wesley
- 出版日期: 1999-11-05
- 售價: $980
- 貴賓價: 9.8 折 $960
- 語言: 英文
- 頁數: 720
- 裝訂: Paperback
- ISBN: 0201612445
- ISBN-13: 9780201612448
-
相關分類:
Algorithms-data-structures
無法訂購
買這商品的人也買了...
-
$1,200$1,176 -
$680$490 -
$2,800$2,660 -
$860$774 -
$990$495 -
$2,520$2,394 -
$990$970 -
$1,300$1,274 -
$1,300$1,235 -
$1,050$998 -
$860$731 -
$780$616 -
$1,860$1,767 -
$650$514 -
$590$466 -
$830$813 -
$2,480$2,356 -
$2,350$2,233 -
$690$497 -
$720$518 -
$750$675 -
$1,000$790 -
$490$387 -
$1,150$1,127 -
$1,881$1,782
商品描述
Description
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.
Features
-
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.
Table Of Contents
1. Analyzing Algorithms and Problems: Principles and Examples. Introduction.
Java as an Algorithm Language.
Mathematical Background.
Analyzing Algorithms and Problems.
Classifying Functions by their Asymptotic Growth Rates.
Searching an Ordered Array.
Java as an Algorithm Language.
A Usable Subset of Java.
Organizer Classes.
Java-Based Pseudocode Conventions.
Organizer Classes.
Java-Based Pseudocode Conventions.
Mathematical Background.
Sets, Tuples, and Relations.
Algebra and Calculus Tools.
Elements of Logic.
Algebra and Calculus Tools.
Elements of Logic.
Analyzing Algorithms and Problems.
Correctness.
Amount of Work Done.
Average and Worst-Case Analysis.
Space Usage.
Simplicity.
Optimality.
Lower Bounds and the Complexity of Problems.
Implementation and Programming.
Amount of Work Done.
Average and Worst-Case Analysis.
Space Usage.
Simplicity.
Optimality.
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.
How Important Is Asymptotic Order?
Properties of O, Theta, and Omega.
The Asymptotic Order of Commonly Occuring Sums.
Searching an Ordered Array.
Some Solutions.
Worst-Case Analysis of Binary Search.
Average-Behavior Analysis.
Optimality.
Worst-Case Analysis of Binary Search.
Average-Behavior Analysis.
Optimality.
2. Data Abstraction and Basic Data Structures.
Introduction.
ADT Specifications and Design Techniques.
Elementary ADTs — Lists and Trees.
Stacks and Queues.
ADTs for Dynamic Sets.
ADT Specifications and Design Techniques.
ADT Specifications.
ADT Design Techniques.
ADT Design Techniques.
Elementary ADTs — Lists and Trees.
Recursive ADTs.
The List ADT.
Binary Tree ADT.
The Tree ADT.
In-Tree ADT.
The List ADT.
Binary Tree ADT.
The Tree ADT.
In-Tree ADT.
Stacks and Queues.
Stack ADT.
Queue ADT.
Queue ADT.
ADTs for Dynamic Sets.
Priority Queue ADT.
Union-Find ADT for Disjoint Sets.
Dictionary ADT.
Union-Find ADT for Disjoint Sets.
Dictionary ADT.
3. Recursion and Induction.
Introduction.
Recursive Procedures.
What is a Proof?
Induction Proofs.
Proving Correctness of Procedures.
Recurrence Equations.
Recursion Trees.
Recursive Procedures.
Activation Frames and Recursive Procedure Calls.
Hints for Recursion — Method 99.
Wrappers for Recursive Procedures.
Hints for Recursion — Method 99.
Wrappers for Recursive Procedures.
What is a Proof?
Induction Proofs.
Induction Proof Schema.
Induction Proof on a Recursive Procedure.
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.
Elementary Control Structures.
The Single-Assignment Paradigm.
Procedures with Loops.
Correctness Proofs as a Debugging Tool.
Termination of Recursive Procedures.
Correctness of Binary Search.
Recurrence Equations.
Recursion Trees.
Divide-and-Conquer, General Case.
Chip and Conquer, or be Conquered.
Why Recursion Trees Work (*).
Chip and Conquer, or be Conquered.
Why Recursion Trees Work (*).
4. Sorting.
Introduction.
Insertion Sort.
Divide and Conquer.
Quicksort.
Merging Sorted Sequences.
Mergesort.
Lower Bounds for Sorting by Comparison of Keys.
Heapsort.
Comparison of Four Sorting Methods.
Shellsort.
Radix Sorting.
Insertion Sort.
The Strategy.
The Algorithm and Analysis.
Lower Bounds on the Behavior of Certain Sorting Algorithms.
The Algorithm and Analysis.
Lower Bounds on the Behavior of Certain Sorting Algorithms.
Divide and Conquer.
Quicksort.
The Quicksort Strategy.
The Partition Subroutine.
Analysis of Quicksort.
Improvements on the Basic Quicksort Algorithm.
The Partition Subroutine.
Analysis of Quicksort.
Improvements on the Basic Quicksort Algorithm.
Merging Sorted Sequences.
Worst Case.
Optimality of Merge.
Space Usage.
Optimality of Merge.
Space Usage.
Mergesort.
Lower Bounds for Sorting by Comparison of Keys.
Decision Trees for Sorting Algorithms.
Lower Bound for Worst Case.
Lower Bound for Average Behavior.
Lower Bound for Worst Case.
Lower Bound for Average Behavior.
Heapsort.
Heaps.
The Heapsort Strategy.
FixHeap.
Heap Construction.
Implementation of a Heap and the Heapsort Algorithm.
Accelerated Heapsort.
The Heapsort Strategy.
FixHeap.
Heap Construction.
Implementation of a Heap and the Heapsort Algorithm.
Accelerated Heapsort.
Comparison of Four Sorting Methods.
Shellsort.
The Algorithm.
Analysis and Remarks.
Analysis and Remarks.
Radix Sorting.
Using Properties of the Keys.
Radix Sort.
Radix Sort.
5. Selection and Adversary Arguments.
Introduction.
Finding max and min.
Finding the Second-Largest Key.
The Selection Problem.
Designing Against an Adversary.
The Selection Problem.
Lower Bounds.
Adversary Arguments.
Tournaments.
Lower Bounds.
Adversary Arguments.
Tournaments.
Finding max and min.
Finding the Second-Largest Key.
Introduction.
The Tournament Method.
An Adversary Lower-Bound Argument.
Implementation of the Tournament Method for Finding max and secondLargest.
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.
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.
Introduction.
Array Doubling.
Amortized Time Analysis.
Red-Black Trees.
Hashing.
Dynamic Equivalence Relations and Union-Find Programs.
Priority Queues with a Decrease Key Operation.
Array Doubling.
Amortized Time Analysis.
Red-Black Trees.
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.
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.
Hashing.
Closed Address Hashing.
Open Address Hashing.
Hash Functions.
Open Address Hashing.
Hash Functions.
Dynamic Equivalence Relations and Union-Find Programs.
Dynamic Equivalence Relations.
Some Obvious Implementations.
Union-Find Programs.
Weighted Union.
Path Compression.
Analysis of wUnion and cFind (*).
Applications.
Some Obvious Implementations.
Union-Find Programs.
Weighted Union.
Path Compression.
Analysis of wUnion and cFind (*).
Applications.
Priority Queues with a Decrease Key Operation.
The Decrease Key Operation.
Pairing Forests.
Pairing Forests.
7. Graphs and Graph Traversals.
Definitions and Representations.
Traversing Graphs.
Strongly Connected Components of a Directed Graph.
Biconnected Components of an Undirected Graph.
Some Examples.
Elementary Graph Definitions.
Graph Representations and Data Structures.
Elementary Graph Definitions.
Graph Representations and Data Structures.
Traversing Graphs.
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.
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.
Definitions.
A Strong Component Algorithm.
Analysis.
A Strong Component Algorithm.
Analysis.
Biconnected Components of an Undirected Graph.
Articulation Points and Biconnected Components.
The Bicomponent Algorithm.
Analysis.
Generalizations.
The Bicomponent Algorithm.
Analysis.
Generalizations.
8. Graph Optimization Problems and Greedy Algorithms.
Introduction.
Prim's Minimum Spanning Tree Algorithm.
Single-Source Shortest Paths.
Kruskal's Minimum Spanning Tree Algorithm.
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.
Implementation.
Analysis (Time and Space).
Lower Bound.
An Overview of the Algorithm.
Properties of Minimum Spanning Trees.
Correctness of Prim's MST Algorithm.
Managing the Fringe Efficiently with a Priority Queue.
Implementation.
Analysis (Time and Space).
Lower Bound.
Single-Source Shortest Paths.
Background.
Properties of Shortest Paths.
Dijkstra's Shortest-Path Algorithm.
Implementation.
Properties of Shortest Paths.
Dijkstra's Shortest-Path Algorithm.
Implementation.
Kruskal's Minimum Spanning Tree Algorithm.
Analysis.
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.
The Basic Algorithm.
Warshall—s Algorithm for Bit Matrices.
Introduction.
Kronrod—s Algorithm.
Lower Bound (*).
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.
Computing Transitive Closure by Matrix Operations.
Multiplying Bit Matrices — Kronrod's Algorithm.
Introduction.
Kronrod—s Algorithm.
Lower Bound (*).
10. Dynamic Programming.
Introduction.
Multiplying a Sequence of Matrices.
Constructing Optimal Binary Search Trees.
Separating Words into Lines.
Some Comments on Developing a Dynamic Programming Algorithm.
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.
The Boyer-Moore Algorithm.
Approximate String Matching.
Exercises.
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 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.
Remarks.
And the “Old” Idea.
The Boyer-Moore Scan Algorithm.
Remarks.
Approximate String Matching.
Exercises.
12. Polynomials and Matrices.
Introductory Comments.
Evaluating Polynomial Functions.
Vector and Matrix Multiplication.
The Fast Fourier Transform and Convolution (*).
Evaluating Polynomial Functions.
Algorithms.
Lower Bounds for Polynomial Evaluation.
Preprocessing of Coefficients.
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.
Winograd's Matrix Multiplication.
Lower Bounds for Matrix Multiplication.
Strassen's Matrix Multiplication.
The Fast Fourier Transform and Convolution (*).
Introduction.
The Fast Fourier Transform.
Convolution.
Appendix: Complex Numbers and Roots of Unity.
The Fast Fourier Transform.
Convolution.
Appendix: Complex Numbers and Roots of Unity.
13. NP-Complete Problems.
P and NP.
NP-Complete Problems.
Approximation Algorithms.
Bin Packing.
The Knapsack and Subset-Sum Problems.
Graph Coloring.
The Traveling Salesperson Problem.
Computing with DNA.
Decision Problems.
Some Sample Problems.
The Class P.
The Class NP.
The Size of the Input.
Some Sample Problems.
The Class P.
The Class NP.
The Size of the Input.
NP-Complete Problems.
Polynomial Reductions.
Some Known NP-Complete Problems.
What Makes a Problem Hard?
Optimization Problems and Decision Problems.
Some Known NP-Complete Problems.
What Makes a Problem Hard?
Optimization Problems and Decision Problems.
Approximation Algorithms.
Bin Packing.
The First Fit Decreasing Strategy.
Other Heuristics.
Other Heuristics.
The Knapsack and Subset-Sum Problems.
Graph Coloring.
Some Basic Techniques.
Approximate Graph Coloring Is Hard.
Wigderson's Graph Coloring Algorithm.
Approximate Graph Coloring Is Hard.
Wigderson's Graph Coloring Algorithm.
The Traveling Salesperson Problem.
Greedy Strategies.
The Nearest Neighbor Strategy.
The Shortest Link Strategy.
How Good Are the TSP Approximation Algorithms?
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.
DNA Background.
Adleman's Directed Graph and the DNA Algorithm.
Analysis and Evaluation.
DNA Background.
Adleman's Directed Graph and the DNA Algorithm.
Analysis and Evaluation.
14. Parallel Algorithms.
Parallelism, the PRAM, and Other Models.
Some PRAM Algorithms.
Handling Write Conflicts.
Merging and Sorting.
Finding Connected Components.
A Lower Bound for Computing a Function on n Bits.
Introduction.
The PRAM.
Other Models.
The PRAM.
Other Models.
Some PRAM Algorithms.
The Binary Fan-In Technique.
Some Easily Parallelizable Algorithms.
Some Easily Parallelizable Algorithms.
Handling Write Conflicts.
Boolean or on n Bits.
An Algorithm for Finding Maximum in Constant Time.
An Algorithm for Finding Maximum in Constant Time.
Merging and Sorting.
Introduction.
Merging.
Sorting.
Merging.
Sorting.
Finding Connected Components.
Strategy and Techniques.
The Algorithm.
PRAM Implementation of the Algorithm.
Analysis.
The Algorithm.
PRAM Implementation of the Algorithm.
Analysis.
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
Library IntListLib Examples.
Generic Order and the “Comparable” Interface.
Copy via the “Clone” Interface.
Subclasses Extend the Capability of Their Superclass. 0201612445T04062001
Supplements
General Supplements
- Online Solutions Manual
See "CS Supplement List" on PIRL for more information.