CS 660: Combinatorial Algorithms
Old Exams
[To Lecture Notes Index]
San Diego State University -- This page last updated October 23, 1995
Contents of Old Exams
- Midterm Fall 1994
- Final Fall 1994
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
.
