{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Assignment 1 - 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": [ "What does the algorithm below compute? Prove your claim with the help of a loop invariant. What is the groth rate of its worst-case running time?" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def something(A):\n", " \"\"\" The input is a python 'list'. For our purposes you may assume it is an array of size n = len(A) \"\"\"\n", " n = len(A)\n", " k = 0\n", " for i in range(0, n): # In pseudo-code: for i=0,...,n-1\n", " if A[i]%2 == 1: # In pseudo-code: If A[i] is odd\n", " k = k + 1\n", " return n - k" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2 [5 points]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "(a) Prove by induction on $n \\ge 1$ that $\\sum_{i=1}^n (i-\\frac{1}{2}) = \\frac{n^2}{2}$ by using the induction hypothesis: *Assume that $\\sum_{i=1}^n (i-\\frac{1}{2}) = \\frac{n^2}{2}$ holds.*\n", "\n", "(b) Consider a $2^n \\times 2^n$ chessboard with one (arbitrarily chosen) square removed. We want to tile the chessboard without gaps (except for the removed square) or overlaps by L-shaped pieces, each composed of 3 squares. The figure below shows an L-shaped piece, a chessbord with a square removed, and a tiling of this chessboard.\n", "\n", "\n", "Give a high-level description (i.e., it is enough to convey the idea) of a recursive algorithm to compute such a tiling. Prove the correctness of your algorithm by a (weak) induction on $n$. You do not need to analyze the running time." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 3 [5 points]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Are the following statements true or false? Briefy explain your answers (a-c). Provide a formal proof for your answer for (d-e). \n", "\n", "(a) $n^2 \\log n = O(n^2)$\n", "\n", "(b) $n + \\log n = \\Omega(n)$\n", " \n", "(c) $10 n^2 + 4n -17 = O(n^2 - 5n)$\n", "\n", "(d) $n \\log n = \\Theta(n)$\n", "\n", "(e) If $f(n) = O(g(n))$, then $g(n) = \\Omega(f(n))$.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 4 [5 points]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You are given an array $A$ of size $n$ that contains distinct (i.e. no number occurs more than once) numbers with the following property: First the numbers in $A$ increase and then they decrease. Stated differently, there is an (unknown) index $i$ such that $A[j] < A[j+1]$ for all $0 \\le j < i$, and $A[j] > A[j+1]$ for all $i \\le j < n-1$.\n", "\n", "(a) Give an iterative worst-case $O(\\log n)$-time algorithm that determines the index of the maximum element of $A$. *Don't forget to prove correctness and analyze the running time.* \n", "\n", "(b) As (a), but now give a recursive algorithm. *Note: For the running time it is sufficient to give an informal argument.*" ] }, { "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 }