 |
 |
 |
 |
| |
|
|
|
| Lecturers: |
Emo Welzl
(CAB G15.2), with the final chapter on PCP presented by
Thomas Holenstein,
who will start as a professor at the
department October 1st, 2009.
|
|---|---|
| Assistants: | Dominik Scheder (CAB G39.1), Martin Jaggi (CAB G33.3), Simone Frau (IFW C45.1) |
| Time: |
Monday 13:15-14:00 CAB
G11, Tuesday 14:15-16:00 CAB
G51; begin: Monday, September 21, 2009 Important: Exercise sessions already start Wednesday, September 16, 13:15, CAB G 56 |
| Credit Points: |
Informatik Bachelor (252-0203-00L, 3V+2U, 6CP). Mathematik Bachelor (252-0209-00L, 3V+2U+2A, 8CP) (extra "2A" means additional reading material and special assignments) |
| Language: | English |
| Contents: | Advanced design and analysis methods for algorithms and data structures: Random(ized) Search Trees, Point Location, Network Flows, Minimum Cut, Randomized Algebraic Algorithms (matchings), 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).
|
| Prerequisites: | Basic knowledge of Probability Theory and Theoretical Computer Science as provided by the lectures "Probability and Statistics" and "Theory of Computing" of the Bachelor Programme. |
There will be a written midterm exam and a written final exam. The final exam takes place on Monday, February 8, 2010, 9am-12m in ETA F5 (Gloriastrasse 35)
| Grading: | Informatik Bachelor (252-0203-00L, 3V+2U, 6CP).
There will be a written midterm exam and
a written final exam (see below). The grade of the midterm exam
amounts to 25% and the grade of the final exam to 75% of the final
grade. Mathematik Bachelor (252-0209-00L, 3V+2U+2A, 8CP). Same procedure as the above variant, plus extra reading material and related special graded assignments handed out during the course. The final grade is composed of the "3V+2U"-component (80%) and the "+2A"-component (20%). |
|---|---|
| Midterm Exam: | November 9, 13:00 (sharp!) - 14:00, CAB G11. Material is everything till November 3. The lecture notes and any other supplementary material for the exam is not permitted. In the week of November 2 there is no new exercise sheet. In the exercise session we will repeat the material of the exam. You are welcome to ask questions related to the material covered and to the course of the exam. |
| Final Exam: | Date and place to be announced (Sessionsprüfung). The lecture notes and any other supplementary material are not permitted for the exam. |
| Previous Exams: | Midterm exam 2007 pdf, midterm exam 2008 pdf, midterm exam 2009 pdf, final exam 2007 pdf, final exam 2008 pdf, |
| Remarks: |
For those students who are not able to do the midterm exam
because of some crucial reason (military service, etc.) there is the
opportunity of a written and oral exam two weeks after the midterm
exam. Every visiting student has to do the midterm exam. If it is however not possible for you to do the final exam there is the opportunity of a written and oral exam one or two weeks before the end of the semester. ETH students who are at a foreign university during fall have to do a written exam there under supervision and at the same time the exam takes place at ETH. If any of the reasons above prevent you from taking the exam at the indicated time and location, please inform one of the assistants at the begin of the semester. |
| Nr. | Time | Place | Assistant |
|---|---|---|---|
| 1 | Wednesday 13:15-15:00 | CAB G 56 | Simone Frau |
| 2 | Thursday 8:15-10:00 | CAB G 52 | Dominik Scheder |
| 3 | Friday 14:15-16:00 | CAB G 56 | Martin Jaggi |
| Exercises (with hints) | ||
| Mo-Fr, September 14-18 | No lectures this week | preparation exercises |
|
| ||
| Mo, 21. September | Overview of the course. Introduction and Definitions. Probability for a given binary tree. | |
| Tu, 22. September | Depth of the smallest key. Number of leaves. Overall Depth. | This exercise sheet
will be solved in the exercise
classes this week. These exercises are due on Monday, September 28: 1.7, 1.9, 1.10, 1.14 |
| Mo, 28. September | Expected Height. | |
| Tu, 29. September | Depth of Individual Keys. Quicksort. | These exercises are due on Monday,
October 5: 1.4, 1.17, 1.19, 1.26. If time permits, we will do some more exercises this week in the exercise sessions |
| Mo, 5. October | Quickselect. | |
| Tu, 6. October | Randomized Search Trees: Def. of Treaps, Insertions. Random real numbers. | These exercises are due on Monday, October 12: 1.29, 1.36, 1.39, 1.44, 1.45, 1.47 |
| Mo, 12. October | 2-dimensional range queries. Locus approach. Point/Line relative to a convex polygon. | |
| Tu, 13. October | Line relative to a convex polygon; reporting, duality, fractional cascading, counting. | These exercises are due on Monay, October 19: 2.1, 2.2, 2.3, 2.4, 2.5. There is a hint and a solution for exercise 2.3 |
| Mo, 19. October | Closest point in the plane (Post Office Problem).Trapezoidal decomposition. | |
| Tu, 20. October | Trapezoidal decomposition (cont'd). | These exercises are due on Monday, October 26: 2.6, 2.9, 2.11, 2.16, 2.17 |
|
| ||
|
| ||
| Mo, 26. October | Residual graph and augmenting path. Ford-Fulkerson algorithm. | |
| Tu, 27. October | Proof of the Main Theorem. Capacity Scaling. | These exercises are due on Monday, November 2. |
| Mo, 2. November | Shortest Augmenting Paths. | |
| Tu, 3. November | Dinits' Algorithm. Bipartite matchings. | |
| Mo, 9. November | Midterm Exam | |
| Tu, 10. November | Introduction, Random Contractions, some Bootstrapping | |
| Mo, 16. November | Bootstrapping. | These exercises are due on Monday, November 15 |
|
| ||
| Tu, 17. November | Checking Matrix Multiplication. Polynomial Identity Test. | Here is the new exercise sheet |
|
| ||
| Mo, 23. November | Testing for Perfect Bipartite Matchings and Perfect Matchings in General Graphs. | |
| Tu, 24. November | tba | Here is the new exercise sheet |
| Mo, 30. November | Definition of Approximation ratio. The max-3-SAT problem. Inapproximability (e.g. of MAX-3-SAT). Probabilistic Checkable Proofs. | |
| Tu, 1. December | Equivalence of Inapproximability and PCP | Here is the new exercise sheet |
|
| ||
| Mo, 7. December | Linearity Testing | |
| Tu, 8. December | Safe Evaluation | |
| Mo, 14. December | Proof of Baby PCP. | |
| Tu, 15. December | tba | |
| Fr, 18. December | End of Semester | |