Practice Exercises - Lecture 1

Exercise 1

Rank the following functions of $n$ by order of growth (starting with the slowest growing). Functions with the same order of growth should be ranked equal.

(a) $\log n^3$, $n$, $n^2 \log n$, $4^{\log n}$, $\log \sqrt{n}$, $n + \log n^4$, $2^{\log 16}$, $n^{-1}$, $16$, $n^{\log 4}$

(b) (Note: This part is not much different from (a) and provided for extra practice. You may want to skip it the first time you do the exercises.)

$1$, $n$, $n^{-2}$, $\log 3$, $n + \log n$, $\log n^2$, $16^{\log n}$, $\sqrt n \log n$, $\log n$, $n^{\log 16}$

Exercise 2

Prove by induction:

(a) For every integer $𝑛 \ge 5$, $2^n > 𝑛^2$

(b) $\sum_{i=1}^{n} 2i-1\ = n^2$

(c) $\sum_{i=0}^{n} x^i\ = (1-x^{n+1})/(1-x)$

Note: Additional induction exercises are provided on the slides

Exercise 3

We define the problem CountInInterval as follows: Given an array $A$ of $n$ integers, and two integers $p$ and $q$, count the number of elements of $A$ that are at least $p$ and at most $q$.

(a) Give an algorithm for CountInInterval.Don't forget to prove correctness and analyze the running time.

(b) Apply your algorithm on the weather data provided on the course website.

Exercise 4

For each function on the left, $p(n)$, write the letter of a function on the right, $q(n)$, such that $p(n) \in \Theta(q(n))$, that is, $p(n)$ and $q(n)$ have the same growth rate. If no such function $q(n)$ is listed, then choose (l).

Exercise 5

Take any of the algorithmic problems from the tutorial on loop invariant proofs, write down your version of an algorithm for the problem and prove correctness using a loop invariant.

In [ ]: