In this course, we explore questions exploring both the power and the
limitations of computers, and concrete strategies for solving
problems using computers.
-
What can a computer do?
-
What can a computer do efficiently?
-
Why are programs hard to test?
-
How can we make computers appear clairvoyant?
-
How do you keep secrets in computers?
-
Why should computers flip coins?
-
When is it a good idea to be greedy?
-
Should tables be sorted?
The answers to these questions involve great ideas whose impact range
from
the philosophical foundations of computation to concrete applications
in everyday life. While many of these ideas are mathematical at their
heart,
we will expose these ideas at a purely intuitive level, without
recourse to grungy mathematics.
Prerequisites
Mathematical maturity (e.g., AP math) and exposure to
computer programming is desirable.
Last updated: September 20, 1998 by
Rajeev Motwani
and
Prabhakar Raghavan