This is summary of the material to study for the test on October 31.

1. Review all the written homework assignments:
   1. Assignment 1.
   2. Assignment 2.
   3. Assignment 3.
   4. Assignment 4.
   5. Assignment 5.
2. Use Kruskal's algorithm to find a minimum spanning tree for the weighted graph representing towns on the island of Molokai. Show all the steps, including the use of path compression.
3. Give a short definition of each of the following algorithms.
   1. Mergesort.
   2. Polyphase mergesort.
   3. Binary Search.
4. Find a world wide web page that gives the frequency, in English text, of all 26 letters of the alphabet. (I found such a web page in less than 5 seconds.) Construct an optimal prefix-free code for this alphabet, using Huffman's algorithm.
5. Give a definition of Dijkstra's Algorithm, as defined in class, or on pages 198-202 of your textbook. Your definition should contain the following parts:
   1. The problem to be solved.
   2. The conditions on the graph which are needed for Dijkstra's algorithm.
   3. The abstract data structures needed.
   4. A description of the implementations of those abstract data structures.
   5. A definition of the algorithm itself, in concise form.
   6. An analysis of the time complexity of the algorithm.
   In total, this answer should not be more than 2 handwritten pages long. If longer, you are probably writing too much.
6. There is a well-known sliding block puzzle which appeared in a recent issue of Science News. You can actually try to work the web version. Explain in one paragraph how you would design an algorithm to find a solution to this problem (actually a class of problems). Your answer should be very high level and general, and should not be dependent on any specific feature of that particular puzzle, but should apply equally well to any sliding block puzzle. If your answer is more than a third of a page long you are writing too much.
7. Problem 7.35 on page 256 of your textbook.
8. Problem 8.28 on page 281 of your textbook.
9. Problem 8.32 on page 281 of your textbook.
10. Pattern matching and finding subsequences.