CS 4540 -- Advanced Algorithms

Fall 2012

[Main Page]

Lectures:


• Introduction
  
  • Aug 21, 23: Stable Marriage Problem
  
  
• Randomized Algorithms
  
  • Aug 30: Universal Hash Families
  • Sep 4: k-wise independence, linearity of expectation
  • Sep 6, 11: Min-cut
  
  
• On-line Algorithms
  
  • Sep 13: Intro to on-line algs; paging
  • Sep 18: Randomized paging
  • Sep 25: The k-server problem
  • Sep 27, Oct 2: Ski-rental
  
  
• Tail Inequalities
  
  • Oct 4: Expectation, Variance and Intro to tail inequalities
  • Oct 9: Midterm 1
  • Oct 11: More on tail inequalities and Applications of tail inequalities (pages 4, 5)
    
  • Oct 16: Fall Break!
  
  
• Approximation Algorithms
  
  • Oct 18, 23: Vertex cover, traveling salesman, set cover (or these notes showing rounding approaches)
  • Oct 25: Knapsack and PTASs
  
  
• Computational Geometry
  
  • Oct 30: Convex hulls
  • Nov 1, 6: Voronoi regions (see also notes by David Mount)
  • Nov 8: Delaunay triangulations (see also slides here and Mount's notes from the last lecture).
  • Fun demonstrations: Fortune's sweep algorithm applet,
  
  
• Random Walks
  
  • Nov 13: Random walks and Markov chains
  • Nov 15: Slides on Markov chains (tutorial) (first half only)
  • Nov 20: Slides on domino tilings
    
    
  • Nov 27: REVIEW (and more on MC if time)
  • Nov 29: Midterm 2 !!!!
  
  
• Optimization in special cases
  • Dec 4: Maximum matching and minimum vertex cover in bipartite graphs
  • Dec 6: Maximal independent sets
    
  • Dec 11: FINAL