CS计算机代考程序代写 data structure c++ algorithm Algorithmic Patterns

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