Assignment 3 - JBP030 (Fall 2017)

Note: You should always justify your answers. Whenever you are asked to describe an algorithm, you should present three things: the algorithm, a proof of its correctness, and a derivation of its running time.

Exercise 1 [5 points]

Suppose you want to make statements of the form "It was warmer on day $i$ than on the $k$ previous days". Your input is the (average) temperatures on day $1,\ldots,n$ stored in an array $A$ of size $n$. Design a linear-time algorithm (using a stack) that computes for every day $i$ the $k$ from the statement above (and stores it in an array B). For instance, input $A = [14, 7, 31, 15, 20, 40]$ should result in output $B = [0, 0, 2, 0, 1, 5]$.

Analyze the running time. You do not need to prove correctness. Note: This exercise is tricky. If you can't figure out what to store in the stack, ask for a hint.

Exercise 2 [5 points]

Given a hash table of length $m = 11$, consider inserting the keys $10, 22, 31, 4, 15, 28, 17, 88, 59$ using open addressing with the hash function $h'(k) = k \mod m$. Show the result of inserting these keys by linear probing, by quadratic probing with $c_1=1$ and $c_2 = 3$, and by double hashing with $h''(k) = 1+(k \mod(m-1))$. For every key you should note how often you had to probe unsuccessfully before you could insert the key. For each hashing scheme give the total number of unsuccessful probes.

Exercise 3 [5 points]

(Reminder: Justify your answer, even if the question is a simple yes/no question.)

(a) [3 points] Illustrate the execution of HeapSort on the following input: $(7,13,25,42,17,36,16)$. Show every step that changes the array. (Remark: You do not need to give drawings of heaps in your solution; giving the arrays is sufficient.)

(b) [1 point] What is the running time of HeapSort on an array $A$ of length $n$ that is already sorted?

(c) [1 point] Is an array that is in sorted order a min-heap?

Exercise 4 [5 points]

(Reminder: Justify your answer, even if the question is a simple yes/no question.)

(a) [1 point] Is the sequence $\langle 42, 9, 25, 7, 1, 21, 22, 2, 4, 3 \rangle$ a max-heap?

(b) [1 point] Where in a max-heap might the smallest element reside, assuming that all elements are distinct?

(c) [3 points] Devise a divide-and-conquer algorithm for building a heap stored in an array $A[1..n]$ in $O(n)$ time. You should derive the running time using a recurrence, and argue correctness.