E2011: Theoretical fundamentals of computer science
Introduction to algorithms
Vlad Popovici, Ph.D.
Fac. of Science - RECETOX
Outline
1 Algorithms
Pseudocode
2 Analysis of algorithms
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 2 / 29
Physics: electrons
Transistors, diodes -
devices
Analog circuits:
amplifiers, filters
Logic: adders,
memory
Digital circuits: gates
Microarchitecture:
data paths,
controllers
Architecture:
instructions,
registers
Operating system:
device drivers,
kernels
Application software:
programs
Abstraction
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Basic concepts about operating systems3 / 16Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 3 / 29
Algorithm
a step-by-step procedure to solve a task/problem
word algorithm originates from the Latin version of the name
Muh.ammad ibn M¯us¯a al-Khw¯arizm¯ı (IX-th century) - a highly
influential Arab mathematician
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 4 / 29
an algorithm has an input and an output
the procedure describes how the input is used to obtain the output
attributes of an algorithm:
▶ correctness
▶ efficiency
▶ complexity
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 5 / 29
Example - Greatest Common Divisor
(one of the oldest algorithms - Euclid (III-IV centuries BC))
Algorithm 1 Euclid’s algorithm
Input: a, b ∈ N∗
Output: GCD
1: r ← a mod b
2: while r ̸= 0 do ▷ We have the answer if r is 0
3: a ← b
4: b ← r
5: r ← a mod b
6: end while
7: GCD ← b ▷ The gcd is b
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 6 / 29
while r ̸= 0 do
a ← b
b ← r
r ← a mod b
end while
GCD ← b
Example: GCD of a = 72 and b = 120
r a b
before “while” 72 72 120
iteration 1 48 120 72
iteration 2 24 72 48
iteration 3 0 48 24
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 7 / 29
Pseudocode
a means of describing an algorithm
not directly interpretable by a computer; needs to be implemented in
a programming language
has a less strict syntax and vocabulary than a programming language
it is independent on the programming language
shortcuts are allowed if their meaning is clear (e.g.
θ∗ = arg minθ Ω(θ))
describes the solution with enough granularity so it can be
implemented
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 8 / 29
Main ingredients of the 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. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 9 / 29
Main ingredients of the pseudocode
If-then-else structure
specifies the conditional
execution of a part (branch) of
the code
the else part may be missing
the ⟨condition⟩ is a Boolean
predicate that is evaluated to
either True or False (or,
equivalently, to ̸= 0 or 0.)
if ⟨condition⟩ then
code for ⟨condition⟩ is True
else
code for ⟨condition⟩ is False
end if
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 10 / 29
Main ingredients of the pseudocode
While-do loop
specifies a repeated execution of
a set of operations (instruction
block)
the block is executed as long as
the ⟨condition⟩ is True and no
forced exit is encountered
if the condition is False at the
very beginning, the block is not
executed at all
while ⟨condition⟩ do
instruction
...
end while
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 11 / 29
Main ingredients of the pseudocode
Repeat-until loop
specifies a repeated execution of
an instruction block
the block is executed as long as
the ⟨condition⟩ is False and no
forced exit is encountered
the block is executed at least
once
repeat
instruction
...
until ⟨condition⟩
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 12 / 29
Main ingredients of the pseudocode
For loop
executes a block for
a given number of
steps (unless forced
exit is encountered)
typically used with
vectors, lists, etc
for ⟨iterator⟩ do
instructions
end for
for all ⟨iterator⟩ do
instructions
end for
Examples:
sum ← 0
for i = 1, . . . , n do
sum ← sum + xi
end for
for all a ∈ A do
print(a)
end for
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 13 / 29
Main ingredients of the pseudocode
Procedures
groups a set of instructions into a construct that can be invoked
(called) with or without parameters
the parameters may function as input/output or in/out parameters
procedure ⟨name⟩(⟨params⟩)
block
end procedure
Functions
special procedures with only input parameters which returns a value
much like the mathematical equivalent (e.g. sin(x))
function ⟨name⟩(⟨params⟩)
body
return value
end function
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 14 / 29
Main ingredients of the pseudocode
continue: used in loops; indicates a jump to the test condition, any
instructions after it are not executed
break: used in loops; indicates an exit from the loop, continuing
execution with the instruction after the loop
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 15 / 29
√
x with precision ϵ > 0 - binary search
Algorithm 2
√
x via binary search
1: function sqrt1(x ∈ R+, ϵ > 0)
2: low ← 0
3: if x > 1 then
4: high ← x
5: else
6: high ← 1
7: end if
8: while high − low > ϵ do
9: middle = 0.5(high−low)
10: if middle2 > x then
11: high ← middle
12: else
13: low ← middle
14: end if
15: end while
16: return low
17: end function
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 16 / 29
√
x with precision ϵ > 0 - Babylonian method
Algorithm 3
√
x - Babylonian algorithm
1: function sqrt2(x ∈ R+, ϵ > 0)
2: r0 ← x/2 ▷ some initial guess
3: r1 ← (r0 + x/r0)/2
4: while |r1 − r0| > ϵ do
5: r0 ← r1
6: r1 ← (r0 + x/r0)/2
7: end while
8: return r1
9: end function
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 17 / 29
there might be several algorithms for a given problem
the choice of the ”best” algorithm is not always obvious
execution time, memory requirements, implementation options, etc
are factors to keep in mind
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 18 / 29
Flowcharts: alternative to pseudocode
START
END
INPUT:
variables
OUTPUT:
variables
Instruction or
block of
instructions
test
False True
Procedure
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 19 / 29
GCD - with flowchart
Input: a, b ∈ N∗
Output: GCD
1: r ← a mod b
2: while r ̸= 0 do
3: a ← b
4: b ← r
5: r ← a mod b
6: end while
7: GCD ← b
START
INPUT:
a, b positive
integers
r ← a mod b
r = 0
a ← b
b ← r
r ← a mod b
OUTPUT: “GCD
is “, b
END
NO
YES
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 20 / 29
Analysis of algorithms
What’s more important than performance?
modularity
correctness
maintainability
functionality
robustness
user-friendliness
programmer time
simplicity
extensibility
reliability
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 21 / 29
Insertion sort
Problem: sort a sequence of numbers [ai ], i = 1, . . . , N in increasing order.
8 25 6 7
8 25 6 7
82 5 6 7
82 5 6 7
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 22 / 29
Insertion sort
Algorithm 4 Insertion sort
Input: [ai ], i = 1, . . . , N
Output: sorted [ai ]
for j = 2, . . . , N do
key ← aj
i ← j − 1
while i > 0 AND ai > key do
ai+1 ← ai
i ← i − 1
end while
ai+1 ← key
end for
ai
1 Ni j
key
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 23 / 29
Running time analysis
depends on the ordering of the sequence: if it’s ordered already, we
just sweep once through it
idea 1: find the dependency of the running time on the sequence size
idea 2: find the upper limit of the running time
idea 3: ignore machine-dependent part, concentrate on the intrinsic
time
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 24 / 29
Running time analysis - two scenarios
T(n) =?
worst case scenario: gives the upper limit on the running time
average-case: gives the expected running time
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 25 / 29
Running time analysis - asymptotic analysis
Main idea
Study
T(n) as n → ∞
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 26 / 29
”Big-Oh notation” - complexity function
O(g(n)) = {f (n)|∃c1, c2 > 0, n0 ∈ N : 0 ≤ c1g(n) ≤ f (n) ≤
c2g(n), ∀n ≥ n0}
e.g. for polynomial functions, consider just the dominating term:
an3
+ bn2
+ cn + d = O(n3
), ∀a, b, c, d ∈ R
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 27 / 29
Complexity of the insertion sort algorithm
worst case: the sequence is reversed (decreasing order)
T(n) =
n
j=2
O(j) = O(n2
)
average case: consider all permutations of n elements as equally
probable
T(n) =
n
j=2
O(j/2) = O(n2
)
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 28 / 29
Questions?
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Introduction to algorithms 29 / 29