CSC 8150-001 Theory of Computing
Wednesdays from 6:15pm to 8:45pm in Mendel 260
Dr. David Matuszek, Mendel 162C, (610) 519-5654
Purpose
This course is highly theoretical, in that it delves into mathematical models of computers
and examines the limits of what can and cannot be computed. But "theoretical" is
not equivalent to "useless": many of the mathematical models are directly
relevant to day-to-day programming problems, such as overall system design, processing
structured input, describing new programming languages, and performing complex searches.
Language theory is fundamental to all modern compiler construction. In addition, knowledge
of complexity theory is often useful in determining when a given programming task is
infeasible or even impossible.
The emphasis throughout the course will be not only on conveying the fundamental ideas of the theory of computation, but also on demonstrating practical applications of the theory.
Textbook
The textbook for the course is Introduction to the Theory of Computation, Michael
Sipser, ISBN 0-534-94728-X. We will cover all of chapters 0 (Introduction), 1, 2, 3, 4,
and 7, and selected topics from the remaining chapters.
There is considerable overlap with a course I taught a couple of years ago, CSC 4170, for which I have extensive CSC 4170 lecture notes at http://www.netaxs.com/people/nerp/automata/syllabus.html. This course will have more material and will cover a wider range of topics, but we will begin in the same place. I hope you find these earlier pages useful.
For those of you that can run Java, I have put the following programs online:
|
Additional links:
Extra credit
If you did badly on the midterm (70 or less), you may if you wish take an additional take-home exam. Your grade on this exam will be averaged with your grade on the regular midterm exam.
If you did not do badly on the midterm, but you want to do the take-home exam anyway, I am willing to reduce your midterm exam grade to 60 and average it with the grade on the take-home exam.