CSC 477/677 Assignment 2

Due date: Thursday, March 10, 2011, 4:00 PM.

1. Use Huffman's algorithm to construct an optimal prefix code for the alphabet consisting of the first 13 letters of the Roman alphabet, together with the space symbol. Use this table of frequencies.
2. Use the Bellman-Ford algorithm to solve the single source shortest path problem for this graph of ten nodes.
   
   • The first line of the file contains n, the number of vertices of G. The names of the vertices are the integers from 1 to n.
     (Note that n = 10 in this example.)
   • Each remaining line of the graph is a list of integers separated by spaces, and represents the list of outneighbors of one vertex.
   • The first number in the line is the name of the vertex.
   • After that, there is a sequence of pairs, consisting of a vertex name and a weight.
   • For example, the third line of the file,
     8 5 3 7 3 4 -2
     indicates that there is an edge from 8 to 5 of weight 3, an edge from 8 to 7 of weight 3, an edge from 8 to 4 of weight -2, and no other edges from 8.
   • The source will be vertex 1.
3. Walk through Dijkstra's algorithm to solve the single source shortest problem for the weighted directed graph given. The source is s.
   The graph in postscript format.
   The graph in portable document (pdf) format.
   You don't have to use up a ream of paper describing each iteration of the inner loop. Instead, you only need to write something when some value of the array d changes. I was able to do it on a single sheet of paper in 16 minutes.
4. We say that a sequence of integers is nice if it is increasing and the difference between consecutive terms is either 5 or 6. For example, the sequence 0,5,11,17,22,27,33 is nice.
   Use dynamic programming to compute the number of nice sequences that start with 0 and end with 50.
   Hint: Don't attempt to solve this problem by listing all the sequences. Yes, it can be done. But that is a very inefficient way to do it, and it will be marked wrong, since that is not the method you are supposed to use.



















5. Build a cuckoo hash table of size 13, using these inputs. The first line is 13, the size of the hash table. Each subsequent line consists of a name, the first hash value of that name, and then the second hash value of that name. Insert the names into the hash table in alphabetical order, which is the order given.
6. 1. Insert these letters into a binary search tree in the order given.
   2. What is the height of the resulting binary search tree?
   3. You have been told that if n items are inserted at random, the expected height of a binary search tree is O(log n). However, if you go to the world wide web and search for "average height of a binary tree" you will discover that that average height of a binary tree of n nodes is (asymptotically) Theta of the square root of n.
      This appears to be a contradiction, but it isn't. Explain why not.
7. Use Kruskal's algorithm to find a minimum spanning tree for this graph.
8. Use the Floyd Warshall algorithm to solve the all-pairs shortest path problem for the graph shown below.
   The graph in postscript format.
   The graph in portable document (pdf) format.
9. Click here if you think this homework assignment is too easy.