Computer Science 284/484

Advanced Algorithms

Spring 2012

Instructor: Daniel Stefankovic
Class: Tuesday, Thursday 12:30pm-13:45pm, CSB 632.
Instructor office hours (CSB 620): Mon, Wed 4pm-5pm, or by appointment.

Textbooks (all on a 2 hour reserve in the library):

• required: Approximation Algorithms, V. Vazirani, 2004.
• recommended: The Design of Approximation Algorithms, D.Williamson, D. Shmoys, 2011

Other resources/recommended reading (most on a 2 hour reserve in the library):

• Introduction to Algorithms (3rd edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2009.
• Algorithm Design, J. Kleinberg and E. Tardos, 2005.
• The Design and Analysis of Algorithms, D. Kozen, 1991.
• The Design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.
• Algorithms Algorithms, R. Johnsonbaugh, M. Schaefer, 2003.
• How to Think About Algorithms Algorithms, J. Edmonds, 2008.
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher, E. Upfal, 2005.
• Randomized Algorithms, R. Motwani, P. Raghavan, 1995.

Prerequisites: CSC282.

Schedule

TOPIC: Introduction to approximation algorithms

reading: Vazirani, chapters 1-11.

Jan. 19 Th - Set cover problem

Jan. 24 Tu - Metric TSP
Jan. 26 Th - Multiway cut and k-cut

Jan. 31 Tu - k-center
Feb. 2 Th - Feedback vertex set

Feb. 7 Tu - Shortest superstring
Feb. 9 Th - Knapsack

Feb. 14 Tu - Euclidean TSP


TOPIC: Linear programming based approximation algorithms

reading: Vazirani, chapters 12-26.

Feb. 16 Th - Linear programming basics I

Feb. 21 Tu - Linear programming basics II
Feb. 23 Th - Linear programming basics III

Feb. 28 Tu - Set Cover - rounding
Mar. 1 Th - Set Cover - primal dual schema

Mar. 6 Tu - Scheduling on unrelated parallel machines
Mar. 8 Th - MIDTERM

Mar. 13 Tu - SPRING BREAK
Mar. 15 Th - SPRING BREAK

Mar. 20 Tu - Multiway cut via LP
Mar. 22 Th - Multicut

Mar. 27 Tu - Metric embeddings I
Mar. 29 Th - Metric embeddings II

Apr. 3 Tu - Sparsest cut
Apr. 5 Th - Semidefinite programming

Apr. 10 Tu - Steiner forest
Apr. 12 Th - Facility location



TOPIC: Markov Chains

reading:

Apr. 17 Tu - Monte Carlo method
Apr. 19 Th - Markov chains

Apr. 24 Tu - Colorings (coupling)
Apr. 26 Th - Matchings (canonical paths)

May. 1 Tu - review

May. 9 Wednesday (comprehensive) FINAL EXAM (7:15pm, CSB 632)

Grading

The grade for the course is the minimum of the exam grade and the homework grade. The midterm contributes 30% to the exam grade; the final exam contributes 70% to the exam grade.

Homework Rules

• Homework is collected on the due date, before class.
• No late homework will be accepted without instructor's permission (a permission must be requested at least 24 hours before the due date).
• In the final evaluation the lowest homework score will be dropped.
• You may work with other people on the homework, but you must each write up your solutions separately (without any written aid). If you work with other people, indicate who you worked with on your solution.

Test Rules

• All tests are closed book. No text or notes, no scratch paper allowed.

This course follows The University Policy on Academic Honesty .