Foundations of Algorithms Assignment

Collaboration groups will be set up in Blackboard; however, there are no collaborative problems on this first assignment. All solutions are to be the result of individual e?ort.

Problems

1. Use induction to prove _i=1∑ⁿ i³ = ( {n(n+1)} / 2 )².

2. Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n²) worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become su?ciently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.

(a) Show that insertion sort can sort the n/k sublists, each of length k, in Θ(nk) worst-case time.

(b) Show how to merge the sublists in Θ(n lg(n/k)) worst-case time.

(c) Given that the modified algorithm runs in Θ(nk + n lg(n/k)) worst-case time, what is the largest value of k as a function of n for which the modified algorithm has the same running time as standard merge sort, in terms of Θ-notation?

(d) How should we choose k in practice?

3. Write a Θ(m + n) algorithm that prints the in-degree and the out-degree of every vertex in an m-edge, n-vertex directed graph where the directed graph is represented using adjacency lists.

4. Consider the following algorithm for doing a postorder traversal of a binary tree with root vertex root.

Algorithm 1 Postorder Traversal
Postorder(root)
if root ?= null then
Postorder(root.lef t);
Postorder(root.right);
visit root;
end if;

Prove that this algorithm runs in time Θ(n) when the input is an n-vertex binary tree.

5. We define an AVL binary search tree to be a tree with the binary search tree property where, for each node in the tree, the height of its children differs by no more than 1. For this problem, assume we have a team of biologists that keep information about DNA sequences in an AVL binary search tree using the specific weight (an integer) of the structure as the key. The biologists routinely ask questions of the type, "Are there any structures in the tree with specific weight between a and b, inclusive?" and they hope to get an answer as soon as possible. Design an efficient algorithm that, given integers a and b, returns true if there exists a key x in the tree such that a ≤ x ≤ b, and false if no such key exists in the tree. Describe your algorithm in pseudocode and English. What is the time complexity of your algorithm? Explain.