E2011: Theoretical fundamentals of computer science
Introduction to algorithms – part II
Vlad Popovici, Ph.D.
RECETOX
Outline
1 Review of pseudocode constructs
2 Basic data structures
3 Exercises
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II2 / 21
Pseudocode
variables - store some values (e.g. x, y); may refer to simple (e.g.
scalar) values, or more complicated data structures (vectors, matrices,
lists, etc.)
input to specify the required values for the algorithm to compute the
output
variables are assigned values: x ← 50 or x ← y, but values are never
assigned variables or other values: 50 ← x is a nonsense
mathematical operators can be used as usual
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II3 / 21
Branching - conditional execution
if ⟨condition⟩ then
code for ⟨condition⟩ is True
[
else
code for ⟨condition⟩ is False
]
end if
”else” branch is optional
one can use ”continue” to force quitting a loop or ”next” to force
jumping to the next iteration within a loop
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II4 / 21
Loops
Repeat as long as the
condition is true:
while ⟨condition⟩ do
instruction
...
end while
Repeat as long as the
condition is false:
repeat
instruction
...
until ⟨condition⟩
Repeat for all values in
a series:
for ⟨iterator⟩ do
instructions
end for
for all ⟨iterator⟩ do
instructions
end for
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II5 / 21
Subroutines
Procedures
procedure ⟨name⟩(⟨params⟩)
block
end procedure
may change the values of the
parameters
use return to cause immediate
exit from the procedure
Functions
function ⟨name⟩(⟨params⟩)
body
return value
end function
does not change the values of
the parameters
returns a computed value
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II6 / 21
Vectors and arrays
may contain ≥ 0 elements
all elements have the same type (e.g. N, R)
each element is addressble by an index - e.g. i ∈ N∗ or i, j ∈ N∗
the indexing induces an order among the elements
for the purpose of this introductory course, we stick to single element
addressing
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II7 / 21
x ∈ Rn
: [xi ]; M ∈ Mm×n(R) : [mij ]; A ∈ Rn
× Rm
× Rp
x xix1 xn
M mij
A
aijk
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II8 / 21
Arrays - access patterns - examples
Access all [xi ]
sequentially:
for i = 1, 2, . . . , n do
work with xi
. . .
end for
Access all elements in odd-numbered columns:
for j = 2k + 1, k = 1, . . . , ⌊(n − 1)/2⌋ do
for i = 1, . . . , m do
work with mij
. . .
end for
end for
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II9 / 21
Sets
bag of elements, usually of the same type
no inherent ordering
needs an element selection strategy to be specified
you can use sets operations to make things clear(er)
e.g. A ⊂ Z, |A| = n
if asked to detail some operation (e.g. union), then you need to
describe the algorithm, not only say ”A ∪ B”
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II10 / 21
Problem 1
Find the minimum and maximum of a (a) vector, (b) matrix, and (c) set
of real numbers.
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II11 / 21
Solution 1(a)
Input: x = [xi ] ∈ Rn
Output: xmin = mini (x); xmax = maxi (x)
xmin ← x1; xmax ← x1 ▷ initial values
for i = 2, . . . , n do
if xi > xmax then
xmax ← xi ▷ a larger value was found
end if
if xi < xmin then
xmin ← xi ▷ a smaller value was found
end if
end for
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II12 / 21
Solution 1(b)
Input: X = [xij ] ∈ Mm,n(R)
Output: xmin = minij (X); xmax = maxij (X)
xmin ← x11; xmax ← x11 ▷ initial values
for i = 1, . . . , m do
for j = 1, . . . , n do
if xij > xmax then
xmax ← xij ▷ a larger value was found
end if
if xij < xmin then
xmin ← xij ▷ a smaller value was found
end if
end for
end for
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II13 / 21
Solution 1(c)
Input: A ⊂ R, A ̸= ∅
Output: amin = min(A); amax = max(A)
amin ← ∞; amax ← −∞ ▷ initial values
while A ̸= ∅ do
a ← pick random element from A
if a > amax then
amax ← a ▷ a larger value was found
end if
if a < amin then
amin ← a ▷ a smaller value was found
end if
A ← A \ {a} ▷ remove the element from A
end while
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II14 / 21
Problem 2
Given a vector of real numbers, sort its elements in increasing order.
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II15 / 21
Solution 2 (Bubble sort)
Input: x = [xi ] ∈ Rn
Output: sorted x
repeat
swapped ← False
for i = 1, . . . , n − 1 do
if xi > xi+1 then
t ← xi ▷ need to swap xi and xi+1
xi ← xi+1
xi+1 ← t
swapped ← True
end if
end for
until not swapped
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II16 / 21
Problem 3
Given a real-valued vector x, compute the (sample-based) estimates of the
mean and standard deviation.
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II17 / 21
Solution 3 - first version
Use ˆµ = 1
n i xi ; ˆσ2 = 1
n−1 i (xi − ˆµ)
2
Input: x = [xi ] ∈ Rn
Output: m - the mean; σ - the standard deviation
m ← 0
for i = 1, . . . , n do
m ← m + xi
end for
m ← m
n
s ← 0
for i = 1, . . . , n do
s ← s + (xi − m)2
end for
σ ← s
n−1
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II18 / 21
Discussion
why not use updates like m ← m + xi
n ?
what happens if n = 1?
what about underflow and precision of the result? how can we
improve the robustness?
can we make it faster - e.g. by passing only once through data?
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II19 / 21
Solution 3 - second version
It can be show (prove it!) that
ˆσ2
=
1
n − 1
i
(xi − µ)2
=
1
n − 1
i
x2
i +
1
n(n − 1)
i
xi
2
Input: x = [xi ] ∈ Rn
Output: m - the mean; σ - the standard deviation
s1 ← 0; s2 ← 0
for i = 1, . . . , n do
s1 ← s1 + xi
s2 ← s2 + x2
i
end for
m ← s1
n
σ ← s2
n−1 +
s2
1
n(n−1)
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II20 / 21
Questions?
Vlad Popovici, Ph.D. (RECETOX) E2011: Theoretical fundamentals of computer science Introduction to algorithms – part II21 / 21