Basic notions of

algorithmics

Piotr Chrząstowski-Wachtel
Uniwersytet Warszawski

Algorithmics



The most important part of computer

science



Describes



how to solve the algorithmic problems,



how to choose appropriate data structures



how to analyse program behavior



Results in the most spectacular
improvements of computer
performance!

What is algorithmics about?



Any planning – in particular writing

computer programs



We must remember that computers

must have a rigid and precise

interface. They are quite stupid

machines in general, and will not

deduce anything as humans use to

do.

The roots of algorithmics



The first known people

who made a scientific

approach to algorithmic

solutions were the

Ancient Greeks



The first algorithmic

problems thoroughly

investigated were the

geometric constructions

Plato

Geometric constructions

(Plato's approach)



The aim is to determine certain

objects on a plane (points, lines and

circles), satisfying some given

properties.



Example problem:



Given a circle o(O,r) and a point A outside

the circle, draw a tangent line crossing A.

Is such solution legal?



We position the compass' needle in A,

and rotate the ruler around it until the

first point of a circle shows up.



We draw a line connecting A with this

point.

Plato forbid such operations



... like sliding or rotating a ruler, and

many others, like drawing a parabola,

spiral, using the 3rd dimension and

many others.



What is allowed then?

Domain of geometric
constructions



We focus on 3 kinds of objects: points,

lines and circles



On these objects only 5 operations are

legal.

Legal geometric operations



For 2 points draw a line crossing them,



For 2 points draw a circle, having a center in

one of them and crossing the other one,



For 2 lines determine their intersection point



For a line and a circle, determine their

common points



For 2 circles, determine their common points



... and nothing more!

Notation for legal operations



Let's invent the names for the legal operations



l := line(X,Y) – line containing points X and Y



o:= circle(O,Y) – circle with center O and radius OY



X := l  k – point od intersection of lines l and k



(X,Y) := l o – points of intersection of line l and circle o



(X,Y) := o1  o2 – point od intersection of circles o1 and
o2



All these operations are partial – they are detertmined only
if arguments are sensible.

The tangent problem
solution



We present here the solution of the problem to draw

a tangent line to a given circle o(O,Y) and point A

:



l := line(O,A) – line l connects circle's center with the point A



o1:= circle(O,A) – circle with center O and radius OA



o2:= circle(A,O) – circle with center A and radius AO



(P,Q) := o1  o2 – points of intersection of o1 and o2



k := line(P,Q) – k is the perpendicular bisector of segment
OA



X := l  k – center of OA



o3 := circle (X,O) – circle with the center X and radius XO



(R,S) := o  o3 – intersection points of o and o3



s := line(R,A) – line s is one of the 2 tangent lines

Compact version of the
solution



We can present it shortly:



s := line((o 

1

(circle((line(O,Y) 

line(circle(A,O))  circle(O,A)),O))),A)



by





we mean here the first of two intersection

points



... this is more or less how the functional

programming looks like

Non-solvable problems



Ancient Greeks could not solve the following
three problems algorithmically within the given
framework:



determine the side of a square of equal area
to a given circle (squaring a circle)



divide an angle to 3 equal parts (angle
trisection)



determine the side of a cube which has the
volume twice as big as the given one (cube
doubling)

Unsolvability of some
geome-trical construction
problems



In 19th century it was rigourously proven that

none of the presented 3 problems can be solved!



Maybe it is so, because we have too few and too

primitive operations?



But if we add some more operations will new

unsolvable problems arise?

Unsolvable problems



Much later (20th century) Alan
Turing showed that there exist
algorithmic problems, which are
generally unsolvable by any
computer, no matter how
powerful it is!

Post correspondence
problem



Example:



x

1

=abb y

1

=a



x

2

=b y

2

=abb



x

3

=a y

3

=bb



Does there exist a sequence of indices i1,i2,…,in,

such that x

i1

…x

in

=y

i1

…y

in

?



Post correspondence problem is

unsolvable

! However,

for many cases the answer can be given (like for the

above example). There does not exist a general

algorithm, which for any input data x

1

,...,x

n

i y

1

,...,y

n

would determine, if one can equalize the words by

the same sequence of indices.

Emil Post

Where does the word

"algorithm” come from?



It must be an old word, because in

many languages sound similar.

Al Khwarizmi



Abu Ja'far Muhammad
ibn Musa Al-Khwarizmi
(ok. 780 – ok. 850)



Hisab al-jabr w'al-
muqabala



Described interesting
methods to solve
equations by means of
algorithmic methods!



Introduced the decimal
system

An example from Al
Khwarizmi book



We solve the equation
x

2

+10x=39



What are we allowed to
do?



Use only natural numbers
(segment length)



add and subtract segments



multiply (making rectangles)



taking square roots (determining
the side length of a square with
the given area)

S=64

hence x=3

An example from Euclid



Determine the Greatest Common
Divisor GCD(m,n)



What are we allowed to do? The same as
previously, in particular:



use only natural numbers



add and subtract them

Euklides

GCD(m,n)



There is no formula for GCD(m,n), which
would work for any m and n.



Euclid proved that if we subtract the
smaller number from the greater one,
their GCD will remain the same.

GCD(m,n) for 0



m



n,

n>0



The first idea:



The following pseudo-code will do the job:



Input(m,n);



While m>0 do



begin



if m>n then Exchange(m,n);



n:=n-m



end;



Output(n)

Euclid 



If m=0 then GCD(m,n)=n



If m>0 then GCD(m,n)=GCD(n –

m,m)

Do we see the problem?



How long would it take to perform the
code for a computer with 1THz clock for
n=10

30

and m=1?



if n=10

9

and m=1, then it would take ca

1/40 s.



But 10

21

/40s = more than 790 billion

years! Few dozens as much as our
Universe exists!



In RSA cryptography the numbers used
are of order 10

200.

Should we give up?



Let's look more closely, how our algoritms
works.



Subtracting the smaller number m from the bigger n
ends, when the result is smaller than m.



What remains is nothing but the remainder from the
divisioin n by m.



This is the moment, when the number roles are
exchanged: m becomes the bigger number, and n –
smaller.



So all the subtraction does nothing more than just
determining the remainder!

Can't we determine the
remainder faster?



Definitely we can – for instance by performing
the written division.



So we can modify our algorithm:

Euclid 2



If m=0 then GCD(m,n)=n



If m>0 then GCD(m,n)=GCD(n mod m,

m),

•where mod stands for the remainder

Code of Euclid 2



We can program the algorithm using the
following pseuo-code:



Input(m,n);



While m>0 do



begin



r := n mod m;



n := m;



m := r



end;



Output(n)

Have we won anything?



This time the worst data will not be  and the
greatest number in the given range. The
remaider would then be 0, and the algorithm
would terminate after one loop turn.



Let's try to determine data, for which Euclid2
will perform the greatest number of loops.



What are the worst data for 30-digit numbers?

Pessimistic complexity



... is the number of operations that algorithm
will perform for the most evil data.



We should determine the range of data we are
looking for the most pessimistic one.



Let's calm down. What are the worst data for
Euclid2 in the range ..99?

Pessimistic complexity of
Euclid2



Let's ask the question from the other side.
Instead of asking what the worst data are, let's
ask how big the data should be at least, in
order to enforce the given number of loop turn.



Let's start with the small values. What are the
smallest data which will enforce 0 loop turns?
Clearly (1,0). For 1 loop turn (1,1). For 2 loop
turns we need at least the numbers (2,3),
because the divisor should be greater than ,
and the denominator greater than the divisor.

..Complexity of Euclid2



The next values are:



3 loop turns: (3,5), because in order to get "the
cheapest" 2 turns – the pair (2,3) – the divisor
should be 3, and the smallest divident giving for
that divisor the remainder 2 is 5.



4 loop turns: (5,8); divisor 5 and divident 5+3=8



5 loop turns: (8,3); because 3=8+5



...and so on



In each of the cases, the quotient is 

..Complexity of Euclid2



The record is (55,89) – 9 loop turns:



(55,89)



(34,55)



(2,34)



(3,2)



( 8,3)



( 5, 8)



( 3, 5)



( 2, 3)



( , 2)



( 0, )

Looking at the right column we see that:

•one cannot make 2 loop turns with numbers less

than 3,

•one cannot make 3 loop turns with numbers less

than 5

•,..

•one cannot make 9 loop turns with numbers less

than 89

and so on...

Fibonacci numbers



So the worst numbers in each row are such that the
smaller of them is equal to the greater one from below,
and the greater one is the sum of the two below numbers.



(

55,89)



(34,55)



(2,34)



(3,2)



( 8,3)



( 5, 8)



( 3, 5)



( 2, 3)



( , 2)



( 0, )

The numbers in one column form

the so called Fibonacci sequence

F

0

= 0, F

1

= 1,

F

n

= F

n-1

+ F

n-2

for

n>1

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...

Leonardo Fibonacci

Fibonacci numbers



Here are the numbers of loop turns for given pairs of 2
Fibonacci numbers:



(

F

10

,F

11

) 9 turns



(F

9

,F

10

) 8 turns



(F

8

,F

9

) 7 turns



(F

7

,F

8

) 6 turns



(F

6

,F

7

) 5 turns



(F

5

,F

6

) 4 turns



(F

4

,F

5

) 3 turns



(F

3

,F

4

) 2 turns



(F

2

,F

3

)  turn



(F

0

,F

1

) 0 turns

From (F

n-1

,F

n

) for n>2

we obtain n-2 loop turns.

Fibonacci numbers



Among the 30-digit numbers the worst for
Euclid2 are the 2 biggest Fibonacci numbers
within this range.



The index of the greater of them minus 2
equals to the biggest number of loop turns
within this range.



The key question is how fast they grow?



If fast, then good! Because the number index
will be small.

Fibonacci numbers



Fibonacci himself was unable to determine a
formula for "his" numbers. But such formula
exists!



The formula was discovered by Leonard Euler
in the 8th century, and later re-discovererd
by Jacques

Binet in the 9th

century.

Euler-Binet formula

Leonard Euler

Jacques Binet

Conslusions from Euler-Binet

formula:



Let's introduce the notation



These numbers are equal to ca. 1.618... and

-0.618... . The Euler-Binet formula takes the form



Now getting rid of the second component, which

soon becomes close to 0, we get a simplified

formula:

Fibonacci numbers grow

exponentially fast!



So from some moment each Fibonacci

number is greater more than 60% than

the previous one.



Since we want to find the greatest

Fibonacci number less that 10

30

, we wish

to solve the inequality





n

/



5 < 10

30

, and after taking logarithm

with base  we get n-2 < 30log



10 =

148,33...



Finally n150.

We have won!



It turns out that even for such enormous

data as 30-digit numbers, the number of

loop turns will not exceed 150.



There is however one difficulty:

programming the mod operation is more

challenging that simple subtraction.



... but who claims that programming is

easy?

Important aspects



Algorithmic domain



Before we start designing algorithms, we

should be aware of the exact set of

objects and operations we wish to build

our algorithm of.



For geometrical constructions they were

points, lines, and circles together with 5

operations we admitted.

Algorithmic domains for Euclid

algorithms



In both Euclid algorithms we used a

different set of operations:



Euclid1: (N, , –, Exchange )



Euclid2: (N, >

0

, mod )

Algorithmic domain



The basic notion of an algorithmic

domain is the set together with

specified operations and relations – a

relational system



where A is the carrier, and the sets



are the sets of operations and relations

on the carrier

Structural programming



When we program in a structured way,

we create hierarchical domains, letting

the higher-level domains use the

operations of lowel-level domains.



On none of the levels we want to be

engaged with unnecessary details.



Such programming style is

characteristic to the languages of

newer generations (object-orientation,

logic and functional programming).

Computational complexity



This is the second important notion of

algorithmics.



We consider the number of

operations, which we call a

computational cost.



We can apply it to



a concrete algorithm



an algorithmic problem.

What do we count?



It would be hard to focus on each

operation.



Instead we choose the most frequent

operation and the most expensive one,

and concentrate on counting the number

of executions of such operation for some

data.



The number of all other operations is

limited by a linear function. The size of

each program is finite!

Pessimistic and average

complexity



Most commonly we consider 2 types

of data:



worst data (pessimistic complexity)



typical data (average complexity)

Space complexity



Sometimes we need additional

memory (like in the Eratosthenes

sieve). The amount of such memory is

called space complexity. Again we

distinguish:



pessimistic space complexity



average space complexity

Complexity of a problem



Complexity of a problem is the

complexity of the best algorithms in a

given class solving this problem. Here

we can distinguish:



pessimistic problem complexity



average problem complexity

Computational complexity



So we have 3 categories of

complexity:

time – memory

pessimistic – average

algorithm – problem

Data size



We determine the data size by the

number of bits required to represent

the input data.



for arrays – their length



for numbers – the number of digits



for graphs – the sum of the number of

nodes and edges

Conclusion



Algorithmics is the essence of computer

science



It is important, what algorithm we

choose. Even the fastest computers can

be useless if we choose a bad algorithm.



It is always a good idea to consider a

structural approach and to determine

the cost of the solution.