Week 02b: Analysis of Algorithms
Analysis of Algorithms |
Running Time | 2/63 |
An algorithm is a step-by-step procedure
Empirical Analysis | 3/63 |
... Empirical Analysis | 4/63 |
Limitations:
Theoretical Analysis | 5/63 |
Pseudocode | 6/63 |
... Pseudocode | 7/63 |
Example: Find maximal element in an array
arrayMax(A): | Input array A of n integers | Output maximum element of A | | currentMax=A[0] | for all i=1..n-1 do | | if A[i]>currentMax then | | currentMax=A[i] | | end if | end for | return currentMax
... Pseudocode | 8/63 |
Control flow
Exercise #1: Pseudocode | 9/63 |
Formulate the following verbal description in pseudocode:
In the first phase, we iteratively pop all the elements from stack S and enqueue them in queue Q, then dequeue the element from Q and push them back onto S.
As a result, all the elements are now in reversed order on S.
In the second phase, we again pop all the elements from S, but this time we also look for the element x.
By again passing the elements through Q and back onto S, we reverse the reversal, thereby restoring the original order of the elements on S.
Sample solution:
while empty(S) do pop e from S, enqueue e into Q end while while empty(Q) do dequeue e from Q, push e onto S end while found=false while empty(S) do pop e from S, enqueue e into Q if e=x then found=true end if end while while empty(Q) do dequeue e from Q, push e onto S end while
Exercise #2: Pseudocode | 11/63 |
Implement the following pseudocode instructions in C
A
int
... swap A[i] and A[j] ...
head
... swap head and head->next ...
S
... swap the top two elements on S ...
int temp = A[i]; A[i] = A[j]; A[j] = temp;
NodeT *succ = head->next; head->next = succ->next; succ->next = head; head = succ;
x = StackPop(S); y = StackPop(S); StackPush(S, x); StackPush(S, y);
The following pseudocode instruction is problematic. Why?
... swap the two elements at the front of queue Q ...
The Abstract RAM Model | 13/63 |
RAM = Random Access Machine
Primitive Operations | 14/63 |
Counting Primitive Operations | 15/63 |
By inspecting the pseudocode …
Example:
arrayMax(A): | Input array A of n integers | Output maximum element of A | | currentMax=A[0] 1 | for all i=1..n-1 do n+(n-1) | | if A[i]>currentMax then 2(n-1) | | currentMax=A[i] n-1 | | end if | end for | return currentMax 1 ------- Total 5n-2
Estimating Running Times | 16/63 |
Algorithm arrayMax
arrayMax
a·(5n - 2) ≤ T(n) ≤ b·(5n - 2)
Hence, the running time T(n) is bound by two linear functions
... Estimating Running Times | 17/63 |
Seven commonly encountered functions for algorithm analysis
... Estimating Running Times | 18/63 |
In a log-log chart, the slope of the line corresponds to the growth rate of the function
... Estimating Running Times | 19/63 |
The growth rate is not affected by constant factors or lower-order terms
... Estimating Running Times | 20/63 |
Changing the hardware/software environment
⇒ Linear growth rate of the running time T(n) is an intrinsic property of algorithm arrayMax
Exercise #3: Estimating running times | 21/63 |
Determine the number of primitive operations
matrixProduct(A,B): | Input n×n matrices A, B | Output n×n matrix A·B | | for all i=1..n do | | for all j=1..n do | | | C[i,j]=0 | | | for all k=1..n do | | | C[i,j]=C[i,j]+A[i,k]·B[k,j] | | | end for | | end for | end for | return C
Exercise #4: Estimating running times | 22/63 |
matrixProduct(A,B): | Input n×n matrices A, B | Output n×n matrix A·B | | for all i=1..n do 2n+1 | | for all j=1..n do n(2n+1) | | | C[i,j]=0 n2 | | | for all k=1..n do n2(2n+1) | | | C[i,j]=C[i,j]+A[i,k]·B[k,j] n3·5 | | | end for | | end for | end for | return C 1 ------------ Total 7n3+4n2+3n+2
Big-Oh |
Big-Oh Notation | 24/63 |
Given functions f(n) and g(n), we say that
if there are positive constants c and n0 such that
... Big-Oh Notation | 25/63 |
Example: function 2n + 10 is O(n)
|
|
... Big-Oh Notation | 26/63 |
Example: function n2 is not O(n)
|
Exercise #5: Big-Oh | 27/63 |
Show that
Big-Oh and Rate of Growth | 29/63 |
f(n) is O(g(n)) | g(n) is O(f(n)) | |
g(n) grows faster | yes | no |
f(n) grows faster | no | yes |
same order of growth | yes | yes |
Big-Oh Rules | 30/63 |
Exercise #6: Big-Oh | 31/63 |
Show that `sum_(i=1)^n i` is O(n2)
which is O(n2)
`sum_(i=1)^ni = (n(n+1))/2 = (n^2+n)/2`
Asymptotic Analysis of Algorithms | 33/63 |
Asymptotic analysis of algorithms determines running time in big-Oh notation:
arrayMax
arrayMax
Example: Computing Prefix Averages | 34/63 |
NB. computing the array A of prefix averages of another array X has applications in financial analysis
... Example: Computing Prefix Averages | 35/63 |
A quadratic alogrithm to compute prefix averages:
prefixAverages1(X): | Input array X of n integers | Output array A of prefix averages of X | | for all i=0..n-1 do O(n) | | s=X[0] O(n) | | for all j=1..i do O(n2) | | s=s+X[j] O(n2) | | end for | | A[i]=s/(i+1) O(n) | end for | return A O(1)
⇒ Time complexity of algorithm prefixAverages1
... Example: Computing Prefix Averages | 36/63 |
The following algorithm computes prefix averages by keeping a running sum:
prefixAverages2(X): | Input array X of n integers | Output array A of prefix averages of X | | s=0 | for all i=0..n-1 do O(n) | s=s+X[i] O(n) | A[i]=s/(i+1) O(n) | end for | return A O(1)
Thus, prefixAverages2
Example: Binary Search | 37/63 |
The following recursive algorithm searches for a value in a sorted array:
search(v,a,lo,hi): | Input value v | array a[lo..hi] of values | Output true if v in a[lo..hi] | false otherwise | | mid=(lo+hi)/2 | if lo>hi then return false | if a[mid]=v then | return true | else if a[mid]<v then | return search(v,a,mid+1,hi) | else | return search(v,a,lo,mid-1) | end if
... Example: Binary Search | 38/63 |
Successful search for a value of 8:
... Example: Binary Search | 39/63 |
Unsuccessful search for a value of 7:
... Example: Binary Search | 40/63 |
Cost analysis:
search()
a[i..j]
j<i
a[i..j]
i≤j
... Example: Binary Search | 41/63 |
Why logarithmic complexity is good:
Math Needed for Complexity Analysis | 42/63 |
Exercise #7: Analysis of Algorithms | 43/63 |
What is the complexity of the following algorithm?
splitList(L): | Input non-empty linked list L | Output L split into two halves | |// use slow and fast pointer to traverse L | slow=head(L), fast=head(L).next | while fast≠NULL ∧ fast.next≠NULL do | slow=slow.next, fast=fast.next.next// advance pointers | end while | cut L between slow and slow.next
Answer: O(|L|)
Exercise #8: Analysis of Algorithms | 45/63 |
What is the complexity of the following algorithm?
binaryConversion(n): | Input positive integer n | Output binary representation of n on a stack | | create empty stack S | while n>0 do | | push (n mod 2) onto S | | n=n/2 | end while | return S
Assume that creating a stack and pushing an element both are O(1) operations ("constant")
Answer: O(log n)
Relatives of Big-Oh | 47/63 |
big-Omega
big-Theta
... Relatives of Big-Oh | 48/63 |
... Relatives of Big-Oh | 49/63 |
Examples:
Complexity Classes | 50/63 |
Problems in Computer Science …
... Complexity Classes | 51/63 |
Computer Science jargon for difficulty:
Generate and Test Algorithms |
Generate and Test | 53/63 |
In scenarios where
It is necessary that states are generated systematically
... Generate and Test | 54/63 |
Simple example: checking whether an integer n is prime
... Generate and Test | 55/63 |
Function for primality checking:
isPrime(n): | Input natural number n | Output true if n prime, false otherwise | | for all i=2..n-1 do// generate | | if n mod i = 0 then// test | | return false// i is a divisor => n is not prime | | end if | end for | return true// no divisor => n is prime
Complexity of isPrime
Can be optimised: check only numbers between 2 and `|__sqrt n__|` ⇒ O(`sqrt n`)
Example: Subset Sum | 56/63 |
Problem to solve ...
Is there a subset S of these numbers with sum(S)=1000?
34, 38, 39, 43, 55, 66, 67, 84, 85, 91, 101, 117, 128, 138, 165, 168, 169, 182, 184, 186, 234, 238, 241, 276, 279, 288, 386, 387, 388, 389
General problem:
... Example: Subset Sum | 57/63 |
Generate and test approach:
subsetsum(A,k): | Input set A of n integers, target sum k | Output true if Σb∈Bb=k for some B⊆A | false otherwise | | for each subset S⊆A do | | if sum(S)=k then | | return true | | end if | end for | return false
... Example: Subset Sum | 58/63 |
Given: a set of n
A
0000
0011
1111
A[i]
A[i]
A[]=={1,2,3,5}
0011
{1,2}
... Example: Subset Sum | 59/63 |
Algorithm:
subsetsum1(A,k): | Input set A of n integers, target sum k | Output true if Σb∈Bb=k for some B⊆A | false otherwise | | for s=0..2n-1 do | | if k = Σ(ith bit of s is 1) A[i] then | | return true | | end if | end for | return false
Obviously, subsetsum1
... Example: Subset Sum | 60/63 |
Alternative approach …
subsetsum2(A,n,k)
(returns true if any subset of A[0..n-1] sums to k; returns false otherwise)
subsetsum2(A,n,k): | Input array A, index n, target sum k | Output true if some subset of A[0..n-1] sums up to k | false otherwise | | if k=0 then | return true// empty set solves this | else if n=0 then | return false// no elements => no sums | else | return subsetsum(A,n-1,k-A[n-1]) ∨ subsetsum(A,n-1,k) | end if
... Example: Subset Sum | 61/63 |
Cost analysis:
subsetsum2()
subsetsum2
... Example: Subset Sum | 62/63 |
Subset Sum is typical member of the class of NP-complete problems
Summary | 63/63 |
Produced: 2 Dec 2018