Knowledge Frame - Part I

• Stable Matching
  • Stable Matching
    • Algorithm
      • START w/ an empty matching
      • WHILE exists a free man
        • Pick a free man m (FreeQ.DeQueue)
        • m proposes to his favorite untried womon w
          • (w = MenPre[m][P[m]]; P[m]++)
        • IF w prefer m to her current partner m'
          • (m’ = WomanPartner[w]) THEN
          • set m’ free (FreeQ.EnQueue <- m’)
          • accept m (WomanPartner[w] <- m)
        • ELSE w reject m.
          • (IF m hasn’t proposed to every woman THEN)
            • (FreeQ.EnQueue <- m)
    • Claim:
      • In man proposing, women’s partner always gets better (in her view)
    • Time Complexity: O(n^2)
• Interval Scheduling
  • Interval Scheduling
    • Algorithm
      • Sort n jobs in increasing order of finishing times
      • FOR j = 1 to n
        • IF Ij is compatible w/ accepted jobs
          • THEN accept Ij
    • Proof: find the time
    • Time Complexity: O(n*log(n))
  • Scheduling All Intervals
    • Algorithm
      • Sort jobs in increasing order of start times
      • FOR j 1 to n DO
        • IF exists a processor that can accept Ij
          • THEN Choose any such processor Pk
            • Pk accepts Ij
        • ELSE Allocate a new processor and accept Ij
    • Key point of proof
      • find the time when there are depth+1 jobs are active: right after Sj
    • Time Complexity: O(n*log(n))
• Minimum Spanning Tree
  • Claim 1: Let T be a MST, e in T, then e is the cheapest edge in the fundamental cut defined by T,e.
  • Claim 2: Let T be a MST, e in E\T, then e is the most expensive edge in the fundamental cycle defined by T,e.
  • Assume all edge weights are distinct
  • Cut Property: For any cut (A,B), let e be the cheapest cut edge, then e must belong to every MST
  • Cycle Property: For any cycle C, let e be the most expensive edge in C, the e does not belong to any MST
  • Kruskal’s Algorithm
    • Algorithm
      • Start w/ T = empty
      • FOR i = 1 to n-1 DO
        • Choose a cheapest edge from E\T and add it to T
      • OUTPUT T
    • Using Union-Find data structure
    • Time Complexity: O(m*log(n))
      • using Union-Find data structure with Union: Merge-By-Size
    • Time Complexity: O(mlog(n)) sorting + O(malpha(n)) for sorted input
      • using Union-Find data structure with Union: Merge-By-Size and Find: Path Compression
  • Prim‘s Algorithm
    • Time Complexity: O(m*log(n)) using Binary Heap
    • Time Complexity: O(n*log(n)+m) using Fibonacci Heap
  • Reverse-delete Algorithm
    • Algorithm
      • Start w/ T=E
      • FOR i = 1 to m-n+1 DO
        • choose the most expensive edge e in T, remove e from T
      • OUTPUT T
    • Time Complexity: O(m^2*n)
  • Boruvka’s Algorithm
    • Time Complexity: O(m*log(n))
  • Boruvka+Prim’s Algorithm
    • Time Complexity: O(m*log(log(n)))
• Single Source Shortest Paths
  • Dijkstra’s Algorithm
    • Algorithm
      • Start from dist[s]=0, dist[v]=w(s,v)
      • S={s} <- explored nodes: for any u in S, dist[v] is final
      • Repeat n-1 time
        • Pick v in V\S, s.t. dist[v] is smallest
        • S <- SU{v} <- mask v as explored, dist[v] finalized new edges: (v,u) for all u in V\S, for every (v,u) in E, u in V\S <- representation of v
          • dist[u] = min{dist[u], dist[v]+w(v,u)}, from [u]<-v if the update is successful
    • Time Complexity: O(m*log(n)) using Binary Heap
    • Time Complexity: O(n*log(n)+m) using Fibonacci