University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

CSC 477/677 Assignment 3

Due date: Tuesday, March 29, 2011, 4:00 PM.

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 the teaching assistant on or before the due date
  1. Walk through Kruskal's Algorithm to find a minimum spanning tree for this weighted graph. Use union-find, with path compression, as we did in class. Show all steps of union-find, including path compression.
    Graph in pdf format.
  2. How many sequences are there consisting of the numbers 2, 3, 5, and 7, such that
    1. No two consecutive terms of the sequence are equal.
    2. The total of the terms of the sequence is 25.
    An example of such a sequence is 2,3,7,5,3,2,3. Use dynamic programming, showing your steps.
  3. Use the Hu-Tucker algorithm to find an optimal alphabetic prefix code for the following alphabet with given frequencies. Show your steps.

Back to Course Page