Re: Ideas for course on great ideas in (theoretical) CS?

From: Daniel McLaury (daniel_mcl_at_hotmail.com)
Date: 02/21/04 

Date: 21 Feb 2004 02:53:19 -0800

Turing machines (or post production systems or lambda calculus)
Church-Turing Thesis
The Universal Turing Machine
Halting Problem
Algorithms and Big-O, P vs. NP conjecture.
Information theory, coding theory
Public-Key Encryption
Pseudorandom number generation
Quines

etc.

For theory applicable to the real world, use Knuth. If you're a
mathematician like me and have your doubts that there is such a thing
as a "real world," an excellent intoductory text is "Godel, Escher,
Bach."