CS 280 Instructor Page
Course Name: Computer Models and Limitations
Instructor: 
Prof. Lane A. Hemaspaandra
Graduate TA: 
Scott Ames
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
formal tractability.
Textbook: 
Introduction to the Theory of Computation, Michael Sipser,  
(the brand new) third edition, 2012.  
Be careful
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).
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