CSC 477/677 Assignment 4

Due date: Thursday, April 21, 2011, 4:00 PM.

1. Create a binary search tree. Start with an empty tree, and insert the following elements one at at time, in the following order:
   Ann, Zak, Van, Bob, Ted, Dan, Sam, Fay, Nan, Max.
   Hint: the tree will be very unbalanced.
2. Create a treap. Start with an empty tree, and insert the following elements one at a time, in the following order. After each item, I give the random number that your random number generator provides:
   Ann 54, Zak 30, Van 58, Bob 97, Ted 30, Dan 69, Sam 25, Fay 13, Nan 31, Max 24.
   Show the treap after each insertion/rebalancing step.
3. What is the maximum number of edges a graph of n nodes can have? (I want an exact formula in n, not an asymptotic answer.)
4. What is the minimum number of edges a connected graph of n nodes can have? (I want an exact formula in n, not an asymptotic answer.)
5. What is the maximum number of edges an acyclic graph of n nodes can have? (I want an exact formula in n, not an asymptotic answer.)
6. What is the maximum number of edges a directed acyclic graph of n nodes can have? (I want an exact formula in n, not an asymptotic answer.)
7. What is the minimum number of edges a strongly connected directed graph of n nodes can have? (I want an exact formula in n, not an asymptotic answer.)
8. If a planar graph has 4 nodes, it can have no more than 6 edges. If a planar graph has 5 nodes, it can have no more than 9 edges. For any n larger than 5, what is the maximum number of edges a planar graph with n nodes can have? (I want an exact formula in n, not an asymptotic answer.)
9. Describe a dynamic programming algorithm to find the longest monotone increasing subsequence of a finite sequence of numbers. (For example, the longest monotone increasing subsequence of the sequence 1,4,9,2,5,2,3,7,1 is 1,2,2,3,7.)
   Hint: there is a fairly straightforward algorithm that takes O(n²) time, where n is the length of the sequence.
10. A three dimensional array A is stored in RAM in column major order. The first index of A is an integer in the range 1 to 8, the second index of A is an integer in the range 5 to 20, and the third index of A is an integer in the range -4 to 7. (Yes, it is possible to declare an array with such bounds in some computer languages.) Assume that each item stored in A takes 2 address locations in RAM, and that the base address of A is 1024. Find the address of A[5,12,3] in RAM.
11. There are a number of versions of cuckoo hashing. The version we learned in class is probably the simplest, where there are two hash functions, and thus only two places where any given item could be stored in the table.
    One problem with cuckoo hashing is that the insertion procedure can enter an infinite loop, and thus the new item cannot be inserted, even though there are still empty places in the table. If the table is mostly empty, this is very unlikely if the hash functions are "good." For example, the probability that we will fail to insert the third item in a table of size m is is 4*m^-2*(m-1)^-2, which is very small if m is large. On the other hand, if we continue to insert items, the insertion procedure will fail with a very high probability before the table is completely full.
    Is a cuckoo hash table that is 70 percent full considered safe, in the sense that it is extremely likely that we can insert another item? If not 70 percent, what is the approximate number of items we can safely (well, almost safely) insert into a cuckoo hash table of size n?
    Hint 1: Look at the world wide web.
    Hint 2: Write a program.