Assignment 1 - JBP030 (Fall 2018)

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]

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?

In [1]:
def something(A):
    """ The input is a python 'list'. For our purposes you may assume it is an array of size n = len(A) """
    n = len(A)
    k = 0
    for i in range(0, n): # In pseudo-code: for i=0,...,n-1
       if A[i]%2 == 1: # In pseudo-code: If A[i] is odd
           k = k + 1
    return n - k

Exercise 2 [5 points]

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

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

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.

Exercise 3 [5 points]

Are the following statements true or false? Briefy explain your answers (a-c). Provide a formal proof for your answer for (d-e).

(a) $n^2 \log n = O(n^2)$

(b) $n + \log n = \Omega(n)$

(c) $10 n^2 + 4n -17 = O(n^2 - 5n)$

(d) $n \log n = \Theta(n)$

(e) If $f(n) = O(g(n))$, then $g(n) = \Omega(f(n))$.

Exercise 4 [5 points]

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

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

(b) As (a), but now give a recursive algorithm. Note: For the running time it is sufficient to give an informal argument.

In [ ]: