Syllabus for CSC427 Introduction to the Theory of Computation.
General
This is a first course in the theory of computation. The course is of a generally
mathematical nature, however it requires no calculus, or other "normal" mathematics.
It explores what is computation. This is presented by way of machine models, and
also linguistic models.
- The assigned textbook is
Introduction
to the Theory of Computer, Third Edition by Mike Sipser.
-
Please follow us on twitter/csc_517 (same as 317 twitter feed)
-
Some course notes will be found on the Csc427 blog.
-
The course assigns weekly problem sets, due on Wednesdays. It is very
important to do the homeworks.
-
There maybe reading assignments from texts other than the class text.
-
Our grader is Parul Maheshwari, p.maheshwari _at_ umiami.edu.
-
No late homeworks accepted after the last day of classes.
-
Midterm: Monday, TBA.
-
The final will be in MM 200, Wednesday, April 29, 11:00am — 1:30pm.
-
Grades are 40% final, 30% midterm, and 30% homework.
Writing Credit
Three essays, each at least 1500 words. Some possible topics/books are (for books,
read and report):
- The origin of algorithms. A historical paper.
There is actually a book, History
of Algorithms ... that might guide you.
- The origins of computation theory. There is a nice book by Matiyasevich and Martin
Davis called "Hilbert's 10th Problem".
- G Spencer Browns, "The Laws of Form". This book seems to be very updated since I
read it.
-
The need to break military codes drove forward the construction
of computers during World War II.
Among the early computers were
the Colossus
designed by Tommy
Flowers, to break German Navel Codes (Tunny)
and Turing's Bomb,
to break army and high command codes (Enigma).
These were really the first computers ever built.
- A science fiction short story about algorithms, computers, etc.
If not original, you can do an analysis of some Sci-Fi books like
The Diamond Age, or Snow Crash.
- I've recently been reading Norbert Wiener's "The Human Use of Human Beings", and
that might be of interest to some of you.
- Yardley's "American Black Chamber" is another interesting book about the start
of America's secret interception, code breaking activities.
- The
Theory of Numbers by Richard Dedekind. A math book about what a real number means. It's
here because this was the start of the questions that lead to the need to think more about
the nature of proof, language and computation.
Please write me with your proposed topics, if you elect writing
credit. One paper must be done before the midterm, and the other
two before reading days.
