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
Moore’s 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=1 1 n2 < 2n2 – 5n + 7 0 < 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 growth f(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 growth There are also o(g(n)) and w(g(n)) but are rarely used f(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 growth Big-O notation is used very frequently to describe run time of algorithms It is fairly common to use big-O to bound the worst case and provide empirical evaluation of runtime with data Asymptotic growth What 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 growth 1. O(n) or just n 2. 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.61659 3. O(n2) or n2 Asymptotic growth Monotonically increasing means: for all m < n implies f(m) < f(n) Math review Monotonically 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 review floor/ceiling? modulus? exponential rules and definition? logs? factorials? Math review floor is “round down” floor(8/3) = 2 ceiling is “round up” ceiling(8/3) = 3 (both are monotonically increasing) Prove: floor(n/2) + ceiling(n/2) = n Floors and ceilings Prove: floor(n/2) + ceiling(n/2) = n Case: n is even, n = 2k floor(2k/2) + ceiling(2k/2) = 2k k + k = 2k Case: 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 ceilings Modulus is the remainder of the quotient a/n: a mod n = a – n floor(a/n) 7% 2 = 1 Modulus n! = 1 x 2 x 3 x ... x n 4! = 4 x 3 x 2 x 1 = 24 Guess the order (low to high): 1,000 1,000,000 1,000,000,000 25 210 215 220 230 5! 10! 15! 20! Factorial The 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,800 15! ≈ 1,307,674,400,000 20! ≈ 2,432,902,000,000,000,000 (210 = 1024 ≈ 1,000 = 103) Factorial Find g(n) such that (g(n) ≠ n!): 1. n! = Ω(g(n)) 2. n! = O(g(n)) Factorial 1. n! = Ω(g(n)) - n! = Ω(1) is a poor answer - n! = Ω(2n) is decent 2. n! = O(g(n)) - n! = O(nn) Factorial (an)m = anm: (23)4 = 84 = 4096 = 212 anam = an+m: 2324 = 8x16 = 128 = 27 a0 = 1 a1 = a a-1 = 1/a Exponentials for 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
2×2 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