How to think about algorithms / Jeff Edmonds.

Includes index.

Prefacep. xi Introductionp. 1 Iterative Algorithms and Loop Invariants Iterative Algorithms: Measures of Progress and Loop Invariantsp. 5 A Paradigm Shift: A Sequence of Actions vs. a Sequence of Assertionsp. 5 The Steps to Develop an Iterative Algorithmp. 8 More about the Stepsp. 12 Different Types of Iterative Algorithmsp. 21 Typical Errorsp. 26 Exercisesp. 27 Examples Using More-of-the-Input Loop Invariantsp. 29 Coloring the Planep. 29 Deterministic Finite Automatonp. 31 More of the Input vs. More of the Outputp. 39 Abstract Data Typesp. 43 Specifications and Hints at Implementationsp. 44 Link List Implementationp. 51 Merging with a Queuep. 56 Parsing with a Stackp. 57 Narrowing the Search Space: Binary Searchp. 60 Binary Search Treesp. 60 Magic Sevensp. 62 VLSI Chip Testingp. 65 Exercisesp. 69 Iterative Sorting Algorithmsp. 71 Bucket Sort by Handp. 71 Counting Sort (a Stable Sort)p. 72 Radix Sortp. 75 Radix Counting Sortp. 76 Euclid's GCD Algorithmp. 79 The Loop Invariant for Lower Boundsp. 85 Recursion Abstractions, Techniques, and Theoryp. 97 Thinking about Recursionp. 97 Looking Forward vs. Backwardp. 99 With a Little Help from Your Friendsp. 100 The Towers of Hanoip. 102 Checklist for Recursive Algorithmsp. 104 The Stack Framep. 110 Proving Correctness with Strong Inductionp. 112 Some Simple Examples of Recursive Algorithmsp. 114 Sorting and Selecting Algorithmsp. 114 Operations on Integersp. 122 Ackermann's Functionp. 127 Exercisesp. 128 Recursion on Treesp. 130 Tree Traversalsp. 133 Simple Examplesp. 135 Generalizing the Problem Solvedp. 138 Heap Sort and Priority Queuesp. 141 Representing Expressions with Treesp. 149 Recursive Imagesp. 153 Drawing a Recursive Image from a Fixed Recursive and a Base Case Imagep. 153 Randomly Generating a Mazep. 156 Parsing with Context-Free Grammarsp. 159 Optimization Problems Definition of Optimization Problemsp. 171 Graph Search Algorithmsp. 173 A Generic Search Algorithmp. 174 Breadth-First Search for Shortest Pathsp. 179 Dijkstra's Shortest-Weighted-Path Algorithmp. 183 Depth-First Searchp. 188 Recursive Depth-First Searchp. 192 Linear Ordering of a Partial Orderp. 194 Exercisep. 196 Network Flows and Linear Programmingp. 198 A Hill-Climbing Algorithm with a Small Local Maximump. 200 The Primal-Dual Hill-Climbing Methodp. 206 The Steepest-Ascent Hill-Climbing Algorithmp. 214 Linear Programmingp. 219 Exercisesp. 223 Greedy Algorithmsp. 225 Abstractions, Techniques, and Theoryp. 225 Examples of Greedy Algorithmsp. 236 Example: The Job/Event Scheduling Problemp. 236 Example: The Interval Cover Problemp. 240 Example: The Minimum-Spanning-Tree Problemp. 244 Exercisesp. 250 Recursive Backtrackingp. 251 Recursive Backtracking Algorithmsp. 251 The Steps in Developing a Recursive Backtrackingp. 256 Pruning Branchesp. 260 Satisfiabilityp. 261 Exercisesp. 265 Dynamic Programming Algorithmsp. 267 Start by Developing a Recursive Backtrackingp. 267 The Steps in Developing a Dynamic Programming Algorithmp. 271 Subtle Pointsp. 277 The Question for the Little Birdp. 278 Subinstances and Subsolutionsp. 281 The Set of Subinstancesp. 284 Decreasing Time and Spacep. 288 Counting the Number of Solutionsp. 291 The New Codep. 292 Examples of Dynamic Programsp. 295 The Longest-Common-Subsequence Problemp. 295 Dynamic Programs as More-of-the-Input Iterative Loop Invariant Algorithmsp. 300 A Greedy Dynamic Program: The Weighted Job/Event Scheduling Problemp. 303 The Solution Viewed as a Tree: Chains of Matrix Multiplicationsp. 306 Generalizing the Problem Solved: Best AVL Treep. 311 All Pairs Using Matrix Multiplicationp. 314 Parsing with Context-Free Grammarsp. 315 Designing Dynamic Programming Algorithms via Reductionsp. 318 Reductions and NP-Completenessp. 324 Satisfiability Is at Least as Hard as Any Optimization Problemp. 326 Steps to Prove NP-Completenessp. 330 Example: 3-Coloring Is NP-Completep. 338 An Algorithm for Bipartite Matching Using the Network Flow Algorithmp. 342 Randomized Algorithmsp. 346 Using Randomness to Hide the Worst Casesp. 347 Solutions of Optimization Problems with a Random Structurep. 350 Appendix Existential and Universal Quantifiersp. 357 Time Complexityp. 366 The Time (and Space) Complexity of an Algorithmp. 366 The Time Complexity of a Computational Problemp. 371 Logarithms and Exponentialsp. 374 Asymptotic Growthp. 377 Steps to Classify a Functionp. 379 More about Asymptotic Notationp. 384 Adding-Made-Easy Approximationsp. 388 The Techniquep. 389 Some Proofs for the Adding-Made-Easy Techniquep. 393 Recurrence Relationsp. 398 The Techniquep. 398 Some Proofsp. 401 A Formal Proof of Correctnessp. 408 Exercise Solutionsp. 411 Conclusionp. 437 Indexp. 439

This textbook, for second- or third-year students of computer science, presents insights, notations, and analogies to help them describe and think about algorithms like an expert, without grinding through lots of formal proof. Solutions to many problems are provided to let students check their progress, while class-tested PowerPoint slides are on the web for anyone running the course. By looking at both the big picture and easy step-by-step methods for developing algorithms, the author guides students around the common pitfalls. He stresses paradigms such as loop invariants and recursion to unify a huge range of algorithms into a few meta-algorithms. The book fosters a deeper understanding of how and why each algorithm works. These insights are presented in a careful and clear way, helping students to think abstractly and preparing them for creating their own innovative ways to solve problems.

1