Introduction to the Theory of Computation

Instructor: Chih-Jen Lin, Room 413, CSIE building.
TA: Cho-Jui Hsieh (r96048@csie) and Fang-Lan Huang (d93011@csie)
Your HW scores. See the important announcement about your final exam below.
We heard some complaints about the 4th question. Hence, we decide to reweight the fourth question to be 15 points. Your new score of that problem will be min(current+10, 25). Please come to lab 528 by Wed noon if you are affected.
Time: Monday 10am to 1pm.
We have a 20-minute break at around 11:30am.
This course will be taught in English. We will use the blackboard. You are assumed to take notes.
Textbook: Michael Sipser, Introduction to the Theory of Computation, second edition, Course Technology, 2005.
We will mainly teach Chapters 1-4 and 7.

Course Outline

Automata and Languages
Mathematical models of computation
Computability Theory
Problems CAN and CANNOT be solved by computers
Complexity Theory
Why some problems are hard but some are easy ?

Why taking this course?

Why you are forced to study this theoreticla and maybe boring topic?

From authors of the textbook

Theoretical CS has some fancy/big ideas
Relevant to practice (e.g., modern cryptography)
Abstract way of thinking the computers. Help you to design more beautiful ones

Homework

Once every week. Please write your homework/reports in English. For late homework, the score will be exponentially decreased.

Every week we will randomly select one to present his/her homework. Everyone has to turn in the homework before this presentation. Rules: We do not require you to come every week. If you are absent and are selected for presentation, you will be required to do a presentation next week. If you failed to show up then, your midterm score will be deducted by 15 points. On the other hand, every week we seek for a volunteer first who will get 10 bonus points. When no one volunteers, everyone can be picked no matter you have given a presentation before or not.

We have done this seeting for a few years, so you should be able to do it without problem.

HW1: 0.10, 0.11, 1.3, due October 1, 2007
Hw2: 1.16, 1.31, 1.38, due October 8, 2007
Hw3: 1.17, 1.36, 1.40(b), due October 15, 2007
Hw4: 1.21(b), 1.48, 1.53, due October 22, 2007
Hw5: 1.45, 2.6(b,d), 2.10, due October 29, 2007
Hw6: 2.13, 2.15, 2.27, due November 5, 2007
Hw7: 2.19, 2.20, 2.23, due November 12, 2007
Hw8: 3.2e, 3.12, 3.13, due November 26, 2007
Hw9: 3.14, 3.15(bcde), due December 3, 2007
Hw10: 3.20, 3.21, due December 10, 2007
Hw11: 4.12, 4.15, 4.16, due December 17, 2007
Hw12: 4.22, 4.24, 4.26, due December 24, 2007
Hw13: 7.1(abef), 7.2(abef), due December 31, 2007

Exams

You can bring the textbook and your notes. Anything else is not allowed.

Midterm: November 19, 2007
Final: January 7, 2008
We will discuss the final exam on January 14, 2008.

Grading

50% homework, 50% Exam. (tentative)

10 to 15% may not pass (also tentative).

Last modified: Mon Jan 14 14:00:07 CST 2008