Introduction to the Theory of Computation
- Instructor:
Chih-Jen Lin, Room 413, CSIE building.
- TA: (You may find them in lab 528)
Your
HW scores.
- Time: Class A: Tuesday 9:10am to 12pm.
Class B: Thursday 9:10am to 12pm.
We have a 20-minute break at around 10:30am,
so we finish at 12pm.
-
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.
-
No course on December 30, 2008 and January 1, 2009
-
FAQ of this course is here
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 two weeks. Please write your homework/reports in English.
For late homework, the score will be exponentially decreased. See
FAQ about how to submit your
homework.
- HW1: 0.11, 1.3, 1.36, 1.37, due on September 30
or October 2, 2008 according to your class.
- HW2: 1.16, 1.21, 1.38, 1.41, due on the day of the 1st midterm.
- HW3: 1.46(d), 1.53, 1.55(g), 1.61, due on Nov 4 or 6.
- HW4: 2.14, 2.15, 2.26, due on Nov 18 or 20.
HW5: 2.28, 3.12, 3.15, due on on the day of the 2nd midterm (Dec. 4)
Exams
To have the same set of exam questions,
two classes will have exams at the same
time. So we will do them in the evening.
You can bring the textbook and your notes.
Anything else is not allowed.
- Midterm 1: October 16, 6:30-8pm, 2008 (no lectures that week). We will use rooms 101, 102, and 105. Materials before pumping lemma are covered (i.e., pumping lemma is not included).
- Midterm 2: December 4, 6:30-8pm, 2008 (no lectures that week)
- Final: January 15, 6:30pm-8pm, 2009 (no lectures that week)
For midterms, discussions will be in the following week (regular lecture time of each class). For the Final exam, it will be on January 16, 5pm. See the faq page for more details.
Grading
30% homework, 70% Exam. (tentative)
We calculate raw scores first.
We then adjust them to final scores so
that some fail and some pass.
Around 10 to 15% may not pass (tentative).
Last modified: Sun Nov 16 10:10:39 CST 2008