CS 4349.003. Advanced Algorithm Design and Analysis
Spring 2017
Assignment 4
Thu, Mar 9

You can write or type your answers.  Submit in class or upload on elearning.

Due: 1:00 PM, Thu, Mar 23


1. Run the Huffman coding algorithm on the following input:
   Alphabet C = {p, r, a, i, s, e, d}, with
   frequencies f as percentages= {12, 16, 16, 12, 16, 16, 12}.
   Draw the optimal coding tree and the (weighted) average code length.
   Show the steps.  Write the codes for "paradise" and "airspeed".

2. Ex. 22.2-7 (p. 602).  Classify wrestlers (check if a graph is bipartite).

3. Run DFS on the graph in Fig. 22.8 (p. 615), under the assumption that the
   adjacency list is ordered as stated in Ex. 22.3-2 (p. 610).  Show the
   discovery and finish times for each vertex, and show the classification of
   each edge.  Show the topological order of vertices obtained by this run of DFS.


Optional problems (for extra credit):

A. Problem 16-2, part a (p. 447).  Scheduling to minimize average completion time.

B. Ex. 16.1-4 (p. 422).  Interval-graph coloring.

C. Ex. 22.1-4 (p. 593).  Find underlying simple graph of a multigraph.
   Solve this problem without using hashing.