Refresher on algorithms
Louis Jachiet
Louis JACHIET 1 / 14
Optimizing programs
Should you optimize a program?
Louis JACHIET 2 / 14
Should you optimize a program?
Louis JACHIET 3 / 14
Should you optimize a program?
If you have a solution that works and is fast enough. . .
Louis JACHIET 4 / 14
Should you optimize a program?
If you have a solution that works and is fast enough. . . NO.
Also you should only optimize the time-consuming parts of your
program
Louis JACHIET 4 / 14
Should you optimize a program?
If you have a solution that works and is fast enough. . . NO.
Also you should only optimize the time-consuming parts of your
program which means you should measure what takes time.
Louis JACHIET 4 / 14
Why optimize?
If you have a program that is too slow you have three ways of
optimizing it:
• Do some little tweaking
You can go for a 2× speed-up
Louis JACHIET 5 / 14
Why optimize?
If you have a program that is too slow you have three ways of
optimizing it:
• Do some little tweaking
You can go for a 2× speed-up
• Change the language or use a well-optimized library
You can have a 100× speed-up, in a very favorable case
Louis JACHIET 5 / 14
Why optimize?
If you have a program that is too slow you have three ways of
optimizing it:
• Do some little tweaking
You can go for a 2× speed-up
• Change the language or use a well-optimized library
You can have a 100× speed-up, in a very favorable case
• Use multiple computer
n× speed-up with n computers
Louis JACHIET 5 / 14
Why optimize?
If you have a program that is too slow you have three ways of
optimizing it:
• Do some little tweaking
You can go for a 2× speed-up
• Change the language or use a well-optimized library
You can have a 100× speed-up, in a very favorable case
• Use multiple computer
n× speed-up with n computers
• Change the algorithm
No limit on speed-up!
Louis JACHIET 5 / 14
Numbers Everyone Should Know
L1 cache reference 0.5 ns
Branch mispredict 5 ns
L2 cache reference 7 ns
Mutex lock/unlock 25 ns
Main memory reference 100 ns
Compress 1K bytes with Zippy 3 000 ns
Send 2K bytes over 1 Gbps network 20 000 ns
Read 1 MB sequentially from memory 250 000 ns
Round trip within same datacenter 500 000 ns
Disk seek (hard drive) 10 000 000 ns
Read 1 MB sequentially from disk (hard drive) 20 000 000 ns
Send packet CA → Netherlands → CA 150 000 000 ns
Louis JACHIET 6 / 14
Defining algorithmic complexity
Defining algorithmic complexity
Turing machines
Turing machines
Church Turing thesis
Everything that can be computed, can be computed with a Turing
Machine.
Strong Church Turing thesis
Everything that can be computed efficiently, can be efficiently
computed with a deterministic Turing Machine.
Louis JACHIET 7 / 14
Turing machines
In practice
Turing machines are great at modeling large complexity classes P,
EXPTIME, L, etc. but bad for fined-grained complexity.
Example
Testing whether a string contains n times the letter a followed by n
times the letter b cannot be recognized by a deterministic Turing
Machine in linear time.
Louis JACHIET 8 / 14
How to define computational complexity?
In practice
We use a ill-defined, vague but useful notion of RAM-model:
• the memory is divided in register of limited size (64 in actual
computers)
• we have a memory indexed by addresses (this allows for arrays
and pointers)
• we can do basic arithmetic operation (+, −, ×, /, %, etc.)
• all basic operation takes O(1)
Louis JACHIET 9 / 14
Defining algorithmic complexity
Notations
Bachmann-Landau notation
The parameter n
Usually the length of the problem. On TM this is the number of
bits, on RAM machines this is usually the number of machine
words.
• Small o: g(n) = o(f (n)) means g(n)/f (n) tends to 0.
• Big O: g(n) = O(f (n)) means g(n)/f (n) is bounded.
• Big Ω: g(n) = Ω(f (n)) means f (n)/g(n) is bounded, i.e.
f (n) = O(g(n))
• Big Θ: g(n) = θ(n) means ∃c s.t. c −1 < f (n)/g(n) < c.
Louis JACHIET 10 / 14
Bachmann-Landau notation
The parameter n
Usually the length of the problem. On TM this is the number of
bits, on RAM machines this is usually the number of machine
words.
• Small o: g(n) = o(f (n)) means g(n)/f (n) tends to 0.
• Big O: g(n) = O(f (n)) means g(n)/f (n) is bounded.
• Big Ω: g(n) = Ω(f (n)) means f (n)/g(n) is bounded, i.e.
f (n) = O(g(n))
• Big Θ: g(n) = θ(n) means ∃c s.t. c −1 < f (n)/g(n) < c.
• Big Ω̃: g(n) = Ω̃(f (n)) means ∃c s.t. f (n)/g(n) < c for
infinitely many n.
• Big Θ̃: g(n) = Θ̃(f (n)) means ∃c s.t. c −1 < f (n)/g(n) < c
for infinitely many n.
Louis JACHIET 10 / 14
Importance of the constant
The O notation “hides” the actual performance in the constant:
• it is very useful to develop algorithms
• it is generally gives the fastest algorithms
• but there are cases where the constant is huge
However, keep in mind that all computers have a finite memory. . .
Louis JACHIET 11 / 14
Generic algorithmic approach
Know the basics of algorithms
• Divide and conquer
Louis JACHIET 12 / 14
Know the basics of algorithms
• Divide and conquer
• Sliding windows
Louis JACHIET 12 / 14
Know the basics of algorithms
• Divide and conquer
• Sliding windows
• Dynamic algorithms
Louis JACHIET 12 / 14
Know the basics of algorithms
• Divide and conquer
• Sliding windows
• Dynamic algorithms
• Math-trick
Louis JACHIET 12 / 14
Know the basics of algorithms
• Divide and conquer
• Sliding windows
• Dynamic algorithms
• Math-trick
• Reduction of complexity
Louis JACHIET 12 / 14
Know the basics of algorithms
• Divide and conquer
• Sliding windows
• Dynamic algorithms
• Math-trick
• Reduction of complexity
• Data structure
Louis JACHIET 12 / 14
Use the right datastructure
• Array
Louis JACHIET 13 / 14
Use the right datastructure
• Array
• Linked Lists
Louis JACHIET 13 / 14
Use the right datastructure
• Array
• Linked Lists
• Hash table
Louis JACHIET 13 / 14
Use the right datastructure
• Array
• Linked Lists
• Hash table
• Balanced binary tree
Louis JACHIET 13 / 14
Use the right datastructure
• Array
• Linked Lists
• Hash table
• Balanced binary tree
• Queues
Louis JACHIET 13 / 14
Exercises
• Sort a list of integers
• Given two strings, are they anagrams?
• Given a list of pair (people,phone) and a list (people,mail),
what are the people that have both a phone and a mail?
• We define Fn+2 = Fn + Fn+1 with F0 = F1 = 0, how to
compute Fn ?
• Given a list l, compute maxi,j (sum(l[i : j]))
Louis JACHIET 14 / 14