Advanced Algorithms (Algorithms B)

Messages:

• Exams are in Ross-2. You can see the final grades below. Last day for appealing (either the exams or the exercises): 23/3/2006.
• Checked exercises #4 are in Ross -2.
• Extension: The exam can be submitted until 1/3/2006, Ross closing time.
• The exam was published (see the exercises section.)
• Checked exercises #3 are in Ross -2, inside the course's closet.
• Final exam date: 15/2/2006. Exam due date: 26/2/2006.

Info:

• Lecture
  • Thursday 13-15 (Levi 6)
  
  
• Exercise Class
  • Sunday 16-18 (Sprinzak 28)

Teaching subjects:

• Advanced approximation algorithms (using linear programming and positive semi-definite programming methods)
• Online algorithms
• Semi-definite programming
• Metric spaces, embeddings with low distortions and alg$$ algorithmic applications

• Teacher - Yair Bartal
  Location: Ross 84 (ground floor) Tel. (65)84597.
  Reception hour: Flexible - set by e-mail.
• TA - Shahar Dobzinski
  Location: Ross 36, Ross Building.
  Reception hour: Flexible - set by e-mail.

Books references and links:

Approximation Algorithms:

• [A.1] Vazirani - Approximation Algorithms
• [A.2] Hochbaum - Approximation Algorithms for NP-hard Problems
• [A.3] Randomized Algorithms - R. Motwani and P. Raghavan.
• [A.5] Lecture notes on approximation algorithms from Vempala's course in MIT.
• [A.6] Lecture notes from Uri Zwick's course in Tel-Aviv university..

Online Algorithms:

• [B.1] Borodin & El-Yaniv - Online Computation and Competitive Analysis
• [B.2] Fiat & Woeginger - Online Algorithms
• [B.3] Yair's course on online algorithms from Berkeley (local mirror)



Linear Programming:

• [C.1] Bertsimas & Tsitsiklis - Linear Optimization
• [C.2] Papadimitriou & Steiglitz - Combinatorial Optimization
• [C.3] Chvatal - Linear Programming
• [C.4] Karloff - Linear programming
• [C.5] Grotschel, Schrijver & Lovasz - Geometric Algorithms and combinatorial optimization
• [C.6] Schrijver - Theory of Linear and Integer Programming
• [C.7] Michel Goemans's course lecture notes from MIT
• [C.8] Goemans's book on LP - based on lecture notes
• [C.9] Yuval Rabani (Technion) notes on LP (in Hebrew!)



Metric Spaces:

• [D.1] Matousek - Lectures on Discrete Geometry, Chapter 15
• [D.2] Indyk's survey on metric embeddings and applications
• [D.3] Linial's survey on metric embeddings

Lectures:

Exercises:

Exercise 1 -- Due 28/11/2005.
Correction: Q2.a -- you need to prove that the integrality gap is at least 2-2/n.
Exercise 2 -- Due 15/12/2005.
Correction: Q1.c -- you need to prove that Pr[ALG_B>=(1/2-epsilon)OPT ]>=1-delta
Correction: Q.3 -- the exponent in the specified chernoff bound should not be negated (i.e., it should be "(1+delta)mu" .)
Exercise 3 -- Due 6/1/2006.
Reminder: You also have to submit Q3 from the previous exercise.
Exercise 4 -- Due 2/2/2006.
Correction Q4.b: The input vector c=(c_1,...,c_n) is in {r,b}^n (for example, c_1=r iff player 1 wears a red hat.)
Correction Q3: The goal is to find an index i such that x_i=y_i=1.
Correction Q4.b3: You need to prove that half (rounded down) of the players which wear a *blue* hat will guess blue.

Exam -- Due 26/2/2006.
Correction Q2: Assume that k=r. The greedy algorithm, step a(i): we choose a set from S_i and not from S_j.
Clarification Q5a: Minimal cut here is the sparsest cut. In addition, it is enough to prove that its sparsity is Omega(1/n).

Scribes:

Some links for latex can be found here.

Week #1: Lecture Recitation
Week #2: Lecture Recitation
Week #3: Lecture Recitation
Week #4: Lecture
Week #5: Lecture Recitation
Week #6: Lecture Recitation
Week #7: Lecture Recitation
Week #8: Lecture Recitation
Week #9: Lecture Lecture
Week #10: Lecture Recitation
Week #11: Lecture Recitation
Week #12: Lecture Recitation
Week #13: Lecture

Personal Information:

Register to the course here.
View your grades here.

Back to CS HUJI Home Page