# 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