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

From: Chip Klostermeyer (klostermeyer_at_hotmail.com)
Date: 02/21/04 

Date: 20 Feb 2004 16:48:41 -0800

Hi,
  I have been coerced into teaching a Honors course the Fall
(mostly for non-CS freshman/sophomore Honors students). My
idea was to do some Great Ideas/Problems/Puzzles etc. from
computer science -- emphasis on theory/algorithms
and related areas like graph theory/combinatorics.
Of course, the honors college wants a syllabus in one week!
  I looked at the book, "Great Ideas in CS" and though a nice
book, seems a bit light on the theory side ... given that
I want to focus on theory to keep me interested. I saw the
course/web site at CMU "Great Ideas in Theoretical Computer Science"
and may use that as a guide for some of the course. Examples
of some things I might discuss (besides a couple weeks on
basics/definitions/history) include Towers of Hanoi, Byzantine
Generals, voting problems, maybe a gentle discussion
of interactive proofs, prisoner's dilemma, game of life, primality
testing, graph coloring ... anything that can be discussed in a
day or so to folks with no CS background, yet which has some
theory component to it ... stuff that is surprising or counter-intuitive
is all the better ;)
  Anyway, if anyone has any suggestions for material/topics
that I might cover, I would most appreciate it. Any pointers
to references to articles (e.g., from Scientific American) that
would be accessible to students would be great (I have a couple)
would be great.

Thanks in advance. If I get enough interest, I will post a syllabus
(or a link to one) to comp.theory in a week or so.

Chip Klostermeyer