Introduction to the Design and Analysis of Algorithms

<h2>Table of Contents</h2> <div class="c-non-traditional-number-list_container"> <ul> <li>New to the Third Edition</li> <li>Preface</li> </ul> <ol> <li><strong>Introduction</strong> <ul> <li>1.1 What Is an Algorithm? <ul> <li>Exercises 1.1</li> </ul></li> <li>1.2 Fundamentals of Algorithmic Problem Solving <ul> <li>Understanding the Problem</li> <li>Ascertaining the Capabilities of the Computational Device</li> <li>Choosing between Exact and Approximate Problem Solving</li> <li>Algorithm Design Techniques</li> <li>Designing an Algorithm and Data Structures</li> <li>Methods of Specifying an Algorithm</li> <li>Proving an Algorithm’s Correctness</li> <li>Analyzing an Algorithm</li> <li>Coding an Algorithm</li> <li>Exercises 1.2</li> </ul></li> <li>1.3 Important Problem Types <ul> <li>Sorting</li> <li>Searching</li> <li>String Processing</li> <li>Graph Problems</li> <li>Combinatorial Problems</li> <li>Geometric Problems</li> <li>Numerical Problems</li> <li>Exercises 1.3</li> </ul></li> <li>1.4 Fundamental Data Structures <ul> <li>Linear Data Structures</li> <li>Graphs</li> <li>Trees</li> <li>Sets and Dictionaries</li> <li>Exercises 1.4</li> </ul></li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Fundamentals of the Analysis of Algorithm Efficiency</strong> <ul> <li>2.1 The Analysis Framework <ul> <li>Measuring an Input’s Size</li> <li>Units for Measuring Running Time</li> <li>Orders of Growth</li> <li>Worst-Case, Best-Case, and Average-Case Efficiencies</li> <li>Recapitulation of the Analysis Framework</li> <li>Exercises 2.1</li> </ul></li> <li>2.2 Asymptotic Notations and Basic Efficiency Classes <ul> <li>Informal Introduction</li> <li>O-notation</li> <li>-notation</li> <li>-notation</li> <li>Useful Property Involving the Asymptotic Notations</li> <li>Using Limits for Comparing Orders of Growth</li> <li>Basic Efficiency Classes</li> <li>Exercises 2.2</li> </ul></li> <li>2.3 Mathematical Analysis of Nonrecursive Algorithms <ul> <li>Exercises 2.3</li> </ul></li> <li>2.4 Mathematical Analysis of Recursive Algorithms <ul> <li>Exercises 2.4</li> </ul></li> <li>2.5 Example: Computing the nth Fibonacci Number <ul> <li>Exercises 2.5</li> </ul></li> <li>2.6 Empirical Analysis of Algorithms <ul> <li>Exercises 2.6</li> </ul></li> <li>2.7 Algorithm Visualization</li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Brute Force and Exhaustive Search</strong> <ul> <li>3.1 Selection Sort and Bubble Sort <ul> <li>Selection Sort</li> <li>Bubble Sort</li> <li>Exercises 3.1</li> </ul></li> <li>3.2 Sequential Search and Brute-Force String Matching <ul> <li>Sequential Search</li> <li>Brute-Force String Matching</li> <li>Exercises 3.2</li> </ul></li> <li>3.3 Closest-Pair and Convex-Hull Problems by Brute Force <ul> <li>Closest-Pair Problem</li> <li>Convex-Hull Problem</li> <li>Exercises 3.3</li> </ul></li> <li>3.4 Exhaustive Search <ul> <li>Traveling Salesman Problem</li> <li>Knapsack Problem</li> <li>Assignment Problem</li> <li>Exercises 3.4</li> </ul></li> <li>3.5 Depth-First Search and Breadth-First Search <ul> <li>Depth-First Search</li> <li>Breadth-First Search</li> <li>Exercises 3.5</li> </ul></li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Decrease-and-Conquer</strong> <ul> <li>4.1 Insertion Sort <ul> <li>Exercises 4.1</li> </ul></li> <li>4.2 Topological Sorting <ul> <li>Exercises 4.2</li> </ul></li> <li>4.3 Algorithms for Generating Combinatorial Objects <ul> <li>Generating Permutations</li> <li>Generating Subsets</li> <li>Exercises 4.3</li> </ul></li> <li>4.4 Decrease-by-a-Constant-Factor Algorithms <ul> <li>Binary Search</li> <li>Fake-Coin Problem</li> <li>Russian Peasant Multiplication</li> <li>Josephus Problem</li> <li>Exercises 4.4</li> </ul></li> <li>4.5 Variable-Size-Decrease Algorithms <ul> <li>Computing a Median and the Selection Problem</li> <li>Interpolation Search</li> <li>Searching and Insertion in a Binary Search Tree</li> <li>The Game of Nim</li> <li>Exercises 4.5</li> </ul></li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Divide-and-Conquer</strong> <ul> <li>5.1 Mergesort <ul> <li>Exercises 5.1</li> </ul></li> <li>5.2 Quicksort <ul> <li>Exercises 5.2</li> </ul></li> <li>5.3 Binary Tree Traversals and Related Properties <ul> <li>Exercises 5.3</li> </ul></li> <li>5.4 Multiplication of Large Integers and Strassen’s Matrix Multiplication <ul> <li>Multiplication of Large Integers</li> <li>Strassen’s Matrix Multiplication</li> <li>Exercises 5.4</li> </ul></li> <li>5.5 The Closest-Pair and Convex-Hull Problems <ul> <li>by Divide-and-Conquer</li> <li>The Closest-Pair Problem</li> <li>Convex-Hull Problem</li> <li>Exercises 5.5</li> </ul></li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Transform-and-Conquer</strong> <ul> <li>6.1 Presorting <ul> <li>Exercises 6.1</li> </ul></li> <li>6.2 Gaussian Elimination <ul> <li>LU Decomposition</li> <li>Computing a Matrix Inverse</li> <li>Computing a Determinant</li> <li>Exercises 6.2</li> </ul></li> <li>6.3 Balanced Search Trees <ul> <li>AVL Trees</li> <li>2-3 Trees</li> <li>Exercises 6.3</li> </ul></li> <li>6.4 Heaps and Heapsort <ul> <li>Notion of the Heap</li> <li>Heapsort</li> <li>Exercises 6.4</li> </ul></li> <li>6.5 Horner’s Rule and Binary Exponentiation <ul> <li>Horner’s Rule</li> <li>Binary Exponentiation</li> <li>Exercises 6.5</li> </ul></li> <li>6.6 Problem Reduction <ul> <li>Computing the Least Common Multiple</li> <li>Counting Paths in a Graph</li> <li>Reduction of Optimization Problems</li> <li>Linear Programming</li> <li>Reduction to Graph Problems</li> <li>Exercises 6.6</li> </ul></li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Space and Time Trade-Offs</strong> <ul> <li>7.1 Sorting by Counting <ul> <li>Exercises 7.1</li> </ul></li> <li>7.2 Input Enhancement in String Matching <ul> <li>Horspool’s Algorithm</li> <li>Boyer-Moore Algorithm</li> <li>Exercises 7.2</li> </ul></li> <li>7.3 Hashing <ul> <li>Open Hashing (Separate Chaining)</li> <li>Closed Hashing (Open Addressing)</li> <li>Exercises 7.3</li> </ul></li> <li>7.4 B-Trees <ul> <li>Exercises 7.4</li> </ul></li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Dynamic Programming</strong> <ul> <li>8.1 Three Basic Examples <ul> <li>Exercises 8.1</li> </ul></li> <li>8.2 The Knapsack Problem and Memory Functions <ul> <li>Memory Functions</li> <li>Exercises 8.2</li> </ul></li> <li>8.3 Optimal Binary Search Trees <ul> <li>Exercises 8.3</li> </ul></li> <li>8.4 Warshall’s and Floyd’s Algorithms <ul> <li>Warshall’s Algorithm</li> <li>Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem</li> <li>Exercises 8.4</li> </ul></li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Greedy Technique</strong> <ul> <li>9.1 Prim’s Algorithm <ul> <li>Exercises 9.1</li> </ul></li> <li>9.2 Kruskal’s Algorithm <ul> <li>Disjoint Subsets and Union-Find Algorithms</li> <li>Exercises 9.2</li> </ul></li> <li>9.3 Dijkstra’s Algorithm <ul> <li>Exercises 9.3</li> </ul></li> <li>9.4 Huffman Trees and Codes <ul> <li>Exercises 9.4</li> </ul></li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Iterative Improvement</strong> <ul> <li>10.1 The Simplex Method <ul> <li>Geometric Interpretation of Linear Programming</li> <li>An Outline of the Simplex Method</li> <li>Further Notes on the Simplex Method</li> <li>Exercises 10.1</li> </ul></li> <li>10.2 The Maximum-Flow Problem <ul> <li>Exercises 10.2</li> </ul></li> <li>10.3 Maximum Matching in Bipartite Graphs <ul> <li>Exercises 10.3</li> </ul></li> <li>10.4 The Stable Marriage Problem <ul> <li>Exercises 10.4</li> </ul></li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Limitations of Algorithm Power</strong> <ul> <li>11.1 Lower-Bound Arguments <ul> <li>Trivial Lower Bounds</li> <li>Information-Theoretic Arguments</li> <li>Adversary Arguments</li> <li>Problem Reduction</li> <li>Exercises 11.1</li> </ul></li> <li>11.2 Decision Trees <ul> <li>Decision Trees for Sorting</li> <li>Decision Trees for Searching a Sorted Array</li> <li>Exercises 11.2</li> </ul></li> <li>11.3 P, NP, and NP-Complete Problems <ul> <li>P and NP Problems</li> <li>NP-Complete Problems</li> <li>Exercises 11.3</li> </ul></li> <li>11.4 Challenges of Numerical Algorithms <ul> <li>Exercises 11.4</li> </ul></li> </ul> <ul> <li>Summary</li> </ul></li> <li><strong>Coping with the Limitations of Algorithm Power</strong> <ul> <li>12.1 Backtracking <ul> <li>n-Queens Problem</li> <li>Hamiltonian Circuit Problem</li> <li>Subset-Sum Problem</li> <li>General Remarks</li> <li>Exercises 12.1</li> </ul></li> <li>12.2 Branch-and-Bound <ul> <li>Assignment Problem</li> <li>Knapsack Problem</li> <li>Traveling Salesman Problem</li> <li>Exercises 12.2</li> </ul></li> <li>12.3 Approximation Algorithms for NP-Hard Problems <ul> <li>Approximation Algorithms for the Traveling Salesman Problem</li> <li>Approximation Algorithms for the Knapsack Problem</li> <li>Exercises 12.3</li> </ul></li> <li>12.4 Algorithms for Solving Nonlinear Equations <ul> <li>Bisection Method</li> <li>Method of False Position</li> <li>Newton’s Method</li> <li>Exercises 12.4</li> </ul></li> </ul> <ul> <li>Summary</li> <li>Epilogue</li> </ul></li> </ol> <h3>APPENDIX A</h3> <ul> <li>Useful Formulas for the Analysis of Algorithms</li> <li>Properties of Logarithms</li> <li>Combinatorics</li> <li>Important Summation Formulas</li> <li>Sum Manipulation Rules</li> <li>Approximation of a Sum by a Definite Integral</li> <li>Floor and Ceiling Formulas</li> <li>Miscellaneous</li> </ul> <h3>APPENDIX B</h3> <ul> <li>Short Tutorial on Recurrence Relations</li> <li>Sequences and Recurrence Relations</li> <li>Methods for Solving Recurrence Relations</li> <li>Common Recurrence Types in Algorithm Analysis</li> </ul> <h4 class="h5">References</h4> <h4 class="h5">Hints to Exercises</h4> <h4 class="h5">Index</h4> </div>