San Diego State University

Solve any six of the following problems.

1. We are keeping an ordered list of items in an array. Provide a potential function which gives an amortized cost of O(n) to insert an item, an O(1) to delete an item.

2. A tree T is a (2,8)-tree if

i) All leaves of T have the same depth

ii) All internal nodes v of T have at most 8 children (ie each node can have 7 keys)

iii) All internal nodes have at least 2 children

iiii) All keys are stored in order, that is the tree is a search tree.

a) Show how to convert a (2,8)-tree to a binary search tree with the nodes colored with two colors.

b) What properties hold true in the binary search tree created in a)

3. The greedy algorithm can be used to create the optimal static ordering for a linear list. Can the greedy algorithm can be used to create the optimal binary search tree. Explain your answer.

4. a) Use the Hu-Tucker algorithm to construct the optimal alphabetic tree given the following items and frequency of access.

Item a b c d e

Frequency 1 2 2 3 4

b) What is the time complexity of the Hu-Tucker algorithm?

5. Discuss the time complexity of dynamic programming algorithms.

6. Using just the mathematical analysis and understanding of the algorithms, discuss the strong points of red-black trees, splay trees, and skiplists. That is which conditions favor each algorithm?

7. Dynamic programming can be used to solve the following problem: determine how many ways there are to give x cents in change using pennies, nickels, and dimes. What is the recursion that will define the optimal solution. (Hint: how would you solve it with just pennies and nickels? with just pennies?)

8. Add 27 to the following splay tree using top-down splay. Show your work.

10. Average case analysis and amortized analysis both provide information about the performance of an algorithm over a sequence of operations. What is the difference?

11. Under what conditions will move-to-front perform better than optimal static ordering of a linear list?

1. Prove or disprove the following:

a. f(n) = O(g(n))) implies that g(n) = O(f(n))

b. f(n) = O(g(n)) implies that f(n) <= g(n) for all n

2. Contrast the performance of transpose and move-to-front self-organizing linear lists.

3. a. What is the potential function on a splay tree?

b. Explain how to implement the following using the splay operation

join (a, b): Return tree formed by combining tree "a", and tree "b". Assumes that every item in "a" has key less then every item in "b"

split (i, t): Split tree t, containing item i, into two trees: "a", containing all items with key less or equal to "i"; and "b", containing all items with key greater than "i"

delete(i, t): delete i from tree t

4. Describe the process of inserting an item into a skiplist. How does changing the value of p effect on the performance of the skiplist?

5. A red-red-black tree is a binary search tree that satisfies the following conditions:

1. Every node is either red or black

2. Every leaf (nil) is black

3. If a node is red and it's parent is red, then both its children are black

4. Every simple path from a node to a descendant leaf contains the same number of black nodes (the black-height of the tree)

What is the largest number of internal nodes in a red-red-black tree with black-height k?

6. Let f be a flow in a flow network G = (V, E) with source s and sink t argue that if the residual network Gf contains no augmenting paths then |f| = c(S,T) for some cut (S, T) of G.

7. Let f be a flow in a flow network G = (V, E) with source s and sink t. Let cf(u,v) be the residual capacity of the edge uv in E. Show that cf(u, v) + cf(v, u) = c(u, v) + c(v, u).

8.

T or F The probability of a search on a skiplist of size 256 being three times the expected value is less than the probability of a division error on Intel's pentium chip.

T or F If P != NP then no problem in NP can be solved in polynomial time.

9. A binary heap is a complete binary search tree with the following property: the value stored in a node, X, is smaller than the values stored in the children of X. Instructions Insert and extract-min can be performed on a heap with n items in O(lg(n)) worst case. (The operations have to maintain the heap property.) Give a potential function such that the amortized cost of Insert is O(lg(n)) and the amortized cost of Extract-min is O(1).

10.

a. Prove that if language then . ( is the complement of L).

b. Discuss the statement: if then .