| |
| |
| |
| Introduction | |
| |
| |
| What's the Book About? | |
| |
| |
| Mathematics Review | |
| |
| |
| Exponents | |
| |
| |
| Logarithms | |
| |
| |
| Series | |
| |
| |
| Modular Arithmetic | |
| |
| |
| The P word | |
| |
| |
| A Brief Introduction to Recursion | |
| |
| |
| |
| Algorithm Analysis | |
| |
| |
| Mathematical Background | |
| |
| |
| Model | |
| |
| |
| What to Analyze | |
| |
| |
| Running Time Calculations | |
| |
| |
| A Simple Example | |
| |
| |
| General Rules | |
| |
| |
| Solutions for the Maximum Subsequence Sum Problem | |
| |
| |
| Logarithms in the Running Time | |
| |
| |
| Checking Your Analysis | |
| |
| |
| A Grain of Salt | |
| |
| |
| |
| Lists, Stacks, and Queues | |
| |
| |
| Abstract Data Types (ADTs) | |
| |
| |
| The List ADT | |
| |
| |
| Simple Array Implementation of Lists | |
| |
| |
| Linked Lists | |
| |
| |
| Programming Details | |
| |
| |
| Common Errors | |
| |
| |
| Doubly Linked Lists | |
| |
| |
| Circularly Linked Lists | |
| |
| |
| Examples | |
| |
| |
| Cursor Implementation of Linked Lists | |
| |
| |
| The Stack ADT | |
| |
| |
| Stack Model | |
| |
| |
| Implementation of Stacks | |
| |
| |
| Applications | |
| |
| |
| The Queue ADT | |
| |
| |
| Queue Model | |
| |
| |
| Array Implementation of Queues | |
| |
| |
| Applications of Queues | |
| |
| |
| |
| Trees | |
| |
| |
| Preliminaries | |
| |
| |
| Implementation of Trees | |
| |
| |
| Tree Traversals with an Application | |
| |
| |
| Binary Trees | |
| |
| |
| Implementation | |
| |
| |
| Expression Trees | |
| |
| |
| The Search Tree ADT—Binary Search Trees | |
| |
| |
| MakeEmpty | |
| |
| |
| Find | |
| |
| |
| FindMin and FindMax | |
| |
| |
| Insert | |
| |
| |
| Delete | |
| |
| |
| Average-Case Analysis | |
| |
| |
| AVL Trees | |
| |
| |
| Single Rotation | |
| |
| |
| Double Rotation | |
| |
| |
| Splay Trees | |
| |
| |
| A Simple Idea (That Does Not Work) | |
| |
| |
| Splaying | |
| |
| |
| Tree Traversals (Revisited) | |
| |
| |
| B-Trees | |
| |
| |
| |
| Hashing | |
| |
| |
| General Idea | |
| |
| |
| Hash Function | |
| |
| |
| Separate Chaining | |
| |
| |
| Open Addressing | |
| |
| |
| Linear Probing | |
| |
| |
| Quadratic Probing | |
| |
| |
| Double Hashing | |
| |
| |
| Rehashing | |
| |
| |
| Extendible Hashing | |
| |
| |
| |
| Priority Queues (Heaps) | |
| |
| |
| Model | |
| |
| |
| Simple Implementations | |
| |
| |
| Binary Heaps | |
| |
| |
| Structure Property | |
| |
| |
| Heap Order Property | |
| |
| |
| Basic Heap Operations | |
| |
| |
| Other Heap Operations | |
| |
| |
| Applications of Priority Queues | |
| |
| |
| The Selection Problem | |
| |
| |
| Event Simulation | |
| |
| |
| d-Heaps | |
| |
| |
| Leftist Heaps | |
| |
| |
| Leftist Heap Property | |
| |
| |
| Leftist Heap Operations | |
| |
| |
| Skew Heaps | |
| |
| |
| Binomial Queues | |
| |
| |
| Binomial Queue Structure | |
| |
| |
| Binomial Queue Operations | |
| |
| |
| Implementations of Binomial Queues | |
| |
| |
| |
| Sorting | |
| |
| |
| Preliminaries | |
| |
| |
| Insertion Sort | |
| |
| |
| The Algorithm | |
| |
| |
| Analysis of Insertion Sort | |
| |
| |
| A Lower Bound for Simple Sorting Algorithms | |
| |
| |
| Shellsort | |
| |
| |
| Analysis of Insertion Sort | |
| |
| |
| Heapsort | |
| |
| |
| Analysis of Heapsort | |
| |
| |
| Mergesort | |
| |
| |
| Analysis of Mergesort | |
| |
| |
| Quicksort | |
| |
| |
| Picking the Pivot | |
| |
| |
| Partitioning Strategy | |
| |
| |
| Small Arrays | |
| |
| |
| Actual Quicksort Routines | |
| |
| |
| Analysis of Quicksort | |
| |
| |
| A Linear-Expected-Time Algorithm for Selection | |
| |
| |
| Sorting Large Structures | |
| |
| |
| A General Lower Bound for Sorting | |
| |
| |
| Decision Trees | |
| |
| |
| Bucket Sort | |
| |
| |
| External Sorting | |
| |
| |
| Why We Need New Algorithms | |
| |
| |
| Model for External Sorting | |
| |
| |
| The Simple Algorithm | |
| |
| |
| Multiway Merge | |
| |
| |
| Polyphase Merge | |
| |
| |
| Replacement Selection | |
| |
| |
| |
| The Disjoint Set ADT | |
| |
| |
| Equivalence Relations | |
| |
| |
| The Dynamic Equivalence Problem | |
| |
| |
| Basic Data Structure | |
| |
| |
| Smart Union Algorithms | |
| |
| |
| Path Compression | |
| |
| |
| Worst Case for Union-by-Rank and Path Compression | |
| |
| |
| Analysis of the Union/Find Algorithm | |
| |
| |
| An Application | |
| |
| |
| |
| Graph Algorithms | |
| |
| |
| Definitions | |
| |
| |
| Representation of Graphs | |
| |
| |
| Topological Sort | |
| |
| |
| Shortest-Path Algorithms | |
| |
| |
| Unweighted Shortest Paths | |
| |
| |
| Dijkstra's Algorithm | |
| |
| |
| Graphs with Negative Edge Costs | |
| |
| |
| Acyclic Graphs | |
| |
| |
| All-Pairs Shortest Path | |
| |
| |
| Network Flow Problems | |
| |
| |
| A Simple Maximum-Flow Algorithm | |
| |
| |
| Minimum Spanning Tree | |
| |
| |
| Prim's Algorithm | |
| |
| |
| Kruskal's Algorithm | |
| |
| |
| Applications of Depth-First Search | |
| |
| |
| Undirected Graphs | |
| |
| |
| Biconnectivity | |
| |
| |
| Euler Circuits | |
| |
| |
| Directed Graphs | |
| |
| |
| Finding Strong Components | |
| |
| |
| Introduction to the NP-Completeness | |
| |
| |
| Easy vs. Hard | |
| |
| |
| The Class NP | |
| |
| |
| NP-Complete Problems | |
| |
| |
| |
| Algorithm Design Techniques | |
| |
| |
| Greedy Algorithms | |
| |
| |
| A Simple Scheduling Problem | |
| |
| |
| Huffman Codes | |
| |
| |
| Approximate Bin Packing | |
| |
| |
| Divide and Conquer | |
| |
| |
| Running Time of Divide and Conquer Algorithms | |
| |
| |
| Closest-Points Problem | |
| |
| |
| The Selection Problem | |
| |
| |
| Theoretical Improvements for Arithmetic Problems | |
| |
| |
| Dynamic Programming | |
| |
| |
| Using a Table Instead of Recursion | |
| |
| |
| Ordering Matrix Multiplications | |
| |
| |
| Optimal Binary Search Tree | |
| |
| |
| All-Pairs Shortest Path | |
| |
| |
| Randomized Algorithms | |
| |
| |
| Random Number Generators | |
| |
| |
| Skip Lists | |
| |
| |
| Primality Testing | |
| |
| |
| Backtracking Algorithms | |
| |
| |
| The Turnpike Reconstruction Problem | |
| |
| |
| Games | |
| |
| |
| |
| Amortized Analysis | |
| |
| |
| An Unrelated Puzzle | |
| |
| |
| Binomial Queues | |
| |
| |
| Skew Heaps | |
| |
| |
| Fibonacci Heaps | |
| |
| |
| Cutting Nodes in Leftist Heaps | |
| |
| |
| Lazy Merging for Binomial Queues | |
| |
| |
| The Fibonacci Heap Operations | |
| |
| |
| Proof of the Time Bound | |
| |
| |
| Splay Trees | |
| |
| |
| |
| Advanced Data Structures and Implementation | |
| |
| |
| Top-Down Splay Trees | |
| |
| |
| Red Black Trees | |
| |
| |
| Bottom-Up Insertion | |
| |
| |
| Top-Down Red Black Trees | |
| |
| |
| Top-Down Deletion | |
| |
| |
| Deterministic Skip Lists | |
| |
| |
| AA-Trees | |
| |
| |
| Treaps | |
| |
| |
| k-d Trees | |
| |
| |
| Pairing Heaps | |
| |
| |
| Index 0201498405T04062001<$$$> | |