CS-352 Theoretical Computer Science -- Fall 2014
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. Covered material touches upon: streaming algorithms, spectral graph theory, interactive and zero-knowledge proofs, pseudorandomness, algorithmic game theory, and quantum computing.
The list of topics that we plan to cover includes:
Prerequisites
The list of topics that we plan to cover includes:
- Basics of streaming algorithms;
- Fundamentals of spectral graph theory;
- The power of randomness and interaction (zero-knowledge proofs and PCP theorem)
- Theory of pseudorandomness and one-way functions;
- Introduction to algorithmic game theory;
- Nature-inspired models of computations (quantum computing).
Discrete Mathematics (1st year), Algorithms (2nd year), Theory of Computation (2nd year), 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, slightly challenging for beginners. Electronic version of the book is available here (via EPFL library).
- "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 - Fridays 10:15-12:00 in INR 219.
Exercise sessions - Fridays 12:15-13:00 in INR 219.
Teaching staff
Lecturer: Aleksander Mądry (aleksander.madry@epfl.ch), office hour: Fridays 14:15-15:00, INJ 113 or by appointment.
Teaching assistant (TA): Slobodan Mitrović (slobodan.mitrovic@epfl.ch), office hour: Wednesdays 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 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 might 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 might be used as an additional lecture sessions.)
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.
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 individually;
- 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 due date. Late submissions will not be accepted. However, the problem set with the lowest score (which might correspond to a 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);