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:
Prerequisites
- Theoretical foundations of machine learning;
- Introduction to algorithmic game theory;
- Elements of spectral graph theory;
- Approximation algorithms and inapproximability theory;
- Interactive proofs and computational complexity (PSPACE=IP theorem);
- Basics of quantum computing;
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 - "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. 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 - 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 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 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.
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:
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:
- Please submit your solutions as a one file with the name in the format: X_psetY.pdf, where X is your last name and Y is the numer of the problem set. Don't forget to update the relevant part of the LaTeX template with your name and possibly the name of your collaborator - see the source of the main template file for specific instructions;
- Problem sets that are submitted late (but no later than three days after the deadline) will receive half credit. After that time, no credit will be given;
- Collaboration with one other person is allowed, but: (1) the writeup of all the solutions has to be prepared independently (in particular, you should understand and be able to explain everything that is written in your solution); (2) in your writeup, you should include the name of your collaborator.
- 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 most 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 (including the "Theoretical Computer Science" one) - just state clearly what was proved and where (pointing to specific parts of the lecture notes works best);
Announcements:
- Lecture notes and problem sets can be downloaded via course Moodle. Please make sure to sign up there.
- There will be no exercise session in the first week.