Advanced Algorithms (semester 2012A)

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.




  1. Nov. 3, Uri: The basics of Linear Programming [lecture notes #1
  2. Nov. 10, Uri: The simplex and ellipsoid algorithms [supplementary reading: lecture notes on simplex and on ellipsoid]
  3. Nov. 17, Uri: Duality and total unimodularity [lecture notes #3]
  4. Nov. 24, Robi: Flow/cut gaps (single-commodity and multi-commodity) [lecture notes #4]
  5. Dec. 1, Robi: Concurrent-flow/sparsest-cut gap [lecture notes #5]
  6. Dec. 8, Robi: Spectral graph theory (basics and easy direction of Cheeger's inequality) [lecture notes #6]
  7. Dec. 15, Robi: Cheeger's inequality (cont'd) and balanced-cut [lecture notes #7]
  8. Dec. 22, Robi: Prediction using experts, Multiplicative Weights, and application to fast approximate LP solver [lecture notes #8]
  9. Dec. 29, Uri: Treewidth and graph minors
  10. Jan. 5, Uri: Treewidth and graph minors (cont'd) [lecture notes #9+10]
  11. Jan. 12, Uri: Vertex separators and low treewidth k-coloring
  12. Jan. 19, Uri: Vertex separators and low treewidth k-coloring (cont'd) [lecture notes #11+12]
  13. Jan. 26, Robi: Graph compression and cut sparsifiers [lecture notes #13]
  14. Feb. 2, Robi: Graph sparsification for distances [lecture notes #14]


(Should be turned in within two weeks)

Reading material

Relevant textbooks:

Similar courses:

Site Meter