Assignment 1 - JBP030 (Fall 2017)

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 asymptotic running time of the algorithm?

In [1]:
def whatever(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)
    s=0
    for i in range(0, n): # In pseudo-code: for i=0,...,n-1
       if A[i]%2 == 0: # In pseudo-code: If s is even
           s = s + A[i]
    return s

Exercise 2 [5 points]

(a) Prove by induction on $n \ge 1$ that $\sum_{i=1}^n (i-1) < n^2/2$ by using the induction hypothesis: Assume that $\sum_{i=1}^n (i-1) < 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 = \Omega(n)$

(b) $2^{2n} = O(2^{n+1})$

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

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

(e) If $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$.

Exercise 4 [5 points]

You are given a sorted array $A$ of size $n$ that contains numbers in the range $1$ to $n+1$. We know that each number occurs at most once in $A$. Because there are only $n$ numbers in $A$ out of $n+1$ possible numbers, exactly one of the numbers is missing.

(a) Give a worst-case $O(\log n)$-time algorithm that determines the missing number. Don't forget to argue correctness and analyze the running time. You don't need to give a formal proof. (Note: If not stated otherwise, this is what you should do whenever you give an algorithm.)

(b) How fast can we compute the missing number if $A$ is not sorted? You can provide an algorithm as answer. Don't forget to argue ...

In [ ]: