Fudan School of Computer Science Software School IIPL Theory Group Key Development Course (精品课程) -->

Outline

This course is an introduction into the theory of computing. We will learn the fundamental language classes (regular, context-free grammar, general grammar) and their corresponding machine models (finite automata, pushdown automata, Turing machine). We will also discuss problems that are undecidable in these models. Finally, we will study complexity issues like NP-completeness.

The course is divided into four major topics. First we introduce a simple computing model, the finite automata, and characterize the languages that can be decided by these machines, the regular languages. Then we study the more powerful pushdown automata and their corresponding languages, the context-free languages. Finally, we will discuss Turing machines, the most powerful machine model. But we will also see the limitations of this model; not all problems can be solved by a Turing machine. At the end, we will discuss efficiency of Turing machines, mainly in the forrm of lower bounds, i.e., the theory of NP-completeness.

1. Finite automata and regular languages

We will introduce a simple machine model, the finite automaton (FA), and study its computational power. We will show that deterministic and non-deterministic FA can decide exactly the same class of languages, the regular languages. Regular languages are closed under all set operations. We will learn algorithms to transform a non-determinisitcd FA into a deterministic FA, to minimize the size of a deterministic FA, and to construct the regular language corresponding to a FA (and vice versa). We will also learn powerful methods to prove non-regularity of a language, for example, the Pumping Lemma.

2. Pushdown automata and context-free languages

A pushdown automaton (PDA) is a FA with an additional stack to store information. Non-deterministic PDAs can decide context-free languages (CFL), i.e., languages that can be described by a context-free grammar (CFG). CFL are only closed under some set operations. While most problems for FA are computable, some problems for CFG are undecidable. We will see that we can parse context-free languages efficiently. We will also learn powerful methods to prove non-context-freeness of a language, for example, the Pumping Lemma.

3. Turing machines

A Turing machine (TM) is a FA with a memory tape. It is the most powerful machine model known, but still there are problems that cannot be decided by a TM, for example the Halting Problem. We will learn Rice's Theorem, a powerful tool to prove undecidability. There are many equivalent definitions of languages decidable by TMs, for example general grammars, Post correspondence systems, lambda calculus, etc.

4. Complexity theory

In complexity theory we are interested in classifying languages according to the efficiency of deciding them. P (polynomial time) and NP (non-deterministic polynomial time) are the most prominent classes, and we will study complete problems (the most difficult problems in a class) for NP and PSPACE. We will also shortly mention the concept of Kolmogorov complexity which classifies languages according to the size of their most succinct representation.

Textbook

This course will closely follow the textbook Introduction to the Theory of Computation by Michael Sipser, 2nd edition (English), China Machine Press, 2002. It is mandatory that you have a copy of that book.

In class, I may sometimes teach material that is not in the textbook. I may also skip some material in the textbook. For the exams, however, I expect that you are familiar with everything we did in class, everything covered by the textbook (except some parts that will be explicitly excluded), and everything that appeared in the homework assignments.

Usually, I will not provide any notes in addition to what you find in the textbook. Below, I will provide links to some nice resources when we encounter them.

FOLDOC On-Line Dictionary of Computing
DADS Dictionary of Algorithms and Data Structures
Introduction Slides from first class on Mar 4
History of computing Slides from Mar 4
The infinity paradox Discussed on Mar 4
Stephen Cole Kleene History of the Kleene star, Mar 11
Kara the ladybug A programmable finite automaton (see also the original version at ETH and the download page for different Java versions); choose JavaKara on the main menu
Exorciser An exercise tool for finite automata (see also the original version at ETH)
Pattern matching with DFA Explanations and visualizations
Pitfalls of the Pumping Lemma Not my notes
State minimization My own notes
History of automata Slides from April 2
DFAs and PDAs Highlights
Alternative models of computing Lambda Calculus and Billiard ball computer
Conway's Game of Life Game of Life, collection of Game of Life links, Jason's Life Page, and a Turing machine implemented in Game of Life
self.cA self-replicating C program.
chaos.cA chaotic self-printing C program.

Just-In-Time Teaching

This course will be different from most courses you have experienced so far at Fudan. It will be a reading course, which means that you must read the material covered in a lecture before you come to class. You should work in teams (see below). Your team must also send me an email every week (before Thursday 8pm) with some problem you encountered in your class preparation.

Classes will always start with a short quiz to test whether you are well prepared. Then, instead of covering all the material step by step, we will skip the more boring easy parts (like simple definitions) and instead spend more time discussing difficult concepts or proofs. If you come to class unprepared, you may have difficulties with the quiz and may not be able to follow the lecture.

This teaching method is called Just-in-Time Teaching (JiTT) and is advocated, for example, by Eric Mazur at Harvard University. JiTT is part of the Interactive Learning Toolkit. You can also watch Prof Mazur explain these concepts in his own class (skip the first ten minutes of the video...).

Schedule

Here is the reading schedule for your class preparation. Minor adjustments during the course are possible. It might be helpful to check the webpage with typographical errors of the textbook.

The pages and section numbers refer to our textbook (2nd edition), for a few topics there are also some notes of my own. The Objectives should guide you in your learning. The FAQs are a list of your class preparation questions together with my answers. The Quiz column contains the class quizzes. The last column contains the homework assignments.

Week/Date Pages Section/Topic Obj. FAQ Quiz Ass.
1: Mar 4 1-41 0-Ex 1.17: Course introduction, Basic definitions, DFA Obj. 1 no FAQ no quiz A1
2: Mar 11 42-63 Ex 1.17-1.2: NFA, NFA=DFA, closure properties Obj. 2 faq2 Q2 A2
3: Mar 18 63-82 1.3-1.4: Regular expressions, Pumping Lemma Obj. 3 faq3 Q3 A3
4: Mar 25 101-111 State minimization and 2.1: CFG Obj. 4 faq4 Q4 A4
5: Apr 1 111-129 2.2-2.3: CFG=PDA, PDA, Pumping Lemma Obj. 5 faq5 Q5 A5
6: Apr 8 137-175 3.1-4.1: TM, Church-Turing, decidable languages Obj. 6 faq6 Q6 A6
7: Apr 15 Midterm exam 9 am, Room Z2102
8: Apr 22 175-202 4.2-5.1: Halting problem, undecidable languages Obj. 8 faq8 Q8 A8
9: Apr 29 203-214 5.2-5.3: Post Correspondence Problem, reductions Obj. 9 faq9 Q9 A9
10: May 6 221-235 6.1-6.2: Recursion Theorem Obj. 10 faq10 Q10 A10
11: May 13 No class
12: May 20 No class
13: May 27 236-267 6.3-7.2: Kolmogorov complexity, P Obj. 13 faq13 Q13 A13
14: Jun 3 268-302 7.3-7.5: NP-completeness Obj. 14 faq14 Q14 A14
15: Jun 10 Review no FAQ no quiz
16: Jun 17 Final exam room 2107

Evaluation

Reading Assignments

On the day before each class before 8pm (i.e., every Thursday before 8pm), each team must send me an email, worth 1 point, about one topic in the material you were supposed to prepare for the class that you found difficult to understand (that could be a concept, a definition, a proof, an example, etc.), or "No problems" if you had no problems. This information will help me to focus on your difficulties in my lecture the next day.

Quizzes

Every class will start with a quiz. Usually, there will be six questions (multiple choice). Usually, four questions will cover the material you had to read in the textbook for that day (see the reading schedule), and two questions will review some older material. You must answer at least three questions correctly to get one point, and you must answer at least five questions correctly to get two points.

To foster the team spirit (i.e., strong members helping their weaker teammates preparing the material), one more point is awarded to each team with an average (among all its members present in the classroom) of at least four correct answers. Only the team members present will get the team point.

It may happen during the term that you have a good reason not to be prepared for the quiz. Therefore, you are allowed to skip one quiz without a penalty, but you must inform me by email before class that you want to skip the quiz on a particular day.

Homework Assignments

There will be a weekly homework assignment. Assignments will be available on this page as they become ready. Corrections to the assignments, should any be necessary, will be posted on the course homepage. Some assignments will contain a challenge problem for bonus points. All Assignments have equal weight (even if they have different number of points).

Solving homework problems should help you better understand the course material. Therefore, you will get one point for each problem or subproblem for which you provide some solution attempt, even it is not correct. You get another point if your solution is (approximately) correct. For challenge problems, you can get only one bonus point for correct solution.

Exams

There will be two exams in this course, a midterm and a final exam. You need at least 50% of the points to pass an exam. For each exam you may bring a cheat sheet, i.e., one piece of paper A4 on which you can write whatever you want (it must be handwritten).

Final Grade

All assignments together (reading, homework, quiz) are worth 30% of the final mark. You need at least 50% of the assignment points to pass the course. Each exam counts 35%.

I reserve the right, where appropriate, to adjust raw marks downward in the case of cheating and upward in other situations. The following table shows hows to calculate your final grade from your raw marks.

B+86-90
C+76-80
A100-94
B84-86
C74-76
D50-70
A-90-94
B-80-84
C-70-74
Fail0-50

Policies

Teamwork

In this course you will be working in teams. Prefered team size is three or four students. During the course, students will earn points individually and teams will earn points. Points earned by the team will be credited to each team member.

Each team should have a speaker who is responsible for sending me emails (necessary for some assignments) and in turn distributing my emails to the team members. Your first task will be to form a team. Your first assignment will be for the team speakers to send me the list of the team members (name and student ID). This must happen before Thursday, Mar 10, 8pm. If you can't find a team, please send me email. Students who have not joined a team before the deadline will be randomly combined to form a team.

Collaboration between teams is not allowed and is treated as plagiarism.

Plagiarism

Problem solutions should be your own or your team's common work. If you find a solution somewhere else (old lecture notes, text book, WWW, etc.), clearly acknowledge the source. The standard penalty for cheating on an assignment is as follows: a grade of -100% will be assigned for the piece of work, with a minimum deduction of 5% from the final grade. This penalty applies to the cheater as well as the team that allows its solution being copied.

Late Assignments

Assignments should be handed in class on the due date (Friday). Late assignments are not accepted; zero points are assigned unless there are extenuating circumstances such as serious illness. In such cases, please inform the instructor as soon as possible.

Grade Adjustment

Note that university regulations require that if a student completes an exam, the grade in the course (in particular, a failing grade) will not be changed, even if the student subsequently claims that his/her performance was affected by illness or other personal problems and submits documentation.

Students who fail a course sometimes ask the instructor if they can write another exam or do some extra work in order to raise their mark. We do not offer supplementary exams or other ad-hoc methods of raising marks.