Exercise 1 Induction Proof and Recursion
1. Let N = {0, 1, 2, . .} be the set of natural numbers. Access to data structures is often governed by the recurrence
T(n) = a, if n = 1
c + T(n/2), if n>1
Prove by induction that T (n) ∈ O (log n). Do not attempt to use the Master Theorem for this proof.
2. Remind how merge-sort works. Show that recursive merge-sort is Θ(n log n) by the master theorem.
Exercise 2 Algorithm design
Describe a Θ(n log n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
Exercise 3 Binary heaps
1. Assume you have an array-based binary heap a with the contents:
1, 4, 7, 8, 9, 10, 14, 12, 15, 13, 17, 12
Show the contents of a after each of the following two operations. Show your working for each operation including the content of the list at its intermediate stages.
You can assume a is large enough to contain all the values inserted.
- Insert 5 into a,
- Delete the least element from a,
2. Is it right or wrong that in a heap of depth d, there must be at least 2d elements. (Assume the depth of the first element (or root) is zero). If it is right, provide your prove. If it is wrong, explain why you think so.
3. Prove that the binary tree represented by the binary heap of n elements has height k = [log n] .