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"? -----