某储备粮的“学习笔记” - cs341 http://blog.gregwym.info/tag/cs341/ zh-CN Fri, 16 Dec 2011 00:27:48 +0800 Fri, 16 Dec 2011 00:27:48 +0800 CS 341 Algorithm 复习小记 http://blog.gregwym.info/cs-341-algorithm-brief-review.html http://blog.gregwym.info/cs-341-algorithm-brief-review.html Fri, 16 Dec 2011 00:27:48 +0800 咳嗽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...

]]>
1 http://blog.gregwym.info/cs-341-algorithm-brief-review.html#comments http://blog.gregwym.info/feed/cs-341-algorithm-brief-review.html