CS-251 Theory of Computation -- Spring 2017

Course description
This course constitutes an introduction to theory of computation and basics of complexity theory. It discusses the basic theoretical models of computing (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.
Textbook

In the course we will closely follow the book "Introduction to the Theory of Computation" by Michael Sipser.

Time and place
     Lectures - Thursdays 8:15-10:00 in CM2.
     Exercise sessions - Thursdays 10:15-12:00 in CM1221 and CM5.

Teaching staff
     Lecturer:                            Nisheeth Vishnoi email for appointment, INJ 135.
     Teaching assistants (TAs): Naman Goel Office Hours: Monday 6pm - 7pm, INR212
                                                Daniyar Chumbalov Office Hours: Tuesday 5pm - 6pm
                                                Buddhima Gamlath Office Hours: Tuesday 6pm - 7pm, INJ 110
                                                Lionel Parreaux Office Hours: Friday 4pm - 5pm, BC 247
                                                Damian Straszak Office Hours: Wednesday 8am - 9am, INJ 116



Contact Information
The instructor and TA will post announcements, clarifications etc. on the moodle. All important announcements will be posted to the course web-page and the moodle. However, most discussions will be restricted to moodle. Please set your notification preferences on moodle accordingly. If you have a straightforward clarification question, your best option is to post a message on moodle. There is a good chance that this will be answered by your classmates or the TA or the instructor, very quickly. Please do not post any solutions or obvious hints to the homework questions on moodle.
If your question is personal you should send a private message to the instructor or TA through moodle. Please use email as a last resort. Please only send emails regarding questions that cannot be satisfactorily handled in office hours or on moodle. Please allow either the TA or the instructor at least 48 hours for an email response.

Grading
     The grade will be based on three in-class exams during the semester and homeworks.
     Class participation (e.g., attending exercise sessions, interaction during the lecture, asking good questions) can also (positively) influence your grade.
     More on: Exams

Exam 1: March 16, 2017
Exam 2: April 13, 2017
Exam 3: June 01, 2017

The location will be confirmed one week in advance. The exams are closed book, no handwritten notes, no printouts.

Regrading Policies:
Regrading of homeworks or exams will only be undertaken in cases where you believe there has been a genuine error or misunderstanding. Bear in mind that our primary aim in grading is consistency, so that all students are treated the same; for this reason, we will not adjust the score of one student on an issue of partial credit unless the score allocated clearly deviates from the grading policy we adopted for that problem. If you wish to request a regrading of a homework or exam, you must return it to the instructor or the TA with a written note on a separate piece of paper explaining the problem. The entire assignment may be regraded, so be sure to check the solutions to confirm that your overall score will go up after regrading. All such requests must be received within one week from the date on which the homework or exam was made available for return.

Problem Sets
Every week or so a problem set will be provided. Their purpose is to help students in understanding current material and prepare for the exams. They will also contribute to the final grade.
More on: Problem sets

Here are the guidelines:

Writing: Please be precise, concise 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 solution that is hard/impossible to decipher/follow might not get full credit (even if it is in principle correct).
You do not need to reprove anything that was shown in the class - just state clearly what was proved and where.

Collaboration: These problem set are meant to be worked on in study groups of 3-5 students. Please submit only one writeup per team - it should contain the names of all the students. You may use books or online resources to help solve homework problems, but you must credit all such sources in your writeup and you must never copy material verbatim. 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.

Submission: Solutions to homeworks would be typically due on the following Thursday at 8.15am before the class. You can either bring your solutions to the lecture or submit them via moodle (only one student per team should submit). Typing your solutions using a typesetting system such as Latex is strongly encouraged! If you must handwrite your solutions, write cleanly. Messy and unreadable homeworks will not be graded. No late homeworks will be accepted.

Warning: Your attention is drawn to the EPFL policy on academic dishonesty. In particular, you should be aware that copying solutions, in whole or in part, from other students in the class or any other source without acknowledgment constitutes cheating. Any student found to be cheating risks automatically failing the class and being referred to the appropriate office.

Course Moodle
It is mandatory to subscribe to the course moodle. All course related questions should be raised there.