Algorithmic Patterns
Overview
• Algorithm Efficiency • Solution Strategies
References
• Bruno R. Preiss: Data Structures and Algorithms with Object-Oriented Design Patterns in C++. John Wiley & Sons, Inc. (1999)
• Russ Miller and Laurence Boxer: Algorithms Sequential & Parallel – A Unified Approach. 2nd Edition. Charles River Media (2005)
• Stanley B. Lippman, Josée Lajoie, and Barbara E. Moo: C++ Primer. 4th Edition. Addison-Wesley (2006)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms. 2nd Edition. The MIT Press (2001)
406
© Dr Markus Lumpe, 2021
The “Best” Algorithm
• There are usually multiple algorithms to solve any particular problem.
• The notion of the “best” algorithm may depend on many different criteria:
• Structure, composition, and readability • Time required to implement
• Extensibility
• Space requirements
• Time requirements
407
© Dr Markus Lumpe, 2021
Time Analysis
• Example:
Algorithm A runs 2 minutes and algorithm B takes 1 minutes and 45 second to complete for the same input.
• Is B “better” than A? ➠ Not necessarily!:
• We have tested A and B only on one (fixed) input set. Another
input set might result in a different runtime behavior.
• Algorithm A might have been interrupted by another process. • Algorithm B might have been run on a different computer.
• A reasonable time and space approximation should be machine-independent.
408
© Dr Markus Lumpe, 2021
Running Time in Terms of Input Size
•What is the one of most interesting aspect about algorithms?
• How many seconds does it take to complete for a particular input size n?
• How does an increase of size n effect the running time? • An algorithm requires
• Constant time if the running time remains the same as the size n changes,
• Linear time if the running time increases proportionally to size n.
• Exponential time if the running time increases exponentially with respect to size n.
409
© Dr Markus Lumpe, 2021
What is computable?
•Computation is usually modeled as a mapping from inputs to outputs, carried out by a “formal machine”, or program, which processes its input in a sequence of steps.
• An “effectively computable” function is one that can be computed in a finite amount of time using finite resources.
410
© Dr Markus Lumpe, 2021
Abstract Machine Model
• Church’s Thesis: It is not possible to build a machine that is more powerful than a Turing machine.
Problem
“effectively computable function”
yes
no Input Program/Machine Output
411
© Dr Markus Lumpe, 2021
Turing Machine
• A Turing machine is an abstract representation of a computing device. It consists of a read/write head that scans a (possibly infinite) one-dimensional (bi-directional) tape divided into squares, each of which is inscribed with a 0 or 1 (possibly more symbols).
• Computation begins with the machine, in a given “state”, scanning a square. It erases what it finds there, prints a 0 or 1, moves to an adjacent square, and goes into a new state until it moves into HALT.
• This behavior is completely determined by three parameters: • the state the machine is in,
• the number on the square it is scanning, and • a table of instructions.
412
© Dr Markus Lumpe, 2021
Formal Definition of a Turing Machine
• A Turing machine is a septuple (Q, Γ, γ, Σ, q0, F, σ) with:
• a set Q = {q0, q1,…} of states,
• a set Γ is a finite, non-empty set of tape symbols,
• a blank symbol γ ∈ Γ (the only symbol to occur infinitely often)
• a set Σ ⊆ Γ \ { γ } of input symbols (to appear as initial tape contents), • a designated start state q0.
• a subset F ⊆ Q called the accepting states,
• a partial function σ :(Q\F) × Γ → Q × Γ × { R, L } called the transition function.
• A Turing machine halts if it enters a state in F or if σ is undefined for the current state and tape symbol.
413
© Dr Markus Lumpe, 2021
Addition on a Turing Machine
• Σ={“1”, “+”, “ ”} – the tape symbols
Q\Γ
“”
“1”
“+”
1
1/“ ”,R
2/“1”,R
2
2/“1”,R
3/“+”,R
3
4/“+”,L
4
5/“1”,R
5
6/“ ”,L
4/“+”,L
5/“+”,R
6
HALT/“ ”,R
414
© Dr Markus Lumpe, 2021
5+3 on a Turing Machine
1
1
1
1
1
+
1
1
1
Q\Γ “ ” “1” “+”
1 2 3 4 5 6
1/“ ”,R 2/“1”,R
2/“1”,R 3/“+”,R
4/“+”,L
5/“1”,R
6/“ ”,L 4/“+”,L 5/“+”,R
HALT/“ ”,R
Start
1
1
1
1
1
1
1
1
415
End
© Dr Markus Lumpe, 2021
5+3 on a Turing Machine (No Move Allowed)
1
1
1
1
1
+
1
1
1
State/Input
“ ” “1” “0” “+”
0 1 2 3 4 5
-/R/- -/R/1
-/R/- “0”/R/2
-/L/3 -/R/4
“ ”/-/stop
-/L/5 -/R/4
-/L/5 “ ”/-/stop
Start
1
1
1
1
1
1
1
1
416
End
© Dr Markus Lumpe, 2021
The Ackermann Function
• The Ackermann function is a simple example of a computable function that grows much faster than polynomials or exponentials even for small inputs.
• The Ackermann function is defined recursively for non- negative integers m and n as follows:
A(0, n) = n + 1
A(m+1, 0) = A(m, 1)
A(m+1, n+1) = A(m, A(m+1, n))
417
© Dr Markus Lumpe, 2021
Ackermann Function Value Table
A(m,n)
n= 0
n= 1
n= 2
n= 3
n= 4
n= 5
m= 0
1
2
3
4
5
6
m= 1
2
3
4
5
6
7
m= 2
3
5
7
9
11
13
m= 3
5
13
29
61
125
253
m= 4
13
65533
265536-3
2 265536 -3
A(3,A(4,3))
A(3,A(4,4))
m= 5
65533
A(4,65533)
A(4,A(5,1))
A(4,A(5,2))
A(4,A(5,3))
A(4,A(5,4))
m= 6
A(4,65533)
A(5,A(6,0))
A(5,A(6,1))
A(5,A(6,2))
A(5,A(6,3))
A(5,A(6,4))
418
© Dr Markus Lumpe, 2021
Halting Problem
• A problem that cannot be solved by any machine in finite time (or any equivalent formalism) is called uncomputable.
• An uncomputable problem cannot be solved by any real computer. The Halting Problem:
• Given an arbitrary machine and its input, will the machine eventually halt?
• The Halting Problem is provably uncomputable – which means that it cannot be solved in practice.
419
© Dr Markus Lumpe, 2021
The Big-Oh
• An algorithm f(n) is O(g(n)), read “has order g(n)”, if there exist constants C > 0 and integer n0 such that the algorithm f(n) requires at most C*g(n) steps for all input sizes n ≥ n0.
• Example:
• Algorithm A takes 4n + 3 steps, that is, it is O(n).
• Choose C = 5 and n0 = 4, then 4n + 3 < 5n for all n ≥ 4.
f(n)
5n
4n+3
n
420
© Dr Markus Lumpe, 2021
Facts About Big-Oh
• Big-Oh focuses on growth rate as running time of input size approaches infinity (n → ∞).
• Big-Oh does not say anything about the running time on small input.
• The function g(n) in O(g(n)) is a simple function for comparison
of different algorithms:
• 1, n, log n, n log n, n2, 2n, ...
Cg(n)
f(n)= O(g(n)) f(n)
© Dr Markus Lumpe, 2021
421
On Running Time Estimation
• Big-Oh ignores lower-order terms:
Lower order terms in the computation steps count • Big-Oh does not consider the multiplier in
•
functions that are concerned with initialization, secondary arguments, etc.
higher order terms:
These terms are machine-dependent. 422
•
© Dr Markus Lumpe, 2021
Performance Analysis
• Best-Case (Lower Bound):
• The search for a given element A in an array of size n can be O(1),
if the element is the first. (Also applies to binary search trees.)
• Worst-Case (Upper Bound):
• The search for a given element A in an array of size n is O(n), if the element is the last in the array. (For binary search trees, it is also O(n), if the element is the last in a totally unbalanced binary search tree, but O(log n) for a balanced search tree.)
• Average-Case:
• The search for a given element A in an array of size n takes on
average n/2, whereas the lookup in a binary search tree is O(log n).
423
© Dr Markus Lumpe, 2021
Constant Time
• Algorithm A requires 2,000,000 steps: O(1)
• As a young boy, the later mathematician Carl Friedrich Gauss was asked by his teacher to add up the first hundred numbers, in order to keep him quiet for a while. As we know today, this did not work out, since:
sum(n) = n(n+1)/2
which is O(1).
424
© Dr Markus Lumpe, 2021
How does Gauss’s formula work?
1 + 2 + 3 + 4= ?
425
© Dr Markus Lumpe, 2021
Let’s look at the whole rectangle.
2 x (1 + 2 + 3 + 4) = 4 x 5
426
© Dr Markus Lumpe, 2021
So, we have ...
1 + 2 + 3 + 4 = (4 x 5) / 2
427
© Dr Markus Lumpe, 2021
We generalize ...
1 + 2 + ... + n = n x (n + 1) / 2
428
© Dr Markus Lumpe, 2021
We focus on the growth rate n → ∞
n x (n + 1) / 2 is O(1)
429
© Dr Markus Lumpe, 2021
Polynomial Time
• 4n2 + 3n + 1:
Ignore lower-order terms: 4n2 Ignore constant coefficients: O(n2)
• aknk + ak-1nk-1 + ... + a1n + a0 = O(nk)
• •
430
© Dr Markus Lumpe, 2021
Logarithmic & Exponential Functions
• log10 n = log2 n/log2 10 = O(log n):
Ignore base: log10 n
• 345n4536 + n(log n) + 2n = O(2n):
Ignore lower-order terms 345n4536 and n(log n)
•
•
431
© Dr Markus Lumpe, 2021
Towers of Hanoi: The Recursive Procedure
procedure TON( n, S, T, M ) begin
if n > 0 then
TON( n-1, S, M, T )
end
d(T) ← d(S)
TON( n-1, M, T, S )
432
© Dr Markus Lumpe, 2020
Towers of Hanoi Complexity
• The body of TON requires T(n) = 2T(n-1) + 1 operations, for an input size n.
• We have
• T(n-1) = 2T(n-2) + 1 = 2*(2T(n-3) + 1) + 1 = 22T(n-3) + 21 + 1
• T(n-2) = 2T(n-3) + 1 = 2*(2T(n-4) + 1) + 1 •…
• T(2) = 2T(1) + 1 = 2(21 + 1) + 1 = 22 + 21 + 1
• T(1) = 2T(0) + 1 = 21 + 1
• T(0) = 1
• Solving the recursive equations, we obtain
• T(n) = 2n + 2(n-1) + … 21 + 1 = 2(n+1) – 1 = O(2n)
433
© Dr Markus Lumpe, 2020
A Simple Example
➠ 2n + 8 = O(n)
• We count the computation units in each line: • line 2: Zero, the declaration requires no time.
• line 4 & 9:One time unit each.
• line 6: Hidden costs for initializing i, testing i <= n, and incrementing i; 1 time unit initialization, n+1 time units for all tests, and n time units for all increments: 2n + 2.
• line 7: 4 time units, two multiplications, one addition, and one assignment.
434 © Dr Markus Lumpe, 2021
Ranking of Big-Oh
• Fastest: O(1) O(log n)
O(n)
O(n log n) O(n2)
O(n2 log n) O(n3)
O(2n) • Slowest: O(n!)
435
© Dr Markus Lumpe, 2021
General Rules
436
© Dr Markus Lumpe, 2021
For Loops
• The running time for a for loop is at most the running time of the statement inside the for loop times the number of iterations.
• Let C be the running time of statement. Then a for loop has a running time of at most Cn or O(n).
for ( initializer; condition; expression ) statement
• For loops have a linear running time. 437
© Dr Markus Lumpe, 2021
Nested For Loops
for ( initializer1; condition1; expression1 ) for ( initializer2; condition2; expression2 )
statement
• The running time for a for nested loop is at most the running time of the statement multiplied by the product of the sizes of all the for loops.
• Let C be the running time of statement. Then a nested for loop has a running time of at most Cn*n or O(n2).
• Nested for loops have quadratic running time. Any additional nesting level adds one factor. A k-nested loop requires polynomial
time or O(nk).
438
© Dr Markus Lumpe, 2021
Consecutive Statements
• The running time for consecutive statements is the sum of each statement.
• Let mi be the running time of each statement. Then consecutive statements have a running time of at most m1 + m2 + ... mn or O(m) where m = max(m1, m2, ..., mn).
statement1; statement2; ... statementn;
439
© Dr Markus Lumpe, 2021
If-Then-Else Branching
• The running time for an if-then-else statement is at most the running time of the condition plus the larger of the running times of the true-statement and the false-statement.
• This can be an overestimate in some cases, but it is never and
underestimate.
if ( condition ) true-statement
else
false-statement
440
© Dr Markus Lumpe, 2021
Maximum Subsequence Sum Problem in O(n3)
441
© Dr Markus Lumpe, 2021
Maximum Subsequence Sum Problem in O(n)
442
© Dr Markus Lumpe, 2021
Running Time T (Algorithm)
• Test environment: MacPro, 2.66 GHz Quad-Core Intel Xeon
• Algorithm A - O(n3):
• n = 2,000: T(A) = 5s
• n = 5,000: T(A) = 72s
• n = 10,000: T(A) = 579s
• Algorithm B - O(n):
• n = 2,000: T(B) < 1s
• n = 5,000: T(B) < 1s
• n = 10,000: T(B) < 1s
1000
800
600
400
200
0
Number of iterations in Millions
0 200 400n600 800 1000
BA
443
© Dr Markus Lumpe, 2021
Algorithmic Patterns
• Direct solution strategies:
• Brute force and greedy algorithms
• Backtracking strategies:
• Simple backtracking and branch-and-bound algorithms
• Top-down solution strategies: • Divide-and-conquer algorithms
• Bottom-up solution strategies: • Dynamic programming
• Randomized strategies: • Monte Carlo algorithms
444
© Dr Markus Lumpe, 2021
Brute-force Algorithms
• Brute-force algorithms are not distinguished by there structure.
• Brute-force algorithms are separated by their way of solving problems.
• A problem is viewed as a sequence of decisions to be made. Typically, brute-force algorithms solve problems by exhaustively enumerating all the possibilities.
445
© Dr Markus Lumpe, 2021
Bubble Sort
• Bubble sort uses a nested loop to sort an array in increasing order.
• Bubble sort is O(n2). It works fine on small arrays, but it is unsuitable on larger data sets. © Dr Markus Lumpe, 2021
446
Greedy Algorithms
• Greedy algorithms do not really explore all possibilities. They are optimized for a specific attribute.
• Example: Knapsack Problem • Profit - Maximal value of items
• Weight - Maximal weight stored first • Density - Maximal profit per weight
• Greedy algorithms produce a feasible solution, but do not guarantee an optimal solution.
447
© Dr Markus Lumpe, 2021
Sudoku Solver: Greedy
1. Find M[i,j] with the minimal number of choices. 2.Let C be the possibilities for M[i,j].
3.Set M[i,j] to first element of C.
4.Solve puzzle recursively with new configuration. 5.If 4. succeeds, then report result and exit.
6.If 4. fails, then set M[i,j] to next element if C. If there is no more element, then report error.
7. Continue with 4.
448
© Dr Markus Lumpe, 2021
Sudoku
A hard puzzle:
5
8
7
9
1
3
6
9
8
4
6
3
1
2
3
6
5
1
7
1
9
2
2
4
9
6
3
8
3,5,7,8
449
© Dr Markus Lumpe, 2021
Divide-and-Conquer
• Top-down algorithms use recursion to divide- and-conquer the problem space.
• This class of algorithms has the advantage that not all possibilities have to be explored.
• Example: Binary Search, Merge Sort, Quick Sort
450
© Dr Markus Lumpe, 2021
Insert 8:
<
1.
8 < 25
10 37
8
25 15 30 65 10 37
15 30 65
2.
25
10 37
8 15 30 65
2 steps required!
451
© Dr Markus Lumpe, 2021
Binary Search: O(log n)
log(10) = 2.3
452
© Dr Markus Lumpe, 2021
Backtracking Algorithms
• A backtracking algorithm systematically considers all possible outcomes for each decision.
• Backtracking algorithms are distinguished by the way in which the space of possible solutions is explored. Sometimes a backtracking algorithm can detect that an exhaustive search is unnecessary.
• Example: Knapsack Problem 453
© Dr Markus Lumpe, 2021
Sudoko Solver: Backtracking
1. Find M[i,j] with the minimal number of choices. 2.Let C be the possibilities for M[i,j].
3.Set M[i,j] to first element of C.
4.Solve puzzle recursively with new configuration. 5.If 4. succeeds, then report result and exit.
6.If 4. fails, then set M[i,j] to next element if C. If there is no more element, then report error.
7. Continue with 4.
454
© Dr Markus Lumpe, 2021
Bottom-up
• Bottom-up algorithms employ dynamic programming. • Bottom-up algorithms solve a problem by solving a
series of subproblems.
• These subproblems are carefully devised in such a way that each subsequent solution is obtained by combining the solutions to one or more of the subproblems that have already been solved.
• Example: Parsing, Pretty-Printing 455
© Dr Markus Lumpe, 2021
Fast Fibonacci
• The iterative solution of the Fibonacci function has its origin in dynamic programming.
• We define the Fibonacci sequence as a table with two elements: the previous value and the current value. In each step we compute the next
value by adding the table entries.
456
© Dr Markus Lumpe, 2021
Randomized Algorithms
• Randomized algorithms behave randomly.
•Randomized algorithms select elements in an random order to solve a given problem.
•Eventually, all possibilities are explored, but different runs can produce results faster or slower, if a solution exists.
• Example: Monte Carlo Methods, Simulation 457
© Dr Markus Lumpe, 2021
Sorting by Fisher&Yates
• There is at least one configuration that satisfies the sorting criterion, but the use of the Fisher&Yates shuffling process
makes this algorithm O(n*n!). It is called “Bogosort.” 458
© Dr Markus Lumpe, 2021
This is only the beginning
459
© Dr Markus Lumpe, 2021