for class on Thursday April 27, 2000
Please read Section 3.6 of the Schneider and Gersting text, and be prepared to discuss the following:
We've considered many different problems and algorithms in this course, from picking the cheapest of three shampoo bottles, through searching and sorting, to the Towers of Hanoi and the problem of deciding whether a Turing machine will ever halt. Some of these problems have fast algorithmic solutions; some have exceedingly slow algorithmic solutions; and some cannot be solved by any algorithm. We will put all of these problems into a common framework, and deconstruct the meaning of famous gargoyle on the the side of the Computer Science building.