Algorithms, Probability, and Computing (2013)

Lecturers: Emo Welzl, contact person (CAB G39.2),
Thomas Holenstein (CAB G23.1), Ueli Maurer (CAB H19.2), Angelika Steger, (CAB G38), Peter Widmayer (CAB H39.2)
Assistants: Vincent Kusters (CAB G37.2), contact assistant.
Manuel Wettstein (CAB G39.3), Sandro Coretti (CAB H17), assistants.
Time: Monday 13:15-15:00 CAB G51,
Tuesday 14:15-16:00 CAB G51;

Important:

  • the first lecture is on Tuesday, September 17
  • the first exercise session is on Wednesday, September 18
Credit Points: 8CP for Informatik Bachelor and Mathematik Bachelor (252-0209-00L, 4V + 2U + 1A)
Honours part: For interested students, there is now an optional honours part giving additional 2CP. The honours part consists of one additional exercise hour (Wed 15-16, CAB G52) per week. The grade will be composed of three additional special assignments and an oral presentation, counting 25% each. For questions, please contact Johannes Lengler or Timon Hertli.
Language: English
Contents: Advanced design and analysis methods for algorithms and data structures: Random(ized) Search Trees, Point Location, Minimum Cut, Randomized Algebraic Algorithms (matchings), Lovász Local Lemma, Cryptographic Reductions (XOR Lemma, Goldreich-Levin Theorem), Probabilistically Checkable Proofs (introduction).
Literature: Notes for every topic will be handed out during the course. Reading assignments are Basics of Probabilistic Analysis for the APC-Lecture. The following textbooks do not cover all topics of the course (neither is every topic treated in these textbooks a topic of the course).
  • Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest
  • Randomized Algorithms by R. Motwani und P. Raghavan
  • Computational Geometry - Algorithms and Applications by M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf
Prerequisites: Basic knowledge of Probability Theory and Theoretical Computer Science as provided by the lectures "Probability and Statistics" and "Theoretical Computer Science" of the Bachelor Programme.

Exams, Special Assignments and Grading

Grading: There will be a written midterm exam and a written final exam (see below). The final grade will be composed by the final exam (60%), midterm exam (20%), and the special assignments (20%).
Midterm Exam: TBD
Special Assignments: Twice in the course of the term, we will hand out specially marked exercises (with reading material for self-study) the solution of which (typeset in LaTeX or similar) is due two weeks later. Your solutions will be graded. You are welcome to discuss these exercises with your colleagues, but we expect you to hand in your own writeup. All material covered by the special assignments (and the regular exercises) is, unless stated otherwise, relevant for the (midterm and final) exams.
Final Exam: TBD. The exam is written and closed-book. No written material permitted.
Previous Exams: midterm exam 2007 pdf,
midterm exam 2008 pdf,
midterm exam 2009 pdf,
midterm exam 2010 pdf,
midterm exam 2011 pdf,
midterm exam 2012 pdf,
midterm exam 2013 pdf,
final exam 2007 pdf,
final exam 2008 pdf,
final exam 2009 pdf,
final exam 2010 pdf,
final exam 2011 pdf,
final exam 2012 pdf
Conditions: Absence
If there are compelling reasons why you cannot attend either of the exams or hand in a special assignment on the due date foreseen, please contact us post-haste and we can look for a solution. Note, however, that we will grant requests of this type only in very exceptional cases (doctor's note, military service, funeral, etc.). Private events (vacation, sports, career fairs, etc.) are never sufficient grounds. As far as special assignments are concerned, you can hand them in to the contact assistant by email at any time before the due date, so there is no need to be present in person.

Exchange studens who depart before the end of term
Exchange students enrolled for APC in fall might want to return to their home university prior to the date of the final exam. If this applies to you and you nonetheless wish to be evaluated and given credits for APC, then as an alternative to returning to Zurich for the exam, there is the possibility for you to take the exam at your home university at the same time it takes place in Zurich. If you want to make use of this exam mode, you as a student are responsible for finding a professor at your home university who is willing to allocate resources for such a supervision and for establishing contact between us and the other party. At any rate, arrangements of this type have to be made very timely, preferrably at the beginning of the semester. If you contact us too late, we cannot help you.

Regular Exercises

The weekly assignments are made available online by Tuesday evening (see schedule below). The "due date" is Tuesday the next week. If you would like your assistant to look over your solutions, we request that you hand them in by Tuesday 2pm.

We strongly recommend that you solve all problems on your own and attend the exercise classes. Your assistant is happy to look at your solutions at any time and correct/comment them. Although only the special assignments need to be solved and handed in mandatorily, all exercises and their solutions are part of the material relevant for the two exams.

Some of the exercises are marked as "in-class", which means that we do not expect you to solve them before the exercise class, instead, your assistant will solve them with you in class. Since handing in solutions is optional anyways, the only implication this has is that your assistant will proceed more slowly when discussing these exercises. For the regular ones, only the solutions will be presented and explained and we expect you to have looked at the problems beforehand if you wish to follow the class.

The exercise classes take place as follows:

Group Time Place Assistant
A Wednesday, 13-15 CAB G56 Sandro Coretti
B Wednesday, 13-15 CHN D44 CANCELLED
C Wednesday, 16-18 CAB G52 Manuel Wettstein

The honours exercises take place on Wednesday, 15-16 in CAB G52.

Errata to the Lecture Notes


Contents

The coarse structure of this course will be as follows (teacher assignments are provisional):
TopicLecturer
Random(ized) Search TreesPeter Widmayer
Point LocationAngelika Steger
Minimum CutAngelika Steger
Randomized Algebraic AlgorithmsEmo Welzl
Lovász Local LemmaEmo Welzl
Cryptography: Hardness, Indistinguishability, and ReductionsUeli Maurer
Introduction to PCPThomas Holenstein

Preliminary Schedule

This schedule is preliminary and subject to change. The exact schedule will be updated on a weekly basis.

Calendar WeekDateTopic Exercises
(by due date)
Solutions Honours exercises
(by due date)
Honours solutions
38 Mon 16.09.2013 No lecture! As a preparation to this week's exercises, please read the Basics of Probabilistic Analysis. ex-KW38.pdf *
ex-KW38-solution.pdf
(updated: 2013-09-19)
ex-KW38-slides.pdf
(updated: 2013-09-19)




Tue 17.09.2013 Random(ized) Search Trees
39 Mon 23.09.2013 " ex-KW39.pdf
ex-KW39-solution.pdf

ex-KW39-slides.pdf

Lecture notes (chapter 1)


Tue 24.09.2013 "
40 Mon 30.09.2013 " ex-KW40.pdf
ex-KW40-solution.pdf

ex-KW40-slides.pdf




Tue 01.10.2013 Point location
41 Mon 07.10.2013 " ex-KW41.pdf
ex-KW41-solution.pdf

ex-KW41-slides.pdf




Tue 08.10.2013 "
42 Mon 14.10.2013 Minimum Cut ex-KW42.pdf
ex-KW42-solution.pdf

ex-KW42-slides.pdf
hex1.pdf
hex1-solution.pdf


Tue 15.10.2013 "
43 Mon 21.10.2013 Randomized Algebraic Algorithms ex-KW43.pdf *
ex-KW43-solution.pdf

ex-KW43-slides.pdf
Honours SPA1 (due: Oct 23)
hspa1-solution.pdf


Tue 22.10.2013 "
44 Mon 28.10.2013 " ex-KW44.pdf(*)
Special Assignment 1 (due: Monday October 28 at the start of the lecture)
(updated: 2013-10-16 09:13)
ex-KW44-solution.pdf
(updated: 2013-11-04 07:50)
ex-KW44-slides.pdf




Tue 29.10.2013 Lovász Local Lemma
45 Mon 04.11.2013 " (No exercises: we will discuss the midterm exam in the exercise session.)







Tue 05.11.2013 MIDTERM EXAM
Location: HG E5
Time: Please arrive at 14:00
Duration: 120 minutes
Exam content: everything up to and including KW44

47 Mon 11.11.2013 " (No exercises: we will discuss the first special assignment in the exercise session.)
spa1-solution.pdf


Honours SPA2 (due: Dec 4)
Lecture notes (chapter 2) hspa2-solution.pdf


Tue 12.11.2013 Cryptography: Hardness, Indistinguishability, and Reductions
47 Mon 18.11.2013 " ex-KW47.pdf
Special Assignment 2 (due: Tue December 3 at the start of the lecture)
ex-KW47-solution.pdf spa2-solution.pdf

ex-KW47-slides.pdf




Tue 19.11.2013 "
48 Mon 25.11.2013 " ex-KW48.pdf *
ex-KW48-solution.pdf

(no slides)




Tue 26.11.2013 "
49 Mon 02.12.2013 " ex-KW49.pdf *
ex-KW49-solution.pdf

ex-KW49-slides.pdf




Tue 03.12.2013 Introduction to PCP
50 Mon 09.12.2013 " ex-KW50.pdf
ex-KW50-solution.pdf

ex-KW50-slides.pdf
Honours SPA3 (due: Jan 15)



Tue 10.12.2013 "
51 Mon 16.12.2013 " ex-KW51.pdf
ex-KW51-solution.pdf

ex-KW51-slides.pdf




Tue 17.12.2013 "

Errata to the Exercises and Solutions

Date Document(s) Version Place Correction