TITLE: Never Been Compared to a Barrel of Boiling Oil Before
AUTHOR: Eugene Wallingford
DATE: February 18, 2005 2:20 PM
DESC: In which the author hopes that his students don't choose their seats in class in order to be able to weep uncontrollable at their classroom experience with minimal embarrassment.
-----
BODY:
I hope that my Algorithms course doesn't have
this kind of reputation
among our students!
Teaching Algorithms is a challenge different from
my other courses, which tend to be oriented toward
programming and languages. It requires a mixture
of design and analysis, and the abstractness of
the design combines with the theory in the analysis
to put many students off. I try to counter this
tendency by opening most class sessions with a
game or puzzle that students can play. I hope
that this will relax students, let them ease into
the session, and help them make connections from
abstract ideas to concrete experiences they had
while playing.
Some of my favorite puzzles and games require
analysis that stretches even the best students.
For example, in the last few sessions, we've
taken a few minutes each day to consider a
puzzle that
David Ginat
has called Election. This is my formulation:
An election is held. For each office, we are
given the number of candidates, *c*, and
a text file containing a list of *v* votes.
Each vote consists of the candidate's number on
the ballot, from 1 to *c*. *v*
and *c* are so large that we can't use
naive, brute-force algorithms to process the
input.
Design an algorithm to determine if there is a
candidate with a majority of the votes. Minimize
the space consumed by the algorithm, while making
as few passes through the list of votes as possible.

We have whittled complexity down to O(log *c*)
space and two passes through the votes. Next class
period, we will see if we can do even better!
I figure that students should have an opportunity
to touch greatness
regularly. How else will they become excited
by the beauty and possibilities of an area that
to many of them looks like "just math"?
-----