CS-352 Theoretical Computer Science -- Fall 2014

Course description
The goal of this course is to provide a more in-depth introduction to some of the key ideas in theoretical computer science. Over the semester, we will explore different aspects and manifestations of computing, as well as, develop a set of mathematical tools enabling us to reason about its nature. Covered material touches upon: streaming algorithms, spectral graph theory, interactive and zero-knowledge proofs, pseudorandomness, algorithmic game theory, and quantum computing.

The list of topics that we plan to cover includes:
Prerequisites
Discrete Mathematics (1st year), Algorithms (2nd year), Theory of Computation (2nd year), and mathematical maturity, i.e., ability to read and write mathematical proofs.
 Textbooks
There will be no official course textbook -- instead there will be lecture notes available within a couple of days of each lecture.

If one is looking for some supplementary reading then we recommend two positions:
Time and place
     Lectures - Fridays 10:15-12:00 in INR 219.
     Exercise sessions - Fridays 12:15-13:00 in INR 219.
Teaching staff
     Lecturer: Aleksander Mądry (aleksander.madry@epfl.ch), office hour: Fridays 14:15-15:00, INJ 113 or by appointment.
     Teaching assistant (TA): Slobodan Mitrović (slobodan.mitrovic@epfl.ch), office hour: Wednesdays 14:15-15:00, INJ 110.
Grading
     The grade will be based on two in-class exams during the semester [66%] and five problem sets [34%].
     Class participation (e.g., interaction during the lecture, asking good questions) can also (positively) influence your grade.
     More on: Exams
Both exams will happen during the semester. Each exam will be focused on the material that was covered in the corresponding half of the semester.
Exam dates will be confirmed two weeks in advance; as soon as the date is confirmed, anyone who has a conflict must let Prof. Mądry know of it immediately (for last-minute emergencies, you will need to present documentation, such as a medical certificate) -- for each exam, arrangements will be made for one (and only one) makeup exam, if necessary.

The exams are closed book, but each student is allowed to bring one A4 sheet (double-sided) of hand-written notes (no printouts or copies of someone's else notes permitted). Each exam will take the place of a lecture. (To partially make up for that - a few of the exercise session might be used as an additional lecture sessions.)
 Problem sets
There will be a total of five problem sets (roughly one problem set every two weeks) with two problems per set, on average.

All solutions should be submitted (via course Moodle) as a PDF.
Here are the guidelines:

Announcements: