Revisions
This chapter does not contain any new content, it is only intended to prepare you for the final exam.
Multiple choice question
Indicate, for each pair of expressions \((A,B)\) in the table below, whether \(A\) is \(o\), \(O\), \(\Theta\), \(\Omega\), \(\omega\) of \(B\).
\(A\) |
\(B\) |
\(o\) (A < B) |
\(O\) (A ≲ B) |
Θ (A ∼ B) |
|---|---|---|---|---|
\(n\) |
\(n+1\) |
|||
\(n\) |
\(n^{1.5}\) |
|||
\(4n^2\) |
\(n^2 + n^{1.5}\) |
|||
\(\log{10n}\) |
\(10\sqrt{n}\) |
|||
\(n\log{n}\) |
\(n\log{n}\log{n}\) |
|||
\(\log{n^{10}}\) |
\(\log(n)\) |
|||
\(\log_{10}{n}\) |
\(\log(n)\) |
|||
\(5^n\) |
\(3^{n+4}\) |
|||
\(3^{2n + 2}\) |
\(5^n\) |
Assume that we have the following functions:
f1(n)runs in \(\Theta(1)\)
f2(n)runs in \(\Theta(\log(n))\)
f3(n)runs in \(\Theta(n)\)
f4(n)runs in \(\Theta(n^2)\)
Moreover, cond(n) is a boolean function (it returns true or false) which runs in constant time \(\Theta(1)\).
Give the runtime complexity of the following algorithms:
def algo1(n):
f1(n)
f3(n)
f3(n)
Runtime complexity of algo1(n): Θ()
def algo2(n):
for i = 0 to log(n):
f1(n)
f2(n)
f1(n)
f1(n)
Runtime complexity of algo2(n): Θ()
def algo3(n):
for i = 0 to n:
f2(n)
f2(n)
f4(n)
Runtime complexity of algo3(n): Θ()
def algo4(n):
for i = 0 to n:
f2(n)
f2(n)
f4(n)
for i = 0 to n:
f4(n)
f2(n)
Runtime complexity of algo4(n): Θ()
def algo5(n):
for i = 0 to log(n):
if i%3 == 0:
f3(n);
else:
f4(n);
Runtime complexity of algo5(n): O(), can we say that the bound is tight?
def algo6(n):
for i = 0 to n:
if cond(n):
f2(n);
else:
f3(n);
Runtime complexity of algo6(n): O(), can we say that the bound is tight?
def algo7(n):
for i = 0 to n:
if cond(n):
f2(n);
else:
f2(n);
Runtime complexity of algo7(n): O(), can we say that the bound is tight?
Consider the following recursive functions:
ones1(n):
if n <= 0:
print(1);
else:
ones1(n // 2);
ones2(n):
if n <= 0:
print(1);
else:
print(1);
ones2(n // 2);
ones3(n):
if n == 0:
print(1);
else:
ones3(n - 1);
ones3(n - 1);
ones4(n):
if n == 0:
print(1);
else:
ones4(n // 2);
ones4(n // 2);
The number of ones printed by the previous functions is in the order of:
ones1(n): Θ()ones2(n): Θ()ones3(n): Θ()ones4(n): Θ()
Give the worst case and average case runtime complexity for the following sorting algorithms:
Algorithm |
Worst Case |
Average Case |
|---|---|---|
Quick sort |
O() |
O() |
Insertion sort |
O() |
O() |
Merge sort |
O() |
O() |
Heap sort |
O() |
O() |
Remember that \(\sum_{i=0}^{i\leq n} a^i = \frac{1-a^n}{1-a}\) with \(a>0, a\neq 1\).
The complexity \(T1(n)\), with \(n\) the length of the input, of a recursive algorithm is given by:
with \(c_0\) and \(c_1\) two constants. Solve this recurrence equation, the runtime complexity is: Θ()
The complexity \(T2(n)\), with \(n\) the length of the input, of a recursive algorithm is given by:
with \(c_0\) and \(c_1\) two constants. Solve this recurrence equation, the runtime complexity is: Θ()
The complexity \(T3(n)\), with \(n\) the length of the input, of a recursive algorithm is given by:
with \(c_0\) and \(c_1\) two constants. Solve this recurrence equation, the runtime complexity is: Θ()
Counting sort is a sorting algorithm for small integer numbers with a linear runtime complexity. Assume that we have an array \(A\) of size \(n\) containing numbers between 0 and 1000. To sort this array, counting sort proceeds as follows:
For each number between 0 and 1000 compute how many times this number appears in \(A\).
Create the sorted array with the right elements at the right place. For example, if the number 0 appears 5 times in \(A\) then the 5 first numbers of the sorted array are 0; then, if the number 1 appears 3 times in \(A\) then the elements 5, 6 and 7 of the sorted array are 1; and so on.
Propose an efficient pseudo-code for counting sort under the assumption that the elements of the input array are integers between 0 and 1000.
You are at the bottom of a staircase made up of \(n\) steps. You choose the following arbitrary rule for climbing the staircase. If the number of the current step (the first step has the number 0) is:
even: you can climb either 1 or 3 steps.
odd: you can only climb 1 step.
You want to know the total number of different ways to reach the \(n\)-th step starting from the bottom of the stair.
Let \(G(m)\) be the number of ways to reach the step \(m\). For example, reaching step 4 can be done in the following ways:
Go to step 1, then step 2, then step 3, then step 4; or
Go to step 3, then step 4
Thus, we have G(4)=2.
Give a recursive definition of \(G(m)\)
Propose a naïve recursive pseudocode algorithm to compute \(G(m)\).
Propose an optimized dynamic programming iterative algorithm for computing \(G(m)\).
Give the runtime complexity of your algorithm with respect to \(n\).
Let \(a\) be an array of numbers of size \(n\). A subsequence of \(a\) is an array composed of elements of \(a\) taken in order (we can remove elements from \(a\) but we cannot change their order). For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7], but [1,3,2,7] is not.
The longest increasing subsequence problem is to find the longest subsequence \(s=[s_1,\dots,s_m]\) of \(a\) such that:
\(s_1 < s_2 > s_3 < s_4 > \ldots\) OR
\(s_1 > s_2 < s_3 > s_4 < \ldots\)
Let \(L\uparrow(i)\) (respectively \(L\downarrow(i)\)) be the length of longest alternating subsequence ending at index \(i\) of \(a\) and whose last element is greater (respectively smaller) than its penultimate (the one before the last).
Give a recursive formulation of \(L\uparrow(i)\) and \(L\downarrow(i)\).
Draw the subproblem graph of \(L\uparrow(4)\) and \(L\downarrow(4)\)
Propose a naïve recursive algorithm to compute the longest alternating subsequence of \(a\).