Instructor: Donald
Loveland
Location: D212 LSRC
Office Hours: Tues. 2p.m. - 3p.m., Friday 1:30
- 2:30p.m.
Or by appointment.
TA:
Yusu Wang
Location: D208 LSRC
Office Hours: Mon. 1:20p.m. - 2:20p. m., Thurs.
3p.m. - 4p.m.
Course Location: 116 Old Chem
Course Meeting Time: MWF 10:30 - 11:20a.m.
Prerequisites:
CPS100 or CPS100E, and MTH 103
Synopsis of course content:
An introduction to important formal languages and
the abstract
machines that recognize (process) the languages. The languages
include the languages for finite automata, the context-free
languages used in describing computer languages (and useful for
natural languages), and the recursively enumerable languages and the
related Turing machines. Finite automata are used for everything
from specifying traffic light systems to describing computer chips.
The study of Turing machines addresses the very limits of
computation. (There are limits; there are noncomputable tasks.)
We conclude with a brief introduction to computational complexity
issues at the most fundamental level.
Textbook:
Elements of the Theory of Computation,
Lewis and Papadimitriou (2nd Edition). Prentice-Hall, 1998.
Lecture Notes & Assignments:(click here)
Grading :
Homework
40%
Exam 1
15%
Exam 2
15%
Final Exam
30%
Note:
There will be opportunity for extra credit for
solving more
difficult problems.