E2011: Theoretical fundamentals of computer science
Introduction to algorithms - Exercises
Vlad Popovici, Ph.D.
Fac. of Science - RECETOX
Problem 1
Quadratic equations
Write the pseudocode for solving the second-degree equation
ax2
+ bx + c = 0, a, b, c ∈ R
identify the input and output
express the solution
check that all the input cases are covered
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Exercise2 / 8
Algorithm 1 Quadratic equation solver
Input: a, b, c ∈ R
Output: x1, x2 solutions of ax2 +
bx + c = 0
if a = 0 then
if b = 0 then
if c = 0 then
print ”Undet. eq.”
else
print ”Imp. eq.”
end if
else
x1 ← −c/b
print ”1st deg. eq.:” x1
end if
else
∆ ← b2 − 4ac
if ∆ ≥ 0 then
x1,2 ← −b±
√
∆
2a
print ”Solution(s): ”, x1,2
else
x1 ← −b/(2a)
x2 ←
√
−∆/(2a)
print x1 + i x2
end if
end if
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Exercise3 / 8
Problem 2
Series processing
Given a series (vector) of elements [xi ], i = 1, . . . , N, compute:
sum of all elements
product of all non-zero elements
cummulative sum of positive elements (Sk = i∈P xi , where P is the
set of indexes of positive elements)
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Exercise4 / 8
Problem 3
Series processing
Let [ai ], i = 1, . . . , N, N ≥ 3 be a real-valued vector. Write the
pseudocode to
let the user input the values for [ai ]
compute a new vector [si ] defined as
si =
0 i ∈ {1, N}
ai+1−ai−1
2 0 < i < N
,
display (output) the result
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Exercise5 / 8
Solution to Problem 3
Input: N ∈ N, N ≥ 3 ▷ total number of elements
Output: [si ], i = 1, . . . , N, as required
input N ▷ ask the user for the value of N
input [ai ], i = 1, . . . , N ▷ ask the user for vector elements
[si ] ← 0, i = 1, . . . , N ▷ initialize the result vector
for i = 2, . . . , N − 1 do
si ←
ai+1−ai−1
2
end for
print [si ], i = 1 . . . , N ▷ show the result
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Exercise6 / 8
Problem 4
Sieve of Eratosthenes
Write the pseudocode to find all prime numbers smaller than a given
N ∈ N, N ≥ 2 using the algorithm ”sieve of Eratosthenes”.
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Exercise7 / 8
(non-optimal) Solution to Problem 4
Input: N ∈ N, N ≥ 2
Output: P - the set of prime
numbers ≤ N
P ← ∅
C ← {2, . . . , N} ▷ candidates
x ← 2 ▷ first prime
while C ̸= ∅ do
P ← P ∪ {x} ▷ add current
for k = 1, . . . , ⌊max(C)/x⌋
do
if kx ∈ C then
C ← C \ {kx}
end if
end for
if C ̸= ∅ then
x ← min(C)
end if
end while
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Exercise8 / 8