15-211 review questions

I wrote an outline of the topics we've seen so that you can see where you feel weakest.

Problems

• 15-211 topics
• Questions for 16 Oct 1997: Mergesort, quicksort, heapsort, priority queues
• Questions for 23 Oct 1997: Recurrences, bucket and radix sort, hashing, game playing, destructors
• Questions for 5 Nov 1997: 2-3 trees, AVL trees, tries, more recurrences
• Questions for 11 Nov 1997: Graphs, modeling, planarity, depth-first and breadth-first search
• Questions for 19 Nov 1997: Priority-first search, minimum spanning trees, all-pairs shortest paths, minimum matching, transitive closure
• Questions for 2 Dec 1997: Finite automata, Knuth-Morris-Pratt string matching, regular languages
• Questions for 4 Dec 1997: Invariants, running time analysis, memoization, lists, stacks and queues, trees
• Questions for 9 Dec 1997: Finite automata, recurrences

About the problems

If your answer differs from mine: It may be that your answer is right too. And, although I haven't yet absolutely confirmed that I'm mortal (get back to me in eighty years), I occassionally err. So, if your answer isn't mine, ask me about it. I'll be happy to confirm whether you're correct and to tell you that my answer is better. (Or to correct myself; I really haven't checked my answers very well.)

If a question puzzles you: Don't hesitate to visit my office (4617 Wean Hall) or to e-mail me. My regular office hours are Friday 9-10; but really you can try stopping by any time you find convenient. I will be very happy to discuss these problems; it is no coincidence that I'm posting these the day before my scheduled office hour.

About the difficulty level: My questions tend to range in difficulty from the easiest you'll find in our class, to harder that anything you should expect on a quiz, to the downright challenging. All the questions are worthwhile. If you're comfortable with all the questions (except maybe the challenge problems), you'll be doing very well.

Challenge problems: Occassionally I stumble on questions that are slightly beyond the expected aptitude of 211 students but just too neat to skip. These are indicated by the heading of Challenge problem. You should not feel that you don't understand if you can't get the answer to one of these, but they're worth considering.

Sources: I've made up most of these questions and answers on my own. Some are questions from recitation notes that I skipped due to lack of time. I also draw from Cormen, Leiserson, and Rivest's Introduction to Algorithms. (I think this is what CMU uses in its undergraduate Algorithms course.) I may occassionally draw from Standish, but not too often, both because you can read the textbook as well as I and because few of Standish's questions and exercises seem to involve the higher-level thinking skills we expect. I've tried to credit the sources when known.