Advanced Algorithms (semester 2012A) (original) (raw)
Weizmann Institute of Science
[Course description] [Announcements] [Lectures] [Assignments] [Reading material]
Course description
Instructors: Uriel Feige and Robert Krauthgamer
When and where: Thursday 2-5pm, FGS room C
FGS code: 20124151.
Syllabus: The course will cover theoretical design and analysis of algorithms, focusing on computational problems involving combinatorial optimization, such as cuts, flows and distances in graphs. The emphasis will be on modern algorithmic approaches for finding either exact or approximate (near-optimal) solutions, using tools such as mathematical programming, matrix analysis, geometry, sparsification and compression.
Prerequisites: Students are expected to be familiar with algorithms, complexity theory, probability theory, and linear algebra, at an undergraduate level.
Webpage: http://www.wisdom.weizmann.ac.il/~robi/teaching/2012a-AdvancedAlgorithms
Announcements
- posted 2012-02-16: graded homework (#5 and #6) can be picked up from Sharon/Carol's office (Ziskind room 228).
- posted 2012-01-12: added clarification to problem set 4 question 2.
- posted 2011-12-31: The exam was (re)scheduled to Feb. 23, 2012 at 10am (FGS room C).
Lectures
- Nov. 3, Uri: The basics of Linear Programming [lecture notes #1]
- Nov. 10, Uri: The simplex and ellipsoid algorithms [supplementary reading: lecture notes on simplex and on ellipsoid]
- Nov. 17, Uri: Duality and total unimodularity [lecture notes #3]
- Nov. 24, Robi: Flow/cut gaps (single-commodity and multi-commodity) [lecture notes #4]
- additional reading: lecture notes by Trevisan, book by Vazirani
- Dec. 1, Robi: Concurrent-flow/sparsest-cut gap [lecture notes #5]
- additional reading: lecture notes by Rao-Vazirani, book by Vazirani
- Dec. 8, Robi: Spectral graph theory (basics and easy direction of Cheeger's inequality) [lecture notes #6]
- additional reading: lecture notes by Spielman and by Trevisan, book by Chung.
- Dec. 15, Robi: Cheeger's inequality (cont'd) and balanced-cut [lecture notes #7]
- additional reading: same as last week
- Dec. 22, Robi: Prediction using experts, Multiplicative Weights, and application to fast approximate LP solver [lecture notes #8]
- additional reading: survey by Arora-Hazan-Kale, lecture notes by Rao-Vazirani and by Gupta
- Dec. 29, Uri: Treewidth and graph minors
- Jan. 5, Uri: Treewidth and graph minors (cont'd) [lecture notes #9+10]
- Jan. 12, Uri: Vertex separators and low treewidth k-coloring
- Jan. 19, Uri: Vertex separators and low treewidth k-coloring (cont'd) [lecture notes #11+12]
- Jan. 26, Robi: Graph compression and cut sparsifiers [lecture notes #13]
- Feb. 2, Robi: Graph sparsification for distances [lecture notes #14]
Assignments
(Should be turned in within two weeks)
- handout1 (from Nov. 3)
- handout2 (from Nov. 17, duality)
- problem set 3 (posted Dec. 2, flow/cut gaps)
- problem set 4 (posted Dec. 23, spectral graph theory + prediction using experts)
- clarification for question #2: Assume G has unit edge-weights, and that the balance (1/2 or 2/3) is measured with respect to vertex-weights (where weight=degree).
- handout5 (posted Jan. 5)
- handout6 (from Jan. 19)
- problem set 7 (posted Feb. 4, extra credit only)
Reading material
Relevant textbooks:
- Linear Programming by Karloff
- Understanding and Using Linear Programming by Matoušek and Gärtner
- Approximation Algorithms by Vazirani
- The Design of Approximation Algorithms by Williamson and Shmoys
- Spectral Graph Theory by Fan Chung
Similar courses:
- Advanced algorithms by Feige and Krauthgamer at Weizmann (2008) [related but not identical]
- Combinatorial Algorithms and Data Structures by Satish Rao and Umesh Vazirani (2011)
- Graph Partitioning and Expanders by Luca Trevisan (2011)
- Optimization and Algorithmic Paradigms by Luca Trevisan (2011)
- Spectral Graph Theory by Dan Spielman (2009)
- Advanced Algorithms by Michel Goemans at MIT (2008)
- Advanced Algorithms by Shuchi Chawla at U. Wisconsin (2007)
- Advanced Algorithms by Jon Kleinberg at Cornell (2001)