| |
| |
| |
| Introduction | |
| |
| |
| |
| What's the Book About? | |
| |
| |
| |
| Mathematics Review | |
| |
| |
| |
| Exponents | |
| |
| |
| |
| Logarithms | |
| |
| |
| |
| Series | |
| |
| |
| |
| Modular Arithmetic | |
| |
| |
| |
| The P Word | |
| |
| |
| |
| A Brief Introduction to Recursion | |
| |
| |
| |
| Implementing Generic Components Pre-Java 5 | |
| |
| |
| |
| Using Object for Genericity | |
| |
| |
| |
| Wrappers for Primitive Types | |
| |
| |
| |
| Using Interface Types for Genericity | |
| |
| |
| |
| Compatibility of Array Types | |
| |
| |
| |
| Implementing Generic Components Using Java 5 Generics | |
| |
| |
| |
| Simple Generic Classes and Interfaces | |
| |
| |
| |
| Autoboxing/Unboxing | |
| |
| |
| |
| The Diamond Operator | |
| |
| |
| |
| Wildcards with Bounds | |
| |
| |
| |
| Generic Static Methods | |
| |
| |
| |
| Type Bounds | |
| |
| |
| |
| Type Erasure | |
| |
| |
| |
| Restrictions on Generics | |
| |
| |
| |
| Function Objects | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| 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 | |
| |
| |
| |
| A Grain of Salt | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Lists, Stacks, and Queues | |
| |
| |
| |
| Abstract Data Types (ADTs) | |
| |
| |
| |
| The List ADT | |
| |
| |
| |
| Simple Array Implementation of Lists | |
| |
| |
| |
| Simple Linked Lists | |
| |
| |
| |
| Lists in the Java Collections API | |
| |
| |
| |
| Collection Interface | |
| |
| |
| |
| Iterators | |
| |
| |
| |
| The List Interface, ArrayList, and LinkedList | |
| |
| |
| |
| Example: Using remove on a LinkedList | |
| |
| |
| |
| ListIterators | |
| |
| |
| |
| Implementation of ArrayList | |
| |
| |
| |
| The Basic Class | |
| |
| |
| |
| The Iterator and Java Nested and Inner Classes | |
| |
| |
| |
| Implementation of LinkedList | |
| |
| |
| |
| The Stack ADT | |
| |
| |
| |
| Stack Model | |
| |
| |
| |
| Implementation of Stacks | |
| |
| |
| |
| Applications | |
| |
| |
| |
| The Queue ADT | |
| |
| |
| |
| Queue Model | |
| |
| |
| |
| Array Implementation of Queues | |
| |
| |
| |
| Applications of Queues | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| |
| Trees | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Implementation of Trees | |
| |
| |
| |
| Tree Traversals with an Application | |
| |
| |
| |
| Binary Trees | |
| |
| |
| |
| Implementation | |
| |
| |
| |
| An Example: Expression Trees | |
| |
| |
| |
| The Search Tree ADT-Binary Search Trees | |
| |
| |
| |
| contains | |
| |
| |
| |
| findMin and findMax | |
| |
| |
| |
| insert | |
| |
| |
| |
| remove | |
| |
| |
| |
| Average-Case Analysis | |
| |
| |
| |
| AVL Trees | |
| |
| |
| |
| Single Rotation | |
| |
| |
| |
| Double Rotation | |
| |
| |
| |
| Splay Trees | |
| |
| |
| |
| A Simple Idea (That Does Not Work) | |
| |
| |
| |
| Splaying | |
| |
| |
| |
| Tree Traversals (Revisited) | |
| |
| |
| |
| B-Trees | |
| |
| |
| |
| Sets and Maps in the Standard Library | |
| |
| |
| |
| Sets | |
| |
| |
| |
| Maps | |
| |
| |
| |
| Implementation of TreeSet and TreeMap | |
| |
| |
| |
| An Example That Uses Several Maps | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Hashing | |
| |
| |
| |
| General Idea | |
| |
| |
| |
| Hash Function | |
| |
| |
| |
| Separate Chaining | |
| |
| |
| |
| Hash Tables Without Linked Lists | |
| |
| |
| |
| Linear Probing | |
| |
| |
| |
| Quadratic Probing | |
| |
| |
| |
| Double Hashing | |
| |
| |
| |
| Rehashing | |
| |
| |
| |
| Hash Tables in the Standard Library | |
| |
| |
| |
| Hash Tables with Worst-Case O(1) Access | |
| |
| |
| |
| Perfect Hashing | |
| |
| |
| |
| Cuckoo Hashing | |
| |
| |
| |
| Hopscotch Hashing | |
| |
| |
| |
| Universal Hashing | |
| |
| |
| |
| Extendible Hashing | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Priority Queues (Heaps) | |
| |
| |
| |
| Model | |
| |
| |
| |
| Simple Implementations | |
| |
| |
| |
| Binary Heap | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Implementation of Binomial Queues | |
| |
| |
| |
| Priority Queues in the Standard Library | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| Sorting | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Insertion Sort | |
| |
| |
| |
| The Algorithm | |
| |
| |
| |
| Analysis of Insertion Sort | |
| |
| |
| |
| A Lower Bound for Simple Sorting Algorithms | |
| |
| |
| |
| Shellsort | |
| |
| |
| |
| Worst-Case Analysis of Shellsort | |
| |
| |
| |
| 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 | |
| |
| |
| |
| A General Lower Bound for Sorting | |
| |
| |
| |
| Decision Trees | |
| |
| |
| |
| Decision-Tree Lower Bounds for Selection Problems | |
| |
| |
| |
| Adversary Lower Bounds | |
| |
| |
| |
| Linear-Time Sorts: Bucket Sort and Radix Sort | |
| |
| |
| |
| External Sorting | |
| |
| |
| |
| Why We Need New Algorithms | |
| |
| |
| |
| Model for External Sorting | |
| |
| |
| |
| The Simple Algorithm | |
| |
| |
| |
| Multiway Merge | |
| |
| |
| |
| Polyphase Merge | |
| |
| |
| |
| Replacement Selection | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| The Disjoint Set Class | |
| |
| |
| |
| Equivalence Relations | |
| |
| |
| |
| The Dynamic Equivalence Problem | |
| |
| |
| |
| Basic Data Structure | |
| |
| |
| |
| Smart Union Algorithms | |
| |
| |
| |
| Path Compression | |
| |
| |
| |
| Worst Case for Union-by-Rank and Path Compression | |
| |
| |
| |
| Slowly Growing Functions | |
| |
| |
| |
| An Analysis By Recursive Decomposition | |
| |
| |
| |
| An O(M log * N) Bound | |
| |
| |
| |
| An O(M � (M, N)) Bound | |
| |
| |
| |
| An Application | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| 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 | |
| |
| |
| |
| Shortest-Path Example | |
| |
| |
| |
| 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 NP-Completeness | |
| |
| |
| |
| Easy vs. Hard | |
| |
| |
| |
| The Class NP | |
| |
| |
| |
| NP-Complete Problems | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| 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 | |
| |
| |
| Summary | |
| |
| |
| Exercises | |
| |
| |
| References | |
| |
| |
| |
| 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 | |
| |
| |
| Summary | |