1. Foundation
   1. What's more important than performance
      1. Correctness
      2. Programmer Time
      3. Maintainbility
      4. Robustness
      5. User-Friendliness
   2. Random-Access machine Model
      1. No concurrent operations
      2. Each instruction takes a constant amount of time
   3. Notation
      1. Θ
      2. O
      3. Ω
      4. o
   4. Common Function
   5. Recurrence Analysis
      1. Substitution Method
         1. 1. [Guess] the form of the solution
         2. 2. [Verify] by mathematical induction
      2. Recursion-Tree Method
         1. Topic
      3. Master Method
         1. Topic
         2. Topic
   6. Probabilistic Analysis
2. Divide & Conquer
   1. Divide Paradigm
      1. 1. [Divide] the problem into subproblems
      2. 2. [Conquer] subproblems by solving them recursively
      3. 3. [Combine] subproblems' solutions
      4. Topic
   2. Examples
      1. Merge Sort
      2. Binary Search
      3. Fibonacci Numbers
      4. Matrix Multiplication
      5. Closest Pair of Points
3. Sorting Algorithm
   1. Quick Sort
   2. Counting Sort
      1. Topic
   3. Radix Sort
      1. Idea
         1. Digit-byDigit sort
         2. Bad idea: Sort on most-significant digit first
         3. Good idea: Sort on [least-significant digit first] with auxiliary [stable] sort
      2. Correctness
         1. Topic
      3. Analysis
   4. Bucket Sort
   5. Sorting Network
4. Dynamic Programming
   1. DP vs Divide & Conquer
      1. Sameness
         1. 1. Partition the problem into subproblems
         2. 2. Combining the solutions from subproblems
      2. Differences
         1. 1. Overlapping subproblems vs no overlapping subproblems
         2. 2. Dynamic programming is typically applied to [optimization problems]
   2. Steps of DP
      1. 1. Characterize the structure of an optimal solution
      2. 2. Recursively define the value of an optimal solution
      3. 3. Compute the value of an optimal solution in a bottom-up fashion
      4. 4. Construct an optimal solution from computed information
   3. Elements of DP
      1. When look for a DP solution to a problem?
         1. 1. Optimal substructure
         2. 2. Overlapping subproblems
      2. How to discover optimal substructure?
         1. 1. Make a choice to split the problem into one or more subproblems
         2. 2. Just assume you are given the choice that leads to an optimal solution
         3. 3. Given this choice, try to best characterize the resulting space of subproblems
         4. 4. Show the subproblems chosen are optimal by using a [cut-and-paste] technique
      3. Memorization
         1. Idea
            1. 1. A memorized recursive algorithm maintains an entry in a table for the solution to each subproblem
            2. 2. When the subproblem is first encountered, its solution is computed and then stored in the table
            3. 3. Each subsequent time that the subproblem is encountered, just return the stored value in the table
         2. When to use?
            1. If some subproblems in the subproblem space need not be solved at all, the memorized solution has the advantage of solving only subproblems that are definitely required
   4. Examples
      1. Assembly-line scheduling
      2. Matrix-chain multiplication
         1. Fully parenthesized
            1. A product of matrices is [fully parenthesized] if it is either a single matrix or the product of two fully parenthesized matrix products, surrounded by parentheses.
         2. Why parenthesized?
            1. Different costs incurred by different parenthesizations
         3. Topic
      3. LCS(Longest Common String)
      4. Optimal binary search trees
5. Greedy Algorithm
6. Amortized Analysis, Heaps
7. Graph Algorithm
8. String Match
9. NP-Completeness
10. Approximation Algorithm