CSE 101 Assignment 4
Due date, July 28, 2003, 9:30 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, or on A4 paper.
Write your name on each sheet, and do not fold the pages or crimp the corners.
(You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant at the beginning of class
on the due date.
There will be a 10% penalty if the homework is turned in during office hours
on the due date. Homework turned in later than that will not be accepted.
-
Work problem Exercise 3 at the top of page 310 of your textbook.
-
Use Graham's Scan to find the convex hull of
this set of points.
(You are to walk through the algorithm by hand, rather than writing a
computer program.)
-
Use Kruskal's algorithm to find a minimal spanning tree for
this weighted graph, showing steps.
Then, use Prim's algorithm to do the same thing, using the
same weighted graph, again showing steps.
(You are to walk through the algorithms by hand, rather than writing a
computer program.)
-
Use Huffman's algorithm to find an optimal prefix code for
this weighted alphabet, again showing steps.
(You are to walk through the algorithm by hand, rather than writing a
computer program.)
-
Use the Hu-Tucker algorithm to find an optimal alphabetic tree, using the
this sorted weighted list, again showing steps.
(You are to walk through the algorithm by hand, rather than writing a
computer program.)
Back to
Course Page
