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