Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save misho-kr/e287b825f7995c13b8b1 to your computer and use it in GitHub Desktop.
Save misho-kr/e287b825f7995c13b8b1 to your computer and use it in GitHub Desktop.
Summary of "Algorithms: Design and Analysis, Part 2" course at Coursera.Org

The course will have six weeks of lectures and assignments, followed by a final exam.

Week 1

I. TWO MOTIVATING APPLICATIONS

  • Distributed shortest-path routing -- sending email messages
  • DNA sequence alignment, calculate Needleman-Wunsch score [1970]

II. SELECTED REVIEW FROM PART I

  • The Algorithm Designer’s Mantra -- "Can we do better?"
  • Big-O notation, Asymptotic analysis
  • Graph search algorithms -- BFS and DFS, Dijkstra’s Algorithm
  • Heaps -- supported operations, runtime performance, applications

III. INTRODUCTION TO GREEDY ALGORITHMS

  • No single “silver bullet” for solving problems -- divide & conquer, randomized, greedy, dynamic programming
  • Definition -- iteratively make “myopic” decisions, hope everything works out at the end
  • Easy running time analysis, hard to establish correctness
  • Many greedy algorithms are not correct, e.g.Dijkstra'a algorithm with negative edge lengths
  • Proof of correctness -- induction and exchange argument
  • The Optimal Caching Algorithm
  • Theorem: [Belady 1960s] The “furthest-in-future” algorithm is optimal (i.e., minimizes the number of cache misses)

IV. A SCHEDULING APPLICATION

  • One shared resource, many jobs to do -- in what order should we sequence the jobs?
  • Each job has a weight w-j and length i-j, Completion Time C-j is sum of all jobs up to and including j
  • Goal is to minimize the weighted sum of all completion times, min E(j=1-n) w-j * C-j
  • If weights are equal must schedule shorter jobs first, but if lengths are equal must schedule larger jobs first
  • Assign scores to jobs that are increasing in weight and decreasing in length
  • Order by decreasing ratio w-j / l-j is always correct, runtime is O(n*log(n)) to do the sorting
  • Proof by Exchange Argument

V. PRIM'S MINIMUM SPANNING TREE ALGORITHM

  • Connect vertices together while minimizing the path cost
  • Input is undirected graph G(V,E) (connected) and cost e for each edge, output is minimum cost tree T that spans all vertices
  • Applications are clustering and network routing
  • Prim's and Kruskal's algorithms, O(m*log(n))
  • Proof part 1 -- Prim's algorithm always outputs a spanning tree
  • Empty Cut Lemma -- graph is not connected <=> there exists a cut (A,B) with no crossing edges
  • Double Crossing Lemma -- if cycle C has an edge that crosses a cut (A,B) => there is another edge that crosses that cut
  • Lonely Cut Corollary -- if there is only one edge crossing some cut (A,B) => that edge is not in any cycle
  • Proof part 2 -- Prim's algorithm always outputs a MST, minimum-cost spanning tree
  • Cut Property -- in a cut (A,B) where there is an edge e with minimum cost, that edge is part of MST
  • MST is unique if edge costs are distinct
  • Naive implementation has running time O(nm) but with heaps it drops to O(mlog(n))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment