Theoretical Computer Science (Spring 2009)
Course Schedule
Lectures:
Tuesdays 10:15 - 12:00,
lecture room CM 1
Tom Henzinger,
office BC 350
Exercise Sessions:
Tuesdays 12:15 - 13:00
| Session leader |
Language |
Session room |
Office |
Office hours |
| Grégory Théoduloz |
French |
CM 4 |
BC 345
|
Monday 14-16 |
| Dejan Nickovic |
French |
CM 1120 |
BC 347
|
Monday 10-12 |
| Tatjana Petrov |
English |
CM 1121 |
BC 344
|
Friday 10-12 |
The staff is always glad to help you.
Whenever you get lost, desire help, or just want to talk, please see
your session leader --don't let yourself fall behind!
If you can't come to one of our office hours, send us email to set up
an individual appointment.
To help you with the exam preparation, the teaching
assistants are organizing a revision session the week before the
exam. During this session, you will be to able ask questions about the
material and we will discuss example problems.
The session is taking place
in INR 113
on Thursday, June 11, 10:00-12:00 and 13:30-17:00.
In the morning, we plan to cover topics related to regular and
context-free languages, and in the afternoon, we plan to cover topics
related to Turing machines, decidability and complexity.
Calendar:
| First lecture: |
2009-02-17 |
| Quiz 1: |
2009-03-03 (Solution) |
| Quiz 2: |
2009-03-17 (Solution) |
| Quiz 3: |
2009-03-31 (Solution) |
| Quiz 4: |
2009-04-21 (Solution) |
| Quiz 5: |
2009-05-05 (Solution) |
| Quiz 6: |
2009-05-19 (Solution) |
| Last lecture: |
2009-05-26 |
| Final exam: |
2009-06-16 14:15-18:00 in SG1 |
Homework:
Course Information
Prerequisites:
Discrete Mathematics and Algorithms
Summary:
The course presents some of the most fundamental results in theoretical
computer science.
These results attempt to answer, in a precise mathematical sense, the
following two questions, which are of obvious practical as well as
philosophical interest:
- Can a given problem be solved by computation?
- How efficiently can a given problem be solved by computation?
Thus, we focus on problems rather than on specific algorithms
for solving problems.
To answer both questions mathematically, we need to start by formalizing
the notion of "computer" or "machine".
So the course outline breaks naturally into three parts:
- Models of computation (Automata Theory)
- Finite automata
- Pushdown automata
- Turing machines
- What can we compute? (Computability Theory)
- How efficient can we compute? (Complexity Theory)
Textbook:
You should definitely purchase the following book, which is available
in the campus bookstore:
- Michael Sipser,
Introduction to the Theory of Computation.
Second (International) Edition, Thomson Course Technology, 2005.
ISBN 0-619-21764-2.
Web-site.
In addition, you may find the following books useful.
They are available in the library.
- Michael R. Garey and David S. Johnson,
Computers and Intractability: A Guide to the Theory of
NP-Completeness.
Freeman, 1979.
- John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman,
Introduction to Automata Theory, Languages, and Computation.
Second Edition, Addison-Wesley, 2001.
Web-site.
- Dexter C. Kozen,
Automata and Computability.
Springer, 1997.
Finally, we recommend the following book written in french.
- Pierre Wolper,
Introduction à la Calculabilité:
Cours et Exercices Corrigés.
2e Edition, Dunod, 2001.
ISBN 2-10-004853-8.
Lectures:
You are expected to be familiar with all the material covered in the
lectures and in the specified sections of the textbook.
Attending lectures is highly advisable, because some of the lectures
will be drawn from material not in the text, and you will be responsible
for this material.
Exercise Sessions:
Participation in discussion sessions is optional but advisable.
During exercise sessions, previous and new homework problems will
be discussed, and examples will be presented which aid in the
understanding of the lecture material.
Exercise sessions are also an excellent time to ask questions about
the course material and about homework problems.
Exercise sessions are not the place to work out homework solutions,
unless you are so instructed by the session leader.
Homework:
A problem set is handed out each Tuesday and is due at the beginning of
the exercise session on the following Tuesday.
If you cannot attend a exercise session, you may turn in your
homework to your session leader's office before noon on the due date.
Model solutions are handed out and discussed during the exercise
sessions on the due date.
We will check all homework that is turned in by the due date
in order to give you feedback.
The checked problem sets will be returned a week later also during
the exercise sessions.
Problem sets that are not picked up in the exercise sessions
will be kept in the session leader's office.
Homework will not be graded, but if at the end of the course,
your performance is borderline between two grades, we may take
your homework into account to determine your course grade.
It is extremely important that you continuously stay on top of the
material, because every new topic builds on previous results.
Doing all homework is an excellent way to achieve this.
If you don't understand the material at the beginning, it will be
difficult to catch up later.
If you have questions about course material or homework problems,
please talk to the course staff as soon as possible.
We are more than happy to help you, during office hours and at any
other time.
Newsgroup:
We will monitor the following newsgroup for questions:
http://ditwww.epfl.ch/usenet
or
news:epfl.ic.cours.tcs
Quizzes:
There will be six 15 minute quizzes at the beginning of the exercise
sessions at the dates given above.
Each quiz will focus on the most recent material.
No notes or books are allowed at the quizzes.
Your best four performances on the six quizzes will count towards your
course grade.
We will automatically drop your two lowest quiz scores.
Since you can miss two quizzes without penalty, no excuses for missed
quizzes will be accepted, and missed quizzes cannot be made up for.
Final Exam:
The final exam will take place during the regularly scheduled exam
period.
You will be allowed to bring one A4-size sheet of hand-written notes
to the exam.
No other material is allowed.
Grading:
Your course grade will be based on your quiz and final exam scores.
Each quiz will count for 10% of the course grade, for a total of 40%,
and the final exam will count for 60% of the course grade.
Course Outline
- Lecture 1 (2009-02-17):
- Motivation and course outline
- Finite automata
(Handout 1)
- Boolean operations on finite automata
(Handout 2)
- Lecture 2 (2009-02-24)
- Lecture 3 (2009-03-03)
- From regular expressions to finite automata and back
- Regular pumping lemma
(Handout 5)
- Lecture 4 (2009-03-10)
- Push-down automata
(Handout 6)
- Context-free grammars
- Lecture 5 (2009-03-17)
- From context-free grammars to push-down automata and back
- Context-free pumping lemma
(Handout 7)
- Lecture 6 (2009-03-24)
- Lecture 7 (2009-03-31)
- From problems to languages
- Boolean operations on Turing machines
(Handout 10)
- Lecture 8 (2009-04-07)
- Robustness of Turing machines
- Nondeterminism in Turing machines
- Lecture 9 (2009-04-21)
- Lecture 10 (2009-04-28)
- Lecture 11 (2009-05-05)
- Lecture 12 (2009-05-12)
- Variants of SAT
- Variants of CLIQUE
- Variants of HAMPATH
- Variants of SUBSETSUM
- Lecture 13 (2009-05-19)
- Reduction from SAT to CLIQUE
- Reduction from SAT to HAMPATH
- Reduction from SAT to SUBSETSUM
- Lecture 14 (2009-05-26)
- NP-hardness of SAT
- Beyond NP
Update now
