This course covers a number of fundamental concepts in the theory of computation, which are essential to computer scientists and to many application areas of computer science, e.g., programming languages, compiler construction, natural language and speech processing, image compression and generation, and theory of concurrency. In this course, we study regular languages, context-free languages, and recursively enumerable languages. We study the abstract machines: finite automata, pushdown automata, and Turing machines, as well as grammars that accept or generate those languages. We also study the basic computability theory, i.e., what can and what cannot be done by computation.
There will be four assignments in this course. Assignments will be graded according to their correctness, preciseness, and elegance. Each assignment weighs 10% of the course grade.
All assignments are to be handed in to the Computer Science 3331 assignment locker or to the instructor directly. All assignments are due by 10pm of the due date. Late assignments will be accepted for up to five days after the due date, with weekends (Saturday and Sunday) counting as a single day; the late penalty is 2^n%, where n is the number of days late.
There will be a midterm test and a final exam. The midterm test is scheduled for Wednesday, October 26 at 7:00-9:00pm in SH 2316. The final exam has been scheduled for December 11 at 7:00pm-10:00pm in TH 3101. Midterm test weighs 25% of the course grade and final exam 35%.