# 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.