Master Theorem

T(n) = a * T(n / b) + f(n)
x    = log_b(a)
T(n) = θ(n^x)          if f(n) = O(n^(x-ε))
       θ(n^x * lg(n))  if f(n) = θ(n^x)
       θ(f(n))         if f(n) = Ω(n^(x+ε)) 
                          and a * f(n/b) <= c * f(n)

Greedy

• At each step, make the "best" next choice.
• Never backtrack or change past choices.
• Never look ahead to see if this choice has negative consequences.

Greedy Proof, Type 1

1. Describe a greedy local choice strategy
2. Setup the configurations of the greedy solution G and the optimal solution O
3. Argue that O can become G by replacing each entry in O
   For each replacement, show it is possible, because it consist the compatibilty and optimality The last two step involves induction

• In basecase, focusing on how the first greedy choice can be used in an optimal solution
• During induction,
  assume the first k choices in an optimal solution are made by the greedy algorithm, show that the k+1 choice can be made by the greedy algorithm as well

Greedy Proof, Type 2

1. Describe a greedy local choice strategy
2. Setup the configurations of the greedy solution G and the optimal solution O
3. Find out the difference between O and G
4. Try to reorder O to G and consists the optimality

Dynamic Programming

Dynamic Programming calculates a solution based on the result of a previous calculation. It saves the previous result so that no duplicate calculation needed. Dynamic Programming Design Recipe

1. Find out the subproblem
   
   
   • give a score evaluation function
   • give a recursive difinition
2. State how an array can be used to evaluate the scores
   
   
   • dimension
   • evaluation order
   • basecase
   • final result
3. How to recover the solution

Graph

Representations of Graphs

• Pointers
  
  
  • vertices have pointers to adjacent vertices
  • Cannot determine whether an edge exists directly
• Adjacency matrix
  
  
  • A matrix M, M[i, j] = 1 iff exists edge from i to j
  • waste a lot of space
• Adjacency lists
  
  
  • Link-list like representation

继续ing...