CS-352 Theoretical Computer Science -- Fall 2013

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. The tentative list of topics that we might cover includes: Note: The material covered will be fairly disjoint to the one treated in Advanced Theoretical Computer Science course given last semester.
Prerequisites
Discrete Mathematics (1st year), Algorithms (2nd year), Theory of Computation (2nd year, former name: Theoretical Computer Science), 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 - Tuesdays 15:15-16:00 in BC 02.
Teaching staff
     Lecturer: Aleksander Mądry (aleksander.madry@epfl.ch), office hour: Fridays 13:15-14:00, INJ 113 or by appointment.
     Teaching assistant (TA): Slobodan Mitrović (slobodan.mitrovic@epfl.ch), office hour: Tuesdays 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 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 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 (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: