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