Lecture hours AMC 2003

• Tuesday 11.00 - 13.00, in: BBL-420.
• Thursday 09.00 - 11.00, in: BBL-420.
• Exception: FRIDAY 26 september instead of Thursday 25th.
• From week 40 onward also: Tuesday 9.00 - 11.00 (in: BBL-430), see the schedule below.
• Office hours: by appointment.
• Back to main.

LaTex template: scribe.tex.

Example source file of last year: lecture02-1.tex.

Notes posted on this site are for educational use only. They may not be used for any other purposes without the permission of the Instructor.

Weekly schedule

Week 36

• Tuesday 2 september
  Topics: administrivia, research in algorithmic systems, vehicle routing, multiple TSP.
  Lecture notes 1: (ps) (pdf).
• Thursday 4 september
  Topics: Euclidean traveling salesman problem, Clarke-Wright savings heuristic.
  Lecture notes 2: (ps) (pdf).

• Tuesday 9 september
  Topics: dominating sets, k-centers and the lazy tourist problem.
  Lecture notes 3: (ps) (pdf).
• Thursday 11 september
  Topics: fixed parameter tractability, (connected) vertex covers.
  Lecture notes 4: (ps) (pdf)

• Tuesday 16 september
  Topics: integer linear programs and reductions
  Lecture notes 5: (ps) (pdf)
• Thursday 18 september
  Topics: duality, the set cover problem.
  Lecture notes 6: (ps) (pdf)

• Tuesday 23 september
  Topics: primal-dual methods, the facility location problem.
  Lecture notes 7: (ps) (pdf)
• Friday 26 september
  Topics: personnel assignments, perfect and stable matchings.
  Lecture notes 8: (ps) (pdf)

• Tuesday 30 september
  Topics: assignments and transportation problem, equivalence to min cost flow.
  Lecture notes 9: (ps) (pdf)
• Thursday 2 october
  Topics: scheduling on identical and on unrelated machines.
  Lecture notes 10: (ps) (pdf)

• Tuesday 7 october
  Topics: 2SAT, 3SAT, the Davis-Putnam procedure.
  Lecture notes 11: (ps) (pdf)
• Thursday 9 october
  Topics: NP-completeness, tripartite matching, set cover again.
  Lecture notes 12 : (ps) (pdf)

• Tuesday 14 october
  Topics: pseudo-polynomial algorithms, 1-dimensional packing.
  Lecture notes 13: (ps) (pdf)
• Thursday 16 october
  Topics: APX, in-approximability, maximum independent set problem.
  Lecture notes 14: (ps) (pdf)

• Tuesday 21 october
  Topics: distributed processes, fault tolerance, consensus, impossibility results.
  Lecture notes 15: (ps) (pdf)
• Thursday 23 october
  Topics: crash model, consensus problem again, renaming problem.
  Lecture notes 16: (ps) (pdf)

• Tuesday 28 october
  Topics: synchronous networks, reliable broadcasting, Byzantine generals protocol.
  Lecture notes 17: (ps) (pdf)
• Thursday 30 october
  Evaluation.

• Tuesday 4 November: Tentamen
• Time: 9.00-12.00 in: BBL-160.
• The tentamen covers the topics treated and is `open notes'.
• Tentamen: (ps) (pdf)

In reserve