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

CSC 477/677 Assignment 2

Due date: Thursday, February 7, 2008, 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 on or before the due date.
  1. Work Problem 4-1 on page 85 of your textbook.
  2. Read Section 16.3 of your textbook, pages 385 to 391. Then, using the frequencies of the uses of letters in English given by Wikipedia, constuct an optimal prefix code for the first thirteen letters of the Roman alphabet, namely "a" through "m."
  3. Work Problem 16-1, a. and c., on page 402 of your textbook.
  4. Work Problem 16-3, c., on page 403 of your textbook. (Hint: you have already heard of this problem, under a different name.)
  5. Given a graph (V,E), where each member of V has a weight, you would like to find an independent set of vertices of maximum total weight. There is a simple greedy algorithm for this problem; namely, just pick the heaviest vertex, then the next heaviest that is not adjacent to that one, then the next heaviest that is not adjacent to the first two, and so forth, until every remaining vertex is adjacent to one that you've already picked.
    Prove that this greedy algorithm is very bad, that is, does not even come close to picking the best set. (You should do this by drawing an example, then showing how the greedy algorithm picks a set of vertices, and then showing that there is a much better choice that the greedy algorithm does not find.)

Back to Course Page