This is summary of the material to study for the test on October 31.
-
Review all the written homework assignments:
-
Assignment 1.
-
Assignment 2.
-
Assignment 3.
-
Assignment 4.
-
Assignment 5.
-
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.
-
Give a short definition of each of the following algorithms.
-
Mergesort.
-
Polyphase mergesort.
-
Binary Search.
-
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.
-
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:
-
The problem to be solved.
-
The conditions on the graph which are needed for Dijkstra's algorithm.
-
The abstract data structures needed.
-
A description of the implementations of those abstract data structures.
-
A definition of the algorithm itself, in concise form.
-
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.
-
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.
-
Problem 7.35 on page 256 of your textbook.
-
Problem 8.28 on page 281 of your textbook.
-
Problem 8.32 on page 281 of your textbook.
-
Pattern matching and finding subsequences.