CS-251 Theory of Computation -- Spring 2014

Course description
     This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (logical circuits, finite automata, Turing machines), as well as, provides a solid and mathematically precise understanding of their fundamental capabilities and limitations.
Prerequisites
      CS-150 (Discrete Structures), CS-250 (Algorithms), 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 - Thursdays 10:15-12:00 in PO 01.
     Exercise sessions - Thursdays 12:15-13:00 in PO 01.
Teaching staff
     Lecturer:                            Aleksander Mądry (aleksander.madry@epfl.ch), office hour: Thursday 15:15-16:00 (or by appointment), INJ 113.
     Teaching assistants (TAs): Farah Charab (farah.charab@epfl.ch), office hour: Wednesday 15:15-16:00, INJ 110.
                                                Slobodan Mitrović (slobodan.mitrovic@epfl.ch), office hour: Friday 15:15-16:00, INJ 110.
                                                Ashkan Norouzi Fard (ashkan.norouzifard@epfl.ch), office hour: Monday 15:15-16:00, INJ 110.
Grading
     The grade will be based on three in-class exams during the semester [90%] and weekly problem sets [10%].
     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 (most likely, in fifth, ninth, and thirteenth week). Each exam will be focused on the material that was covered in the corresponding one-third 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 will be used as an additional lecture sessions).
 Problem sets
There will be weekly problem sets with two problems per set, on average.
All solutions should be submitted (via course Moodle) as a PDF.
Here are the guidelines:

Announcements: