Algorithm Design

• Algorithm DesignJon Kleinberg and Eva TardosTable of Contents 1 Introduction: Some Representative Problems  1.1 A First Problem: Stable Matching  1.2 Five Representative Problems  Solved ExercisesExcercisesNotes and Further Reading    2 Basics of Algorithms Analysis  2.1 Computational Tractability  2.2 Asymptotic Order of Growth Notation  2.3 Implementing the Stable Matching Algorithm using Lists and Arrays2.4 A Survey of Common Running Times  2.5 A More Complex Data Structure: Priority QueuesSolved Exercises  Exercises  Notes and Further Reading    3 Graphs  3.1 Basic Definitions and Applications  3.2 Graph Connectivity and Graph Traversal  3.3 Implementing Graph Traversal using Queues and Stacks3.4 Testing Bipartiteness: An Application of Breadth-First Search  3.5 Connectivity in Directed Graphs  3.6 Directed Acyclic Graphs and Topological Ordering  Solved Exercises  Exercises  Notes and Further Reading  4 Divide and Conquer  4.1 A First Recurrence: The Mergesort Algorithm4.2 Further Recurrence Relations4.3 Counting Inversions4.4 Finding the Closest Pair of Points4.5 Integer Multiplication4.6 Convolutions and The Fast Fourier TransformSolved ExercisesExercisesNotes and Further Reading  5 Greedy Algorithms  5.1 Interval Scheduling: The Greedy Algorithm Stays Ahead  5.2 Scheduling to Minimize Lateness: An Exchange Argument5.3 Optimal Caching: A More Complex Exchange Argument5.4 Shortest Paths in a Graph  5.5 The Minimum Spanning Tree Problem  5.6 Implementing Kruskal's Algorithm: The Union-Find Data Structure5.7 Clustering  5.8 Huffman Codes and the Problem of Data Compression*5.9 Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm  Solved ExercisesExcercisesNotes and Further Reading  6 Dynamic Programming  6.1 Weighted Interval Scheduling: A Recursive Procedure  6.2 Weighted Interval Scheduling: Iterating over Sub-Problems  6.3 Segmented Least Squares: Multi-way Choices  6.4 Subset Sums and Knapsacks: Adding a Variable  6.5 RNA Secondary Structure: Dynamic Programming Over Intervals  6.6 Sequence Alignment  6.7 Sequence Alignment in Linear Space6.8 Shortest Paths in a Graph  6.9 Shortest Paths and Distance Vector Protocols  *6.10 Negative Cycles in a Graph  Solved ExercisesExercisesNotes and Further Reading    7 Network Flow  7.1 The Maximum Flow Problem and the Ford-Fulkerson Algorithm7.2 Maximum Flows and Minimum Cuts in a Network  7.3 Choosing Good Augmenting Paths  *7.4 The Preflow-Push Maximum Flow Algorithm  7.5 A First Application: The Bipartite Matching Problem7.6 Disjoint Paths in Directed and Undirected Graphs7.7 Extensions to the Maximum Flow Problem  7.8 Survey Design  7.9 Airline Scheduling  7.10 Image Segmentation&nbs

Select Guide Rating