算法Ⅰ-Ⅳ/国外优秀信息科学与技术系列教学用

Fundamentals

Chapter 1.Introduction

1.1 Algorithms　

1.2 A Sample Problem-Connectivity　

1.3 Union-Find Algorithms　

1.4 Perspective　

1.5 Summary of Topics　

Chapter 2.Principles of Algorithm Analysis

2.1 Implementation and Empirical Analysis　

2.2 Analysis of Algorithms　

2.3 Growth of Functions　

2.4 Big-Oh Notation　

2.5 Basic Recurrences　

2.6 Examples of Algorithm Analysis　

2.7 Guarantees, Predictions, and Limitations　

Data Structures

Chapter 3.Elementary Data Structures

3.1 Building Blocks　

3.2 Arrays' S3

3.3 Linked Lists　

3.4 Elementary List Processing　

3.5 Memory Allocation for Lists

3.6 Strings　

3.7 Compound Data Structures　

Chapter 4.Abstract Data Types

4.1 Abstract Objects and Collections of Objects　

4.2 Pushdown Stack ADT

4.3 Examples of Stack ADT Clients　

4.4 Stack ADT Implementations　

4.S Creation of a New ADT　

4.6 FIFO Queues and Generalized Queues

4.7 Duplicate and Index Items　

4.8 First-Class ADTs　

4.9 Application-Based ADT Example

4.10 Perspective

Chapter 5.Recursion and Trees

5.1 Recursive Algorithms

5.2 Divide and Conquer　

5.3 Dynamic Programming

5.4 Trees　

5.5 Mathematical Properties of Trees　

5.6 Tree Traversal

5.7 Recursive Binary-Tree Algorithms　

5.8 Graph Traversal

5.9 Perspective

Sorting

Chapter 6.Elementary Sorting Methods

6.1 Rules of the Game　

6.2 Selection Sort

6.3 Insertion Sort

6.4 Bubble Sort

6.5 Performance Characteristics of Elementary Sorts　

6.6 Shellsort

6.7 Sorting Other Types of Data

6.8 Index and Pointer Sorting

6.9 Sorting Linked Lists

6.10 Key-Indexed Counting　

Chapter 7.Quicksort

7.1 The Basic Algorithm　

7.2 Performance Characteristics of Quicksort

7.3 Stack Size　

7.4 Small Subfiles

7.5 Median-of-Three Partitioning

7.6 Duplicate Keys　

7.7 Strings and Vectors　

7.8 Selection

Chapter 8.Merging and Mergesort

8.1 Two-Way Merging　

8.2 Abstract In-Place Merge

8.3 Top-Down Mergesort

8.4 Improvements to the Basic Algorithm　

8.5 Bottom-UP Mergesort

8.6 Performance Characteristics of Mergesort

8.7 Linked-List Implementations of Mergesort

8.8 Recursion Revisited　

Chapter 9.Priority Queues and Heapsort

9.1 Elementary Implementations

9.2 Heap Data Structure

9.3 Algorithms on Heaps

9.4 Heapsort

9.5 Priority-Queue ADT

9.6 Priority Queues for Index Items

9.7 Binomial Queues

Chapter 10.Radix Sorting

10.1 Bits, Bytes, and Words　

10.2 Binary Quicksort

10.3 MSD Radis Sort　

10.4 Three-Way Radin Quicksort

10.S LSD Radis Sort　

10.6 Performance Characteristics of Radix Sorts

10.7 Sublinear-Time Sorts　

Chapter 11.Spedal-Purpose Sorts

11.1 Batcher's Odd-Even Mergesort　

11.2 Sorting Networks　

11.3 External Sorting

11.4 Sort-Merge Implementations

11.5 Parallel Sort/Merge　

Searching

Chapter 12.Symbol Tables and BSTs

12.1 Symbol-Table Abstract Data Type

12.2 Key-Indexed Search

12.3 Sequential Search

12.4 Binary Search　

12.5 Binary Search Trees (BSTs)　

12.6 Performance Characteristics of BSTs

12.7 Index Implementations with Symbol Tables　

12.8 Insertion at the Root in BSTs　

12.9 BST Implementations of Other ADT Functinns

Chapter 13.Balanced Trees

13.1 Randomized BSTs　

13.2 Splay BSTs

13.3 Top-Down 2-3-4 Trees　

13.4 Red-Black Trees

13.5 Skip Lists

13.6 Performance Characteristics

Chapter 14.Hashing

14.1 Hash Functions

14.2 Separate Chaining

14.3 Linear Probing

14.4 Double Hashing

14.5 Dynadric Hash Tables　

14.6 Perspective　

Chapter 15.Radit Search

15.1 Digital Search Trees　

15.2 Tries　

15.3 Patricia Tries　

15.4 Multiway Tries and TSTs　

15.5 Text String Index Applications

Chapter 16.External Searching

16.1 Rules of the Game

16.2 Indexed Sequential Access

16.3 B Trees

16.4 Extendible Hashing

16.5 Perspective

Index