{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Assignment 3 - JBP030 (Fall 2018)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 1 [5 points]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Recently, the CBS reported *In 2017 laagste aantal faillissementen van deze eeuw*, or stated differently, in 2017 the number of bankruptcies was lower than in the 16 previous years. This motivates the following algorithmic problem.\n",
"\n",
"We are given an array $A$ of size $n$, we want to compute for $i=0,\\ldots,n-1$ the (largest) value $B[i]$ such that the statement *\"$A[i]$ is smaller than the previous $B[i]$ entries\"* is true. If *A[i]* is smaller than all previous entries, then we set $B[i] = i$. \n",
"\n",
"For instance, given the bankrupticy data since 1981 $A = [7288, 8644, 7691, 6224,\\ldots ]$, we would get $B = [0,0,1,3,\\ldots]$. Note that this is different from counting how many previous values are larger, for instance if we had $A = [8644, 7288, 7691,\\ldots]$ then $B = [0,1,0,\\ldots]$.\n",
"\n",
"\n",
"Design a linear-time algorithm (*hint: using a stack*) that given $A$ computes $B$. If you want to run it on the actual data, then you can find it [here](https://www.win.tue.nl/~kbuchin/teaching/JBP030/bankruptcies.html).\n",
"\n",
"Analyze the running time. For the correctness you do not need to give a formal proof, but a sound argument is sufficient. *Note: This exercise is tricky. If you can't figure out what to store in the stack, ask for a hint.* "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 2 [5 points]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 3 [5 points]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(a) [3 points] Assume we have a decreasing sequence of numbers stored as a singly-linked list $L$, e.g., $L = \\langle 56, 13, 11, 2 \\rangle$ (where 56 is the value at the head). Design an algorithm that deletes every second number and sorts the list in increasing order. Thus, the singly-linked list after these modifications should be $L = \\langle 11, 56 \\rangle$ (where now 11 is the value at the head). Now the challenge is: Your algorithm should run in linear-time, and only use a constant amount of extra storage. So, for instance, you cannot copy $L$ to an array or make it a doubly-linked list. *Note: As always (if not stated otherwise) for the correctness a clear and sound argument is sufficient. You don't need provide a formal proof.*\n",
"\n",
"(b) [2 points] Illustrate the execution of HeapSort on the following input: $(1,9,17,20,15,19,11)$. 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.*)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise 4 [5 points]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"(*Reminder: Justify your answer, even if the question is a simple yes/no question.*)\n",
"\n",
"(a) [1 point] Is the sequence $\\langle 2, 5, 9, 7, 30, 21, 22, 25, 26, 28 \\rangle$ a min-heap?\n",
"\n",
"(b) [1 point] Where in a min-heap might the largest element reside, assuming that all elements are distinct?\n",
"\n",
"(c) [3 points] Devise a divide-and-conquer algorithm for building a heap stored in an array $A[0..n-1]$ in $O(n)$ time. You should derive the running time using a recurrence, and argue correctness."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.0"
}
},
"nbformat": 4,
"nbformat_minor": 0
}