CSC 477/677 Assignment 5
Due date, November 22, 2005, 11:00 AM.
All assignments must be handwritten
(not typed or printed from a computer file)
in your own handwriting, on 8.5 by 11 inch paper. Write your name on
each sheet, and do not fold the pages or crimp the corners.
Turn the pages in to me or to the graduate assistant on the due date.
-
Draw a picture of the weighted graph representing
roads and distances
on the island of Molokai. Then, run Kruskal's algorithm, by hand,
obtaining a minimal spanning tree.
-
Consider this weighted directed graph .
Work Dijkstra's algorithm by hand on this graph, to solve the
single source minimum path problem, where the source is s.
matrix representation of the graph
postscript file of the graph
pdf file of the graph
-
This file shows the approximate number of
times each of the 26 letters of the alphabet is used per 1000 words
in English text. "Space" is then added to the alphabet so that words
are separated.
Use Huffman's algorithm, by hand, to find an optimal binary
prefix code for that alphabet, given those frequencies.
Back to
Course Page