CS-251 Theory of Computation -- Spring 2014
Course descriptionThis 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 - "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak. This is an excellent book that covers a whole range of topics in computational complexity. It might be, however, challenging for beginners. A draft of this book is available for free here.
- "The Nature of Computation" by Cris Moore and Stephan Mertens. This position provides a great high-level perspective on the material presented in the course.
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 setsExam 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).
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:
All solutions should be submitted (via course Moodle) as a PDF.
Here are the guidelines:
- These problem set are meant to be worked on in teams of 3-5 students. Please submit only one writeup per team - it should contain the names of all the students. Even though only one writeup is submitted, it is expected that each one of the team members is able to fully explain the solutions if requested to do so.
- Solutions have to be typeset in LaTeX (not scanned, except for figures) and compiled using the provided template. Don't forget to update the relevant information in this template - see the source of the main template file for specific instructions. Please make sure to submit only one file in PDF format (no LaTeX sources). Scanned figures should be imported into the compiled PDF (see, e.g., here for instructions on how to import figures in LaTeX);
- The problem sets will typically be due at 9:30 sharp on the next Thursday after they are released. Late submissions will not be accepted. However, the two problem sets with the lowest score (which might include the missing ones) will be disregarded when computing the final credit for problem sets at the end of the semester;
- You can use any source at your disposal (i.e., Google is your friend), but you have to acknowledge everything that you use and you need to write it up in your own words. (This will not lower your grade.);
- Please be precise and (reasonably) formal. Keep in mind that many of the problems ask you to provide a proof of a statement (as opposed to, say, just to provide an example). Therefore, make sure that your reasoning is correct and there are no holes in it. A clear description of how you tried to solve a problem and failed will always earn partial credit, while a solution that is hard/impossible to decipher/follow might not (even if it is in principle correct).
- Avoid using code in your solutions. A brief plain-text description of an algorithm is much better (as long as, it is sufficiently precise and contains all the important details);
- Please be concise. All the problems have solutions whose all details should comfortably fit on one typeset page. If yours does not, you most likely are overlooking some simplification;
- You do not need to reprove anything that was shown in the class - just state clearly what was proved and where (pointing to specific parts of the lecture notes works best);