E2011: Theoretical fundamentals of computer science
Introduction to algorithms - Additional exercises
Vlad Popovici, Ph.D.
Fac. of Science - RECETOX
Problem 1
Search problem
Given a sequence of n numbers, A = [a1, . . . , an] and a value v, find
1 whether v appears in A and, if yes, output its position, otherwise
output ”value not found” message;
2 whether v appears in A and, if yes, output its position, otherwise
output the closest value in A to v
identify the input and output
express the solution
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Additio2 / 7
Algorithm 1 Find value in a sequence - part 1
Input: n ∈ N, A = [a1, . . . , an], v ∈ R
Output: i such that ai = v or text
for i = 1, . . . , n do
if ak = v then
return i
end if
end for
print ”value not found!”
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Additio3 / 7
Problem 2
Selection sort
Implement the following sequence sorting algorithm for n values
A = [a1, . . . , an]: first find the smallest element of A and exchange it with
the element in a1. Then find the second smallest element of A, and
exchange it with a2. Continue in this manner for the first n − 1 elements
of A.
What needs to be changed to obtain a decreasing ordered sequence?
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Additio4 / 7
Solution to Problem 2
Algorithm 2 Find value in a sequence - part 1
Input: n ∈ N, A = [a1, . . . , an] ∈ R
Output: ordered sequence A
for i = 1, . . . , n − 1 do
min ← i
for j = i + 1, . . . , n do
if aj < amin then
min ← j
end if
end for
if min ̸= i then
▷ swapping values is needed only if ai is not already minimum
tmp ← ai ▷ these 3 lines are for swapping values
ai ← amin
amin ← tmp
end if
end for
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Additio5 / 7
Problem 3
Binary addition
Consider two numbers A and B represented in binary as two vectors of bits
A = [a1a2 . . . an] and B = [b1b2 . . . bn] with most significant bit being at
position 1 and least significant one at position n. Write the pseudocode to
perform the addition of the two numbers, such that the result C = A + B
is represented as a n + 1 vector of bits C = [c1c2 . . . cn+1].
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Additio6 / 7
Solution to Problem 3
Input: n ∈ N, A = [a1a2 . . . an], B = [b1b2 . . . bn]
Output: C = A + B, C = [c1c2 . . . cn+1]
carry ← 0
for i = n, n − 1, . . . , 1 do
ci+1 ← (ai + bi + carry) mod 2
if ai + bi + carry ≥ 2 then
carry ← 1
else
carry ← 0
end if
end for
c1 ← carry
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms - Additio7 / 7