Description
Problem 1
(a) Give an algorithm that multiplies two degree-1 polynomials with only three multiply operations.
That is, given coefficients a, b, c, and d, the algorithm should compute the values of the coefficients
in the expanded form of (ax + b) ∗ (cx + d). Hint: One multiplication will be (a + b)(c + d).
(b) Give a divide-and-conquer algorithm for multiplying two polynomials of degree n, and prove using
the master theorem that your algorithm runs in Θ(n
log2(3)) time. You may assume that n + 1 is a
power of 2.
Problem 2
Give an O(log(n)) time algorithm that computes the following function:
median-of-two(l1, l2)
Input: l1 and l2 are two sorted lists of integers. Each list has n elements – so there are 2n elements
in total – and the value of each element in the lists is unique.
Output: the value of the n
th smallest integer in the set of 2n integers in l1 and l2.
Problem 3
Give an O(n) average case running time algorithm that computes the following function:
k
th-smallest(list, k)
Input: an unsorted list list of unique integers and an integer k
Output: the value of the k
th smallest integer from list
Problem 4
Let T be a tree with n vertices. We say that a vertex v is a minimal separator of T if its removal splits
T into two or more subtrees, each with at most n/2 nodes.
(a) Show that every finite tree has at least one minimal separator.
(b) Give an O(|V |) algorithm for identifying a minimal separator in a given tree.
Problem 5
Give an algorithm that computes the following function:
bst-reconstruction(traversal)
Input: An array of elements traversal generated by a pre-order traversal of some binary search tree
T.
Output: An binary search tree identical to the original T.
1
Problem 6
Let G = (V, E) be a connected, undirected graph. Prove or disprove:
∃v ∈ V |
h
G0 = (V \ {v}, E) is connected i
Problem 7
Do problem 5-26 from the text.
Problem 8
Do problem 6-6 from the text.
Problem 9
Do problem 6-7 from the text.
2
