某储备粮的“学习笔记”

by 咳嗽di小鱼

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...


One comments »

  1. 吉他 吉他

    求继续=。=

Add new comment »

Enter your comment here...

captcha
请输入验证码