{ "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 }