| |
| |
| |
Fundamentals | |
| |
| |
Introduction | |
| |
| |
Algorithms | |
| |
| |
A Sample Problem | |
| |
| |
Connectivity | |
| |
| |
Union-Find Algorithms | |
| |
| |
Perspective | |
| |
| |
Summary Of Topics | |
| |
| |
Principles Of Algorithm Analysis | |
| |
| |
Empirical Analysis | |
| |
| |
Predictions And Guarantees | |
| |
| |
Growth Of Functions | |
| |
| |
Big-Oh Notation | |
| |
| |
Example: Connectivity Algorithms | |
| |
| |
Computational Complexity | |
| |
| |
Perspective | |
| |
| |
| |
Data Structures | |
| |
| |
Elementary Data Structures | |
| |
| |
Types And Structures | |
| |
| |
Arrays | |
| |
| |
Linked Lists | |
| |
| |
Elementary List Processing | |
| |
| |
Storage Allocation For Lists | |
| |
| |
Strings | |
| |
| |
Compound Structures | |
| |
| |
Perspective | |
| |
| |
Trees And Recursion | |
| |
| |
Properties Of Trees | |
| |
| |
Representing Binary Trees | |
| |
| |
Representing Forests | |
| |
| |
Traversing Trees | |
| |
| |
Elementary Recursive Programs | |
| |
| |
Divide-And-Conquer | |
| |
| |
Depth-First Search | |
| |
| |
Removing Recursion | |
| |
| |
Elementary Abstract Data Types | |
| |
| |
Pushdown Stack Adt | |
| |
| |
Stack Adt Implementations | |
| |
| |
Queue Adts And Implementations | |
| |
| |
String Adt And Implementations | |
| |
| |
Set Adt And Implementations | |
| |
| |
Amortized Growth For Array Implementations | |
| |
| |
| |
Sorting | |
| |
| |
Elementary Sorting Methods | |
| |
| |
Rules Of The Game | |
| |
| |
Selection Sort | |
| |
| |
Insertion Sort | |
| |
| |
Bubble Sort | |
| |
| |
Performance Characteristics Of Elementary Sorts | |
| |
| |
Shellsort | |
| |
| |
Sorting Other Types Of Data | |
| |
| |
Index And Pointer Sorting | |
| |
| |
Sorting Linked Lists | |
| |
| |
Distribution Counting | |
| |
| |
Quicksort | |
| |
| |
The Basic Algorithm | |
| |
| |
Performance Characteristics Of Quicksort | |
| |
| |
Stack Size | |
| |
| |
Small Subfiles | |
| |
| |
Median-Of-Three Partitioning | |
| |
| |
Equal Keys | |
| |
| |
Strings And Vectors | |
| |
| |
Selection | |
| |
| |
Mergesort | |
| |
| |
Two-Way Merging | |
| |
| |
Abstract Implace Merge | |
| |
| |
Top-Down Mergesort | |
| |
| |
Improvements To The Basic Algorithm | |
| |
| |
Bottom-Up Mergesort | |
| |
| |
Performance Characteristics Of Mergesort | |
| |
| |
Linked-List Implementations Of Mergesort | |
| |
| |
Recursion Revisited | |
| |
| |
Priority Queues And Heapsort | |
| |
| |
Elementary Implementations | |
| |
| |
Heap Data Structure | |
| |
| |
Algorithms On Heaps | |
| |
| |
Heapsort | |
| |
| |
Priority-Queue Abstract Data Type | |
| |
| |
Indirect Priority Queues | |
| |
| |
Binomial Queues | |
| |
| |
Radix Sorting | |
| |
| |
Bits, Bytes, And Words | |
| |
| |
Binary Quicksort | |
| |
| |
Msd Radix Sort | |
| |
| |
Three-Way Radix Quicksort | |
| |
| |
Lsd Radix Sort | |
| |
| |
Performance Characteristics Of Radix Sorts | |
| |
| |
Sublinear-Time Sorts | |
| |
| |
Special-Purpose Sorts | |
| |
| |
Batcher's Odd-Even Mergesort | |
| |
| |
Sorting Networks | |
| |
| |
External Sorting | |
| |
| |
Sort-Merge Implementations | |
| |
| |
Parallel Sort/Merge | |
| |
| |
| |
Searching | |
| |
| |
Symbol Tables And Bsts | |
| |
| |
Symbol-Table Abstract Data Type | |
| |
| |
Key-Indexed Search | |
| |
| |
Sequential Search | |
| |
| |
Binary Search | |
| |
| |
Binary Search Trees | |
| |
| |
Performance Characteristics Of Bsts | |
| |
| |
Index Implementations With Symbol Tables | |
| |
| |
Insertion At The Root In Bsts | |
| |
| |
Bst Implementations Of Other Adt Functions | |
| |
| |
Balanced Trees | |
| |
| |
Randomized Bsts | |
| |
| |
Splay Bsts | |
| |
| |
Top-Down 2-3-4 Trees | |
| |
| |
Red-Black Trees | |
| |
| |
Skip Lists | |
| |
| |
Performance Characteristics | |
| |
| |
Hashing | |
| |
| |
Hash Functions | |