CS 4540 -- Advanced Algorithms

Fall 2015

[Lectures]

Professor

Dana Randall
Office hours: Tuesday 3:00 - 4:00 and Thursday 3:00 - 4:00 in Klaus 2140 (or by request).
Email: randall@cc.gatech.edu

Teaching Assistant

Sarah Cannon
Office hours: Monday 3:00-4:00 and Wednesday 10:30-11:30, common area outside of Klaus 2140.
Email: sarah.cannon@gatech.edu

Lectures

Tues, Thurs 1:30 - 3:00, ES&T L1105.


Textbooks (recommended)

Algorithms, by Cormen, Leisersen, Rivest and Stein [CLRS]
Algorithm Design, by Kleinberg and Tardos [KT]

Midterm Exams

Thursday, October 1 (tentative)
Thursday, November 19 (tentative)


Grading

There will be no makeup exams, for any reason.
Homework: 25%
Midterms: 40%
Final: 35%


Syllabus(tentative)

• I. Introduction. Stable Marriage Problem
• II. Randomized Algorithms
  • Universal Hash Families
  • k-wise independence, linearity of expectation
  • Min-cut
• III. On-line Algorithms
  • Intro to on-line algorithms; paging
  • Randomized paging
  • k-server problem
  • Ski-rental
• IV. Tail inequalities
• V. Approximation Algorithms
  • Vertex cover, traveling salesman, set cover
  • Knapsack and PTASs
• VI. Computational Geometry
  • Convex hulls
  • Voronoi regions
  • Delaunay triangulations
• VII. Random Walks
  • Random walks and Markov chain fundamentals
• VIII. Optimization
  • Max matching and min vertex cover in bipartite graphs
  • Max independent sets