Chapter 1 Design and Analysis of Algorithms
1.1 From Problems to Programs
1.2 Abstract Data Types
1.3 Data Types, Data Structures, and Abstract Data Types
1.4 The Running Time of a Program
1.5 Calculating the Running Time of a Program
1.6 Good Programming Practice
1.7 Super Pascal
Chapter 2 Basic Data Types
2.1 The Data Type "List"
2.2 Implementation of Lists
2.3 Stacks
2.4 Queues
2.5 Mappings
2.6 Stacks and Recursive Procedures
Chapter 3 Trees
3.1 Basic Terminology
3.2 The ADT TREE
3.3 Implementations of Trees
3.4 Binary Trees
Chapter 4 Basic Operations on Sets
4.1 Introduction to Sets
4.2 An ADT with Union, Intersection, and Difference
4.3 A Bit-Vector Implementation of Sets
4.4 A Linked-List Implementation of Sets
4.5 The Dictionary
4.6 Simple Dictionary Implementations
4.7 The Hash Table Data Structure
4.8 Estimating the Efficiency of Hash Functions
4.9 Implementation of the Mapping ADT
4.10 Priority Queues
4.11 Implementations of Priority Queues
4.12 Some Complex Set Structures
Chapter 5 Advanced Set Representation Methods
5.1 Binary Search Trees
5.2 Time Analysis of Binary Search Tree Operations
5.3 Tries
5.4 Balanced Tree Implementations of Sets
5.5 Sets with the MERGE and FIND Operations
5.6 An ADT with MERGE and SPLIT
Chapter 6 Directed Graphs
6.1 Basic Definitions
6.2 Representations for Directed Graphs
6.3 The Single-Source Shortest Paths Problem
6.4 The All-Pairs Shortest Path Problem
6.5 Traversals of Directed Graphs
6.6 Directed Acyclic Graphs
6.7 Strong Components
Chapter 7 Undirected Graphs
7.1 Definitions
7.2 Minimum-Cost Spanning Trees
7.3 Traversals
7.4 Articulation Points and Biconnected Components
7.5 Graph Matching
Chapter 8 Sorting
8.1 The Internal Sorting Model
8.2 Some Simple Sorting Schemes
8.3 Quicksort
8.4 Heapsort
8.5 Bin Sorting
8.6 A Lower Bound for Sorting by Comparisons
8.7 Order Statistics
Chapter 9 Algorithm Analysis Techniques
9.1 Efficiency of Algorithms
9.2 Analysis of Recursive Programs
9.3 Solving Recurrence Equations
9.4 A General Solution for a Large Class of Recurrences
Chapter 10 Algorithm Design Techniques
10.1 Divide-and-Conquer Algorithms
10.2 Dynamic Programming
10.3 Greedy Algorithms
10.4 Backtracking
10.5 Local Search Algorithms
Chapter 11 Data Structures and Algorithms for External Storage
11.1 A Model of External Computation
11.2 External Sorting
11.3 Storing Information in Files
11.4 External Search Trees
Chapter 12 Memory Management
12.1 The Issues in Memory Management
12.2 Managing Equal-Sized Blocks
12.3 Garbage Collection Algorithms for Equal-Sized Blocks
12.4 Storage Allocation for Objects with Mixed Sizes
12.5 Buddy Systems
12.6 Storage Compaction
Bibliography
Index
鄂公网安备 42010302001612号 