CSC326, Spring 2006, Homework #1

• Build a binomial queue by repeatedly inserting 1,2,3,4,5,6,7,8. To remove the ambiguity that occurs when there are 3 1's in a column, use the carry as the result and join the other two 1's.
• Exactly how many key comparisons are done in merging together two binomial queues, one of size 100 and another of size 111?
• Build a Huffman tree on the weights 2,7,1,8,2,8,1,8,2,8,4. What is the average per character code length?
• Prove that there is no algorithm for building a Huffman tree that has running time O(n) where n is the number of leaves in the tree.
• Draw the five ordered forests with 3 nodes and the corresponding binary trees with 3 nodes, using the left-child right-sibling correspondence.
• Write a depth-first-search program in Java to investigate the size of the largest component in a graph as a function of n, the number of vertices, and p, the probability with which an edge occurs. Test your program for n = 1000, and p = 0.01, 0.02, ..., 0.99. Try some other values of n. Try to guess the relation between n, p, and the size of the largest component.