CS 280 Instructor Page
Course Name: Computer Models and Limitations
Prof. Lane A. Hemaspaandra
The Course Catalog Description: This course studies
fundamental computer models and their computational
limitations. Finite-state machines and pumping lemmas, the Chomsky
hierarchy, Turing machines and algorithmic universality,
noncomputability and undecidability, tradeoffs between power and
Introduction to the Theory of Computation, Michael Sipser,
(the brand new) third edition, 2012.
not to accidentally get the first or second edition.
Prerequisites (very important): CSC162 OR CSC172 OR MTH172.
Course Information Document/Syllabus:
Here (version 1.15, last updated 2013/4/1/8:36PM).
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