CS105 W10 Syllabus

• January 5
  • Proving greedy algorithms correct. (KT 4.1-4.3)

• January 7
  • One more example of proving greedy algorithms correct. Review MST algorithms and implementations. (KT 4.4-4.7)

• January 10
  • Minimum-cost arborescences - multistage greedy algorithm (KT 4.9)
  • Disjoint Set Union (CLRS Chapter 21). (Skipped, because almost everyone had seen this.)

• January 12
  • Binomial Heaps (CLRS second edition Chapter 19)
  • Fibonacci Heaps (CLRS second edition Chapter 20, or 19 in third edition)

• January 14
  • Finish Fibonacci heaps
  • Divide and conquer (KT, Chapter 5). Look at finding closest points.
  • Multiplication of two n-bit numbers in O(n^1.59) time

• January 18 (x-hour)
  • FFT (KT Chapter 5 and CLRS Chapter 30)

• January 19
  • Finish FFT
  • Intro to network flows; Ford-Fulkerson

• January 21
  • Network Flows - Scaling, Edmonds-Karp, Overview of preflow-push
  • KT Chapter 7, CLRS Chapter 26

• January 24
  • Applications of network flow - Bipartite Matching, s-t edge disjoint paths, team-banquet seating, circulations with upper and lower bounds on capacities.

• January 25 (x-hour)
  • Applications of min cut: NASA experiment choice, image segmentation.

• January 26
  • String Matching. CLRS chapter 32.

• January 28
  • Review NP-completeness. (KT Chapter 8, CLRS Chapter 34)
  • 6 Basic Problems from Garey and Johnson

• January 31
  • Reductions by restriction
  • Reductions by local replacement
  • Reductions by component design

• February 2
  • Linear programming (CLRS Chapter 29)
  • Idea, standard form, feasibility, unboundedness
  • Slack variables

• February 4
  • Simplex Method
  • Cycling and how to prevent it
  • Time analysis
  • Finding a feasible starting solution

• February 7
  • Duality
  • Applications (network flow, shortest paths, etc.)

• February 8 (x-hour)
  • Introduction to randomized algorithms (KT Chapter 13)
  • Indicator Random Variables (CLRS Chapter 5)

• February 9
  • Average search time in random binary tree (See CLRS Chapter 7 for quicksort analysis, which is similar)
  • Randomized min-cut algorithm

• February 14
  • Skip lists

• February 16
  • Randomized closest pair of points algorithm
  • Hashing, Universal Hashing

• February 18
  • Finish hashing
  • Randomized algorithm for 3-coloring
  • Bounding probability tails: Markov, Chebyshev, and Chernoff bounds

• February 21
  • Randomized routing on a hypercube
  • (This material drawn from Randomized Algorithms by Motwani and Raghavan)

• February 23
  • Approximation Algorithms - idea, approximation ratio (KT Chapter 11, CLRS Chapter 35)
  • Vertex Cover - greedy algorithm with ratio 2
  • TSP - NP-hard to approximate to any ratio. Ratios of 2 and 1.5 with triangle inequality
  • Approximating 3-SAT with ratio 8/7

• February 25
  • Set cover (Book does weighted; I will do unweighted.)
  • Weighted Vertex Cover via pricing method
  • Disjoint paths via pricing method

• February 28
  • Approximations via linear programming - Vertex Cover
  • Randomized rounding
  • Load Balancing

• March 2
  PTAS - Subset Sum problem

• March 4
  • Local Search - gradient descent, simulated annealing (KT Chapter 12)
  • Nash Equilibrium

• March 7
  • Randomized approximation algorithms - Randomized Caching