Exercise I, Algorithms 2022-2023

These exercises are for your own benefit. Feel free to collaborate and share your answers
with other students. Sove as many problems as you can and ask for help if you get stuck for
too long. Problems marked * are more difficult but also more fun :).
These problems are taken from various sources at EPFL and on the Internet, too numer-
ous to cite individually.

Basic Algorithms
1 (Based on Exercise 2.1-3 in the book) Consider the searching problem:

Input: A sequence of n numbers A = ha1 , a2 , . . . , an i and a value v.

Output: An index i such that v = A[i] or the special value N IL if v does not appear in A.

1a Which of the following are instances of the problem and what are the correct outputs for
those instances?

h1, 5, 3, 4i and a value v

h3, 8, 3, 4, 50, 47i and a value 50
h3, 8, 3, 4, 49, 47i and a value 9

Solution. (i) Input v is a variable, not a constant number. Therefore, this is not a valid instance
of the problem.
(ii) The input consists of a sequence A of numbers and a constant value of 50 to be searched in
A. This is a valid instance of the problem and the output is 5.
(iii) The input consists of a sequence A of numbers and a constant value of 9 to be searched in
A. This is a valid instance of the problem and the output is NIL since number 9 is not in the
sequence.


1b Write pseudocode for linear search, which scans through the sequence, looking for v.
Using a loop invariant, prove that your algorithm is correct. Make sure that your loop
invariant fulfills the three necessary properties (Initialization, Maintenance, Termination).

Page 1 (of 7)

CS-250 Algorithms • Autumn 2022

Michael Kapralov
 Solution. Pseudocode for linear search is:

Linear-Search(A,v)
1 for i ← 1 to length(A)
2 if A[i] = v then
3 return i
4 return NIL

Loop invariant: At the start of each iteration of the for loop we have A[j] 6= v for all j < i.
Initialization: Before the first iteration of the for loop, the loop invariant is trivially true
because the statement is empty.
Maintenance: Suppose that the loop invariant is true before the i-th iteration of the for loop
and that there is a (i + 1)-st iteration of the for loop. From the former we know that A[j] 6= v for
all j < i and from the latter we know that A[i] 6= v. We conclude that A[j] 6= v for all j < i + 1
before the (i + 1)-st iteration of the for loop as claimed.
Termination: There are two cases: The first case is that the for loop terminates with i ≤
length(A) and the algorithm outputs i. In this case the loop invariant ensures that A[j] 6= v for
j < i and the if condition ensures that A[i] = v. Hence the output i is correct. The second case
is that i = length(A) + 1 and the algorithm outputs NIL. In this case the loop invariant ensures
that A[j] 6= v for j < length(A) + 1. Hence the output NIL is correct. 

1c Analyze the worst-case running time of your algorithm in terms of Θ-notation.

Solution. There is one for loop in the algorithm which always starts from i = 1, and, in the
worst case, iterates until i = n + 1 (i.e., when the value v is not in the list). The if condition
inside the loop and the increment of i at the end of each iteration both run in constant time,
i.e., O(1). The maximum number of iterations is n + 1 and this dominates the constant running
time of primitive lines of the algorithm. As a result, the running time of the algorithm is lower-
bounded by some function c1 · n and upper-bounded by some other function c2 · n whenever
n ≥ n0 , where c1 < c2 , and c1 , c2 , n0 are positive constants. Hence, the worst-case running
time of linear search is Θ(n). 

Asymptotics
2 Show that for any real constants a and b, where b > 0,

(n + a)b = Θ(nb ).

Page 2 (of 7)

CS-250 Algorithms • Autumn 2022

Michael Kapralov
 Solution. Suppose a > 0. Then, since (n + a)b ≥ nb for all n > 0, we obviously have (n + a)b =
Ω(nb ). Let us fix some N = a, then for all n > N , we have

(n + a)b ≤ (2n)b = 2b nb .

Thus, (n + a)b = O(nb ) as well and therefore (n + a)b = Θ(nb ).

Now, if a < 0, we have that nb = ((n + a) − a)b = Θ((n + a)b ) by the previous part, which
concludes the proof. 

3 Simplify and arrange the following functions in increasing order according to asymptotic growth.
√ √
3N , 4N , log2 N, 2N log2 N , N , N 2 , log N, 20N, N !, (N/e)N

Solution.

• First the logs: log N, log2 N

√
• Second the polynomials: N , 20N, N 2
√
• Then the exponential functions: 4N = 2N , 3N
√
• Finally, (N/e)N , N ! and 2N log2 N = N N . This is because N ! = 2πN (N/e)N (1 + o(1)) by
Stirling’s formula, so (N/e)N = o(N !) and N ! = o(N N )

4 Express the following functions in terms of Θ-notation:

 
N
p
NN N 2 3 2 N
3 + 2 , 3 + 4 , log (N + 300N ), log
2

Solution.
For the first function: 3N √
+ 2N = Θ(3N ), as 3N ≤ 3N + 2N ≤ 2 √ · 3N for all N √
≥ 1.
For the second function: 3 + 4 = Θ(2 ). This is because
N N N
√ 3 N + 4N ≥ 4N = 2N for
all N , and 3 ≤ 4 for N ≥ 0, so 3 + 4 = O(4 ), and hence 3N + 4N = O(2 ).
N N N N N N

For the third function log2 (N 3 + 300N 2 ) = Θ(log2 N ). This is because log2 (N 3 + 300N 2 ) ≥
log (N 3 ) = Ω(log2 N ). At the same time N 3 + 300N 2 ≤ 2N 3 for all N ≥ 300, so N 3 + 300N 2 =
2

O(N 3 ).
For the fourth function log N2 = Θ(log N 2 ) = Θ(log N ). Indeed, for all N ≥ 2 one has

N 2 /4 ≤ N2 ≤ N 2 /2. In particular, this means that log N2 ≥ 2 log N − O(1) ≥ log N for

sufficiently large N , so log N2 = Ω(log N ). Similarly log N2 ≤ 2 log N = O(log N ).



Proof by Induction
5 Prove the following equalities using induction:
n(n+1)(2n+1)
5a 12 + 22 + · · · + n2 = 6 .

Page 3 (of 7)

CS-250 Algorithms • Autumn 2022

Michael Kapralov
Solution. Base case: Clearly, 12 = 1(2)(3)
6 .
Induction step: Suppose now that n > 1 and the equality holds for n − 1. On the one
hand,

(n − 1)n(2n − 1)
12 + 22 + ... + (n − 1)2 + n2 = + n2
6
2n3 − 3n2 + n + 6n2 2n3 + 3n2 + n
= = .
6 6
On the other hand, n(n + 1)(2n + 1) = 2n3 + 3n2 + n.
Conclusion: We can then conclude with weak induction. 

5b The Fibonacci series is recursively defined for n ≥ 1 by

f1 = 1, f2 = 1, fn = fn−1 + fn−2 , n ≥ 2.

Show the Binet formula:

" √ !n √ !n #
1 1+ 5 1− 5
fn = √ − for all n ≥ 1
5 2 2

√  √ 2 √  √ 2
Hint: 3+ 5
2 = 1+ 5
2 and 3− 5
2 = 1− 5
2

Page 4 (of 7)

CS-250 Algorithms • Autumn 2022

Michael Kapralov
 Solution. Base Case: If n = 1,
" √ √ # " √ √ # √
1 1+ 5 1− 5 1 1+ 5−1+ 5 1 2 5
√ − =√ =√ = 1 = f1 .
5 2 2 5 2 5 2
If n = 2,
√ !2 √ !2 √ √ # √
  "
1  1+ 5 1− 5  1 3+ 5 3− 5 1 2 5
√ − =√ − =√ = 1 = f2 .
5 2 2 5 2 2 5 2

Induction Step: Suppose further that n > 1 and the formula holds for all k < n. Then, by
the definition of a fibonacci number and by the induction step,
fn = fn−1 + fn−2
√ !n−1 √ !n−1 √ !n−2 √ !n−2
 
1  1+ 5 1− 5 1+ 5 1− 5
=√ − + − 
5 2 2 2 2
√ !n−2 √ √ !n−2 √
 ! !
1 1+ 5 1+ 5 1− 5 1− 5
=√  +1 − +1 
5 2 2 2 2
√ !n−2 √ ! √ !n−2 √ !
 
1 1+ 5 3+ 5 1− 5 3− 5 
=√  −
5 2 2 2 2
√ !n−2 √ !2 √ !n−2 √ !2
 
1 1+ 5 1+ 5 1− 5 1− 5 
=√  −
5 2 2 2 2
" √ !n √ !n #
1 1+ 5 1− 5
=√ − .
5 2 2
Conclusion: By strong induction, we can conclude the proof. Note that at each step we
only need the two previous ones; this is also why we have to prove two cases in the base step. 

6 (*) What is wrong with the following proof that all horses have the same color?
Let P (n) be the proposition that all the horses in a set of n horses are the same color.
Base case: Clearly, P (1) is true.
Now assume that P (n) is true. That is, assume that all the horses in any set of n horses
are the same color. Consider any n + 1 horses; number these as horses 1, 2, 3, ..., n, n + 1.
Now the first n of these horses all must have the same color, and the last n of these must
also have the same color. Since the set of the first n horses and the set of the last n horses
overlap, all n + 1 must be the same color. This shows that P (n + 1) is true and finishes
the proof by induction.

Solution. The problem is that the “proof” that P (n) ⇒ P (n + 1) does not hold when n = 1.
This is because the argument given above is based on the “fact” that given n + 1 elements, any
two subsets of size n overlap or have at least one element in common. While this is true for
n + 1 ≥ 3, it is not true when n + 1 = 2. In this case, there are two subsets of size one and
it is easy to see that these subsets are disjoint. While P (1) holds for each of these subsets, i.e.
elements, each element can have a different color. 

Page 5 (of 7)

CS-250 Algorithms • Autumn 2022

Michael Kapralov
A Refresh “Proof by Induction”
Main principles. Recall that the principle of weak induction is
1. The statement is true for a base case (say an integer b).

2. Any time the statement is true for n ≥ b, one can show that the statement is true for n + 1.
Under these conditions, the statement is true for all integers ≥ b.
Similarly, the principle of strong induction is:
1. The statement is true for one or several base cases (say integers b, b + 1, . . . , b + i).

2. Any time the statement is true for all integers in [b, n] for some n ≥ b + i, one can show
that the statement is true for n + 1.
Under these conditions, the statement is true for all integers ≥ b.
This looks rather technical so let us clarify these concepts with two examples1

Example A.1 (weak induction) Prove by induction that for all positive integers n ∈ Z+
n
X 1 n
= . (1)
i(i + 1) n+1
i=1

Proof. We will prove (1) by weak induction.

Base case: When n = 1, the left side of (1) is 1/(1 · 2) = 1/2, and the right side is 1/2, so
both sides are equal and (1) is true for n = 1.
Induction step: Let k ∈ Z+ be given and suppose (1) is true for n = k. Then
k+1 k
X 1 X 1 1
= +
i(i + 1) i(i + 1) (k + 1)(k + 2)
i=1 i=1
k 1
= + (by induction hypothesis)
k + 1 (k + 1)(k + 2)
k(k + 2) + 1
= (by algebra)
(k + 1)(k + 2)
(k + 1)2
= (by algebra)
(k + 1)(k + 2)
k+1
= .
k+2
Thus, (1) holds for n = k + 1, and the proof of the induction step is complete.
Conclusion: By the principle of (weak) induction, (1) is true for all n ∈ Z+ . 

Example A.2 (strong induction) The fibonacci series is recursively defined for n ≥ 1 by

f1 = 1, f2 = 1, fn = fn−1 + fn−2 , n ≥ 2.

We have for all n ∈ Z+ that

fn ≥ (3/2)n−2 . (2)
1
These examples are taken from http://www.math.uiuc.edu/ hildebr/213/inductionsampler.pdf. See that page
for many more examples.

Page 6 (of 7)

CS-250 Algorithms • Autumn 2022

Michael Kapralov
Proof. Base cases: When n = 1, the left side of (2) is f1 = 1, and the right side is (3/2)−1 =
2/3, so (2) holds for n = 1. When n = 2, the left side of (2) is f2 = 1 and the right side is
(3/2)0 = 1, so both sides are equal and (2) is true for n = 2.
Induction step: Let k ≥ 2 be given and suppose (2) is true for all n = 1, 2 . . . , k. Then

fk+1 = fk + fk−1 (by recurrence for fn )

k−2
≥ (3/2) + (3/2)k−3
(by induction hypothesis with n = k and n = k − 1)
= (3/2)k−1 (3/2)−1 + (3/2)−2


(by algebra)
 
2 4
= (3/2)k−1 +
3 9
10
= (3/2)k−1 ≥ (3/2)k−1 .
9
Thus, (2) holds for n = k + 1, and the proof of the induction step is complete.
Conclusion: By the principle of strong induction, it follows that (2) is true for all n ∈ Z+ .


Remarks: Number of base cases: Since the induction step involves the cases n = k
and n = k − 1, we can carry out this step only for values k ≥ 2 (for k = 1, k − 1 would be
0 and out of range). This in turn forces us to include the cases n = 1 and n = 2 in the base
step. Such multiple base cases are typical in proofs involving recurrence sequences. For a three
term recurrence we would need to check three initial cases, n = 1, 2, 3, and in the induction step
restrict k to values 3 or greater.

Page 7 (of 7)

CS-250 Algorithms • Autumn 2022

Michael Kapralov