CS-252 Advanced Theoretical Computer Science -- Spring 2013

Course description
The goal of this course is to provide a more in-depth introduction to some of the key ideas in Theory of Computation -- and Theoretical Computer Science at large. 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. The list of topics that we want to cover includes:
Prerequisites
Discrete Mathematics (1st year), Algorithms (2nd year), and mathematical maturity, i.e., ability to read and write mathematical proofs.
Also, this course is a co-requisite for "Theoretical Computer Science" course, thus it will be assumed that the material being covered in that course is known.
 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 - Thursdays 10:15-12:00 in INM 202.
     Exercise sessions (following the lectures) - Thursdays 12:15-13:00 in INM 202 and INM 203
Teaching staff
     Lecturer: Aleksander Mądry (aleksander.madry@epfl.ch), office hours: Mondays 13:30-15:30, INJ 113 or by appointment.
     Teaching assistant (TA): Christos Kalaitzis (christos.kalaitzis@epfl.ch), office hours: Wednesdays 14:00-16:00, INJ 110.
     Questions regarding problem sets and the material, in general, should be sent to atcs2013-staff@listes.epfl.ch
Grading
     The grade will be based on three in-class exams during the semester [75%] and six problem sets [25%].
     Class participation (e.g., interaction during the lecture, asking good questions) can also (positively) influence your grade.
     More on: Exams
All three exams will happen during the semester. Each exam will be focused on the material that was covered in the roughly one-third of the course since the previous exam.
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 open-book, open-notes, but no electronic devices (cell phones, tablets, e-readers, laptops) are allowed. Each exam will take the place of a lecture.
 Problem sets
There will be a total of six problem sets (roughly one problem set every two weeks).
All solutions should be submitted (via course Moodle) as a PDF (typeset in LaTeX, not scanned, except for figures). For your convenience, there will be a template accompanying each problem set (as a .zip archive) - please use it. (These templates will be crafted individually for each problem set, so please do not reuse the templates from other problem sets.)
Here are the guidelines:

Announcements:

Schedule: