Past CS 660 Exams

San Diego State University

Solve any six of the following problems. Indicate which six problems you want graded.

- a. f(n) = o(g(n))) implies that g(n) = [[omega]](f(n))
- b. f(n) = o(g(n)) implies that f(n) > g(n) for all n

- b. Explain how this recurrence relation is related to (a, b) trees.

- AVL, Red-Black, Splay, Randomized Search tree

- b. Describe how to insert a node in a Treap.

Solve any six of the following problems. Indicate which six problems you want graded.

b) What is the time complexity of the Edmond-Karp algorithm?

c) Give an example of a network flow where the Ford-Fulkerson algorithm is faster than the Edmond-Karp algorithm.

- a. f(n) + g(n) =
_{ }(min( f(n), g(n) ). - b. f(n) = O( g(n) ) and f(n) =
_{ }( g(n) ) implies f(n) =_{ }( g(n) ).

b) Define the following terms: P, NP, polynomial transformation.

b) Describe the accounting method of amortized analysis.

- 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)

Item a b c d e

Frequency 1 2 2 3 4

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

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

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

- 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?

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.

a. Prove that if language

b. Discuss the statement: if