[SOLVED] CS algorithm Introduction / Review

Introduction / Review

Number of transistors double every two years
This trend has slowed a bit, closer to doubling every 2.5 years
Moores Law

Memory: 1 MB
CPU: 2.4 Mhz
First computer

Do you remember how fast the CPU was on your first computer?
How about your current computer? What about your previous computer?
CPU trends

CPU trends

CPU trends

CPU trends

CPU trends

You and your siblings are going to make dinner
How would all three of you make : (1) turkey?
(2) a salad?
Parallel processing (cooking)

Parallel processing (cooking)
If you make turkey.
preheat

Parallel processing (cooking)
If you make turkey.
preheat
WAIT

Parallel processing (cooking)
If you make turkey.
put in turkey

Parallel processing (cooking)
If you make turkey.
put in turkey
WAIT A LOT

Parallel processing (cooking)
If you make turkey.
take out

Parallel processing (cooking)
If you make turkey.
take out
WAIT

Parallel processing (cooking)
If you make a salad
chop grate cut

Parallel processing (cooking)
If you make a salad
chop grate cut

Parallel processing (cooking)
If you make a salad
dump together

To make use of last 15 years of technology, need to have algorithms like salad
Multiple cooks need to work at the same time to create the end result
Computers these days have 4-8 cooks in them, so try not to make turkey
Parallel processing (cooking)

An algorithm is correct if it takes an input and always halts with the correct output.
Many hard problems there is no known correct algorithm and instead approximate algorithms are used
Correctness

What does O(n2) mean? (n2)?
(n2)?
Asymptotic growth

If our algorithm runs in f(n) time, then our algorithm is O(g(n)) means there is an n0 and c such that
0 < f(n) < c g(n) for all n > n0
O(g(n)) can be used for more than run time
Asymptotic growth

f(n)=O(g(n)) means that for large inputs (n), g(n) will not grow slower than f(n)
n = O(n2)? n = O(n)? n2 = O(n)?
Asymptotic growth

f(n)=O(g(n)) gives an upper bound for the growth of f(n)
f(n)=(g(n)) gives a lower bound for the growth of f(n), namely: there is an n0 and c such that
0 < c g(n) < f(n) for all n > n0
Asymptotic growth

f(n)=(g(n)) is defined as:
there is an n0, c1 and c2 such that
0 < c1 g(n) < f(n) < c2 g(n) for all n > n0
Asymptotic growth

Suppose f(n) = 2n2 5n + 7 Show f(n) = O(n2):
Asymptotic growth

Suppose f(n) = 2n2 5n + 7 Show f(n) = O(n2):
we need to find c and n0 so that
c n2 > 2n2 5n + 7, guess c=3
3 n2 > 2n2 5n + 7
n2 > 5n + 7 (RHS is decreasing) so c=3 and n0=2 proves this
Asymptotic growth

Suppose f(n) = 2n2 5n + 7 Show f(n) = (n2):
For any general f(n) show: f(n)=(g(n)) if and only if f(n)=O(g(n)) and f(n)=(g(n))
Asymptotic growth

Suppose f(n) = 2n2 5n + 7 Show f(n) = (n2):
again we find a c and n0
cn2 < 2n2 5n + 7, guess c=11 n2 < 2n2 5n + 70 < n2 -5n +7, or n2 > 5n -7
n > 4, so c=1 and n0=4 proves this
Asymptotic growth

f(n)=(g(n)) implies
f(n)=O(g(n)) and f(n)=(g(n)):
by definition we have c1, c2, n0 so
0 < c1 g(n) < f(n) < c2 g(n) after n0 0 < c1 g(n) < f(n) after n0 is (g(n)) 0 < f(n) < c2 g(n) after n0 is O(g(n))Asymptotic growthf(n)=O(g(n)) and f(n)=(g(n)) implies f(n)=(g(n)):by definition we have c1, c2, n0, n1(g(n)) is 0 < c1 g(n) < f(n) after n0 O(g(n)) is 0 < f(n) < c2 g(n) after n1 0 < c1 g(n) < f(n) < c2 g(n) after max(n0,n1)Asymptotic growthThere are also o(g(n)) and w(g(n)) but are rarely usedf(n)=o(g(n)) g(n) grows much faster than f(n), specifically:lim(n) f(n)/g(n) = 0 w(g(n)) is the opposite of o(g(n))Asymptotic growthBig-O notation is used very frequently to describe run time of algorithmsIt is fairly common to use big-O to bound the worst case and provide empirical evaluation of runtime with data Asymptotic growthWhat is the running time for n (less than 300) people on the following: 1. Does anyone share my birthday? 2. Does any two people share a birthday?3. Does any two people share a birthday (but I can only remember and ask one date at a time)? Asymptotic growth1. O(n) or just n2. O(n) or just n for small n (https://en.wikipedia.org/wiki/Birth day_problem)Worst case: 365 (technically 366) Average run time: 24.616593. O(n2) or n2 Asymptotic growthMonotonically increasing means: for all m < n implies f(m) < f(n)Math reviewMonotonically decreasing means: for all m < n implies f(m) > f(n)
Strictly increasing means:
for all m < n implies f(m) < f(n)In proving it might be useful to use monotonicity of f(n) or d/dn f(n) Math reviewfloor/ceiling?modulus?exponential rules and definition? logs?factorials? Math reviewfloor is round down floor(8/3) = 2ceiling is round upceiling(8/3) = 3(both are monotonically increasing)Prove: floor(n/2) + ceiling(n/2) = n Floors and ceilingsProve: floor(n/2) + ceiling(n/2) = n Case: n is even, n = 2kfloor(2k/2) + ceiling(2k/2) = 2kk + k = 2kCase: n is odd, n = 2k+1 floor((2k+1)/2) + ceiling((2k+1)/2) floor(k+1/2) + ceiling(k+1/2)k + k+1 = 2k + 1 Floors and ceilingsModulus is the remainder of the quotient a/n:a mod n = a n floor(a/n)7% 2 = 1Modulusn! = 1 x 2 x 3 x … x n 4! = 4 x 3 x 2 x 1 = 24Guess the order (low to high):1,000 1,000,000 1,000,000,000 25 210 215 220 2305! 10! 15! 20! FactorialThe order is (low to high): {25, 5!, (1,000), 210, 215, (1,000,000), 220, 10!, (1,000,000,000), 230, 15!, 20!} 10! = 3,628,80015! 1,307,674,400,00020! 2,432,902,000,000,000,000 (210 = 1024 1,000 = 103) FactorialFind g(n) such that (g(n) = n!): 1. n! = (g(n))2. n! = O(g(n)) Factorial1. n! = (g(n))- n! = (1) is a poor answer – n! = (2n) is decent2. n! = O(g(n)) – n! = O(nn) Factorial(an)m = anm: (23)4 = 84 = 4096 = 212 anam = an+m: 2324 = 8×16 = 128 = 27 a0 = 1a1 = aa-1 = 1/aExponentialsfor all constants: a>1 and b:
What does this mean in big-O notation?
Exponentials

What does this mean in big-O notation?
nb = O(an) for any a>1 and b
i.e. the exponential of anything eventually grows faster than any polynomials
Exponentials

Sometimes useful facts:
ex = sum(i=0 to ) xi / i! ex = lim(n ) (1 + x/n)n
Exponentials

Write the first 5 numbers, can you find a pattern:
1. Fi = Fi-1 + 2 with f0 = 0
2. Fi = 2Fi-1 with f0 = 3
3. Fi = Fi-1 + Fi-2, with f0=0 and f1=1
Recurrence relationships

1. Fi = Fi-1 + 2 with f0 = 0
F0=0, F1=2, F2=4, F3=6, F4=8 Fi = 2i
2. Fi = 2Fi-1 with f0 = 3
F0=3, F1=6, F2=12, F3=24, F4=48
F
i
= 3 x 2i
Recurrence relationships

3. Fi = Fi-1 + Fi-2, with f0=0 and f1=1 F0=0, F1=1, F2=1, F3=2, F4=3
F0=5, F1=8, F2=13, F3=21, F4=34
Fi = [(1+sqrt(5))i(1-sqrt(5))i]/(2isqrt(5))
Recurrence relationships

3. Fi = Fi-1 + Fi-2 is homogeneous We as Fi = cFi-1 is exponential,
we guess a solution of the form:
Fi = Fi-1 + Fi-2, divide by Fi-2
F2 = F + 1, solve for F
F = (1 sqrt(5))/2, so have the form a[(1 + sqrt(5))/2]i+b[(1 sqrt(5))/2]i
Recurrence relationships

a[(1 + sqrt(5))/2]i+b[(1 sqrt(5))/2]i with F0=0 and F1=1
22 System of equations solve i=0: a[1] + b[1] = 0 a = -b
i=1: a[1+sqrt(5)/2] a[1-sqrt(5)/2]
a[sqrt(5)] = 1 a = 1/sqrt(5) = -b
Recurrence relationships

Fi = 2Fi-1 Fi-2 , change to exponent Fi = 2Fi-1 Fi-2 , divide by Fi-2
F2 = 2F 1 (F-1)(F-1) = 0
This will have solution of the form: 1i + i x 1i
Recurrence relationships