CSC280, Spring 2014: Computer Models and Limitations
Instructor:
Prof. Lane A. Hemaspaandra
TAs:
Dan Hassin,
Mark Mullock,
and
Xing Yan.
Workshop Leaders:
Julian Lunger and
Samantha Piccone.
The Course Catalog Description: (The school is
in the process of updating this course's
description in the course catalog; the blurb below is
a more up-to-date one than the one in the course catalog.)
This course studies
fundamental computer models and their computational
limitations. Finite-state machines and pumping lemmas, the
context-free languages, Turing machines, decidable and
Turing-recognizable languages, undecidability.
Textbook:
Introduction to the Theory of Computation, Michael Sipser,
(the rather new) third edition, 2012.
Be careful
not to accidentally get the first or second edition.
Note that we will be using
the (standard, USA-version)
third edition, not the "international" edition;
in the international edition apparently
some problem numbering differs, so if you use the international
third edition (which you might get if you
buy a used one, so be careful), you
may
do the wrong problems
(and so will end up with 0's as you'll
have done the wrong problems).
(And no, I don't work for the publisher;
all my books are published by Springer.)
The ISBN of the US edition (the international edition
has slightly different ISBNs) is listed by the publisher as:
ISBN-10: 113318779X and ISBN-13: 9781133187790.
On the other hand,
the right book is also on reserve in the library, though you will be using
it very, very often (you may find it
comforting to sleep with it under your pillow!).
Prerequisites (very important): CSC173 and MTH 150.
Course Information Document/Syllabus:
syllabus (version, V. 1.3.2, last updated 2014/3/26).
Other
Important
Links:
Some of My Favorite Bits of Science Wisdom:
-
After solving a challenging problem, I solve it again from scratch,
retracing only the *insight* of the earlier solution. I repeat this
until the solution is as clear and direct as I can hope for. Then I
look for a general rule for attacking similar problems, that *would*
have led me to approach the given problem in the most efficient way
the first time. -- Robert Floyd
-
In computer science, elegance is not a dispensable luxury, but a
matter of life and death. -- Edsger Dijkstra
-
Imagination is more important than knowledge. -- Albert Einstein
-
They are ill discoverers that think there is no land, when they can see
nothing but sea. -- Francis Bacon
Other Odds and Ends (Mostly Quotations):
-
I don't believe it. Prove it, and I still won't believe it.
--Life, the Universe and Everything
-
It was mentioned on CNN that the new prime number discovered
recently is four times bigger then the previous record.
-
Sooner or later society will realize that certain kinds of hard work
are in fact admirable even though they are more fun than just about
anything else. -- Donald E. Knuth
-
Getting tenure doesn't really change anything.
However, not getting tenure changes everything.
-
My late friend Stan Ulam used to remark that his life was sharply
divided into two halves. In the first half, he was always the
youngest person in the group; in the second half, he was always the
oldest. There was no transitional period.
-- Gian-Carlo Rota, "Indiscrete Thoughts"
-
Fools ignore complexity. Pragmatists suffer it. Some
can avoid it. Geniuses remove it.
-- Alan Perlis, Epigrams in Programming
-
More Quotes from Dijkstra:
* None of the programs in this monograph, needless to say, has been tested on a machine. (From "A Discipline of Programming.")
* Computer science is not about computers, any more than astronomy is about telescopes.
* The question of whether computers can think is just like the question of whether submarines can swim.
-
"Supposing a tree fell down, Pooh, and we were underneath it?" [said Piglet.]
"Supposing it didn't," said Pooh after careful thought.
Page Maintained by: Lane A. Hemaspaandra