程序代写代做代考 C data structure algorithm COSC 336 Data Structures and Algorithms

COSC 336 Data Structures and Algorithms
Mathematical tools for the analysis of algorithms
Professor: Marius Zimand
1 Important functions
The functions that appear commonly in the analysis of algorithms are: logarithms, polyno- mials, exponential, factorial.
1.1 Polynomials.
A polynomial function is a function of the type
p(n)=aknk +ak1nk1 +…+a1n+a0,
where the coecients ak , . . . a0 are constants. This is a polynomial of degree k. Typically in algorithms ak > 0, which we assume henceforth.
The behavior of a polynomial of degree k is controlled by the dominating term nk.
The simple but important fact to remember is that nk goes to 1 as n goes to 1. nk1
So if p(n),q(n) are two polynomials and the degree of p is larger than the degree of q, then q(n)/p(n) goes to 0, which is also written as q(n) = o(p(n)), or, equivalently, p(n) = !(q(n)).
1.2 Exponential function.
The exponential function has the form f(n) = an for some constant a > 1 (It is possible that a < 1, but such situations are less common in algorithms). Consider a process in which a parameter n has initially the value 1 and doubles at each iteration: 1 ! 2 ! 4 ! . . . ! 2n 1 Thus in n iterations, the parameter becomes exponentially large. In general if the initial value is a0 and at each iteration the parameter gets multiplied by q, then at iteration n, it becomes a0qn. The exponential function also appear when counting di↵erent objects. Thus, the number of binary strings of length n is 2n, and more generally the number of words of length n over an alphabet with q letters is qn. Main Properties: • a0 = 1. • a1 = 1/a. • am · an = am+n. • (am)n = amn • The exponential function grows faster than any polynomial. Formally, for every k 0, lim nk =0. n!1 an For example, n3000 < 20.01n if n is suciently large. Proofsketch: Wewritea=1+c,withc>0. Then
an =1+✓n◆c+✓n◆c2+…+✓ n ◆ck+1+…+cn (binomialformula). 12k+1
So,
an > n ck+1 = n(n1)…(nk) ck+1.
k+1 (k+1)! Then,
nk nk
an < n(n1)...(nk) ·(k+1)!/c k+1 . The right hand side goes to 0 because (k + 1)!/ck+1 is a constant and in the fraction the numerator is a polynomial of degree k, and the denominator is a polynomial of degree k + 1. 2 " 1.3 Logarithms. By definition logb n is the number a such that ba = n. The number b is called the base and it is required that b 6= 1. For example, log2 n is the number a such that 2a = n. By default in computer science, if the base is not specified, it is equal to 2. Some occurrences of the logarithmic function Consider a process that depends on a parameter n, and suppose the parameters halves at each step: n!n/2!n/22 !...!n/2k... It can be shown that the number of steps till the parameter becomes  1 for the first time is log2 n. The length in bits for writing an integer n in base 2 is dlog(n + 1)e ⇡ log n. Main Properties • a=2loga foralla>0. Ingenerala=blogba.
• log(ab)=loga+logbandloga/b=logalogb
• logan = nloga
• formula for changing the base: lognew-base a = Example: log2 5 = log10 5/ log10 2.
I
32,0 →
logold-basea . logold-basenew-base
• By default, if the base is not written explicitly, it is 2.
• The logarithm even raised to a constant power grows slower than any polynomial
functions. More formally, limn!1 (log n)k = 0. n
This is easy to see. We denote m = log n and then n = 2m and the ratio becomes mk/2m which goes to 0 as we know from the properties of the exponential function. For example, (log n)1000 < n0.001 if n is suciently large. 3 32 32→ M 16 = →2→I I5 -log Fk S.t. 2K- I < n < I →8→4 23 5- = , 3 2 m= 2K 2K 2%1 2K- ' → → 2K- Z→ → K -n Is :3:gu n 7 2K- ' logon > K ‘ k=Tloga7= logic
t. nly, ¥. 1,
I
” ly d
2K < 6 .. no- of Z . steps If n is not a power of 45 132245264 steps Jk 2K 2K-2 MIZ 2K- 1 : → - -- - t, If . . n → f-→ I→ . - - → ¥ It takes log u steps to get to E b log, n = A ( logan ) l. 1.4 Factorial function 3! = 1.2-3=6 The number of permutations of n di↵erent object is n!. The number of combinations of k chosen from n is n = n! k k!(nk)! Approximating the factorial Using calculus, we can derive the following approximation of n!: (Stirling approximation): n! ⇡ p2⇡n(n/e)n. n! = 1 · 2 · . . . · n. Some occurrences of the factorial = n(n1)...(nk+1) . k! While the Stirling approximation is somewhat more dicult to derive, we can easily show the following bounds: (n/2)n/2 < n! < nn. Indeed n! = 1 · 2 · . . . · n < n · n · . . . · n = nn, and n! > (n/2 + 1) · . . . · n > (n/2)(n/2) . . . (n/2) (n/2 factors). Thus n! grows faster than the exponential 2n.
Also, log(n!) = ⇥(n log n).
Order of growth of some important functions
constant1)1)<2n
U-N. –. An (12+1)/12+2)
n!
=
Lt-
=
Take
– en
so
log :
(E)” ‘
au!an
”
log n ” login
2.—eNL
—– .-.
EMM
-n
F. so :
log’t clogn !
logn! = Ctfu. logie)
log @Juke
bgfn ! )
>
Mz “k
Nz. Nz- – – Mz
–

b. C ⇒
-a, d
• Make
→ permutations a,b,C
9,43 :÷÷.
–
committees a re
A,
bee
a committee of2
,
Hoon money Aib
9,C aid
( E) ” 4 choose
bc
b.a : e-
possible ? (4) =9÷z=6
, E x ( } -) 7 9 7 3 = 3 5 e. d
( Ne )
.
–
–
–
Kei
M ln -17cm -2 ) =
2
I. —K
Cn )
.
2″

2 Sums, and Series
The setting is that there is a sequence u1,u2,…,un,… (many times it is an infinite se- quence).
Let Sn = u1 +…+un. We want to find Sn or to estimate Sn, which means to find lower and upper bounds for Sn.
Arithmetic series a,a+d,…,a+(n1)d,… (so, recalling the general setting, un = a+(n1)d)
Sn = na + dn(n1) 2
Important particular case: 1 + 2 + . . . + n = n(n+1) . 2
Geometric series a, a · r, a · r2, . . . , a · rn1, where r 6= 1. Sn =a·rn1.
r1
Important particular case: 1+r+…+rn1 = rn1.
Harmonic series
LetHn =1+1/2+1/3+…+1/n. We have the following estimation:
Other sums
Hn =lnn+O(1).
T1 =1+2+…+n=n(n+1)/2.
T2 =12 +22 +…+n2 =n(n+1)(2n+1)/6. T3 =13 +23 +…+n3 =[n(n+1)/2]2.
In general Tr = 1r + 2r + … + nr = ⇥(nr+1) (see proof below, using the method of integrals).
5
r1

Aat
d
a c- 201
we add ol
d step .
Su=
-S = S=
Z’S =
…
,,
a + catd)t
e-ahh-is. ol
S= It2T ‘me nxeaut to
S=I 1¥
+N Cn-Dtr- tI
—
–
—
5=17+1 ) I(Base) Prove it for n= I
by
‘)
nineteen u=1 is
=I
-.. ,,
.
=
=n. a+dcitzt– ten-it)e-n.a+c)En
It 2-1 Mt
. (na) n
N
Z ✓7
th 11 u
induction .
prove
AtCn- t) at each
n in th -2
⇒S=
←•
is true Informal

It 3+5+7 t
2n-I=
= =2(
It
..-
tu)
–
=p
.
n”
MIN
–
n m2
=
=
–
n
=
e) +12.2-
Dt N
ton-D —
CEI –
2T
+ 11+12-3 –
–
—

S= It2T ‘Ne axeoutto
th
–
—
S= M¥-1) by I(Base)Proveitforu= I
induction .
S=I 1¥
‘)
( Inductive
prove
whenu=I is =I step)
I
the statement is
we assume
true that it is true for@ti)
for we
It the=
=I4.
we assume :
2 x tntIntl =
Ic- Lt
…
)
– =
—
+ cuts) M (Nfl) + Unit)
Put
u
show *
Assume true Pu is
+me M¥1
nine ,
DONE
istrue
,
!
.

=
=
c- rn- 1) = a
.
-r- I
aira- r2
cairn – ‘ = ata. raa-r’t. – c-a.r”‘
a
,,
s
..
.
,
a ( ltrtrx . –
gq ,
‘t 1- -¥¥
“‘ -..
lt r t r ri
+r .
Cr- =-
T
to
MI
r
–
-I -.-
rn- l
r-T
T D r”I Ifrtl
.
M l+r+rI er”‘ = F-
-T=
-i

2.1 Approximating sums with integrals
Using integrals, we can estimate sums of the form Sn = f(1)+f(2)+…+f(n). If f is an
increasing function then
If f is decreasing then
Z n Z n+1 f(x)dx  Sn 
01
f(x).
and
Zn Znr r+1 n r+1
Tr f(x)dx= x dx=x /(r+1)0 =n /(r+1).
00
Z n+1 Z n f(x)dx  Sn 
f(x).
Example: We want to estimate Tr = 1r +2r +…+nr. We use f(n) = nr, so Tr =
10
f (1) + . . . + f (n). Since f (n) is an increasing function, we obtain using integrals,
Zn+1 Zn+1 r r+1 n r+1
f(x)dx= x dx=x /(r+1)0 =(n+1) /(r+1)1/(r+1).
Tr 
Combining the two estimations, we see that Tr = ⇥(nr+1).
11
Sometimes, the integral involved in the estimation is not defined in the domain of in- terest, and then we have to be a little more careful and split the sum in two parts, so that the part where we use the estimations with integrals does not present this problem.
For example, suppose we want to estimate the harmonic series Hn = 1 + 1/2 + . . . + 1/n. We take the function f(x) = 1/x, which is decreasing. The lower bound does not raise any
problem: Z n+1 n+1
Hn 1/xdx=lnx1 R=ln(n+1).
1
For the upper bound, we would like to say that Hn  0n 1/x dx but this is wrong because
1/x is not defined at 0. So we split Hn into 1 and (1/2+…+1/n), that is Hn = 1+(1/2+…+1/n).
Now, for the second part we can use the integral technique and obtain (1/2+. . .+1/n)  R1n1/xdx=lnn. AndwegetthatHn 1+lnn.
6

2.2 Other techniques for estimating sums
Bounding the terms
Example:
1r +2r +…+nr nr +nr +…+nr =n·nr =nr+1.
Cutting some terms and bounding
Example:
Telescoping
Example:
1r +2r +…+nr
>(n/2+1)r +(n/2+2)r +…+nr >(n/2)r +(n/2)r +…+(n/2)r
= (n/2)(n/2)r
= (1/2r+1)nr+1.
1+1+…+1 =(11)+(11)+…+(11)=11. 1·2 2·3 n·(n+1) 1 2 2 3 n n+1 n+1
7

3 Asymptotic notation:
When we analyze algorithms, many times we want to just get a rough estimate and then it is ok to ignore constants and what happens for small values of the parameters.
In what follows we assume that functions have positive integers inputs.
1. t(n) = O(f(n)) (read t(n) is in Big-Oh of f(n), or just t(n) is Big-Oh of f(n)) means
that there exist positive constants c and n0 such that t(n)  c · f(n) for all n n0. The intuitive meaning is that t(n) “” f(n) if we ignore multiplicative constants and
small values of n.
Sumrule: f(n)+g(n)=O(max(f(n),g(n))).
2. t(n) = ⌦(f(n)) (read t(n) is in Big-Omega of f(n) or just t(n) is Big-Omega of f(n)) means that there exist positive constants c and n0 such that t(n) c · f(n) for all n n0.
The intuitive meaning is that t(n) “” f(n) if we ignore multiplicative constants and small values of n.
Sum rule: f (n) + g(n) = ⌦(min(f (n), g(n))).
3. t(n) = ⇥(f(n)) (read t(n) is in Big-Theta of f(n) or just t(n) is Theta of f(n)) means
that t(n) = O(f(n)) and t(n) = ⌦(f(n)).
The intuitive meaning is that t(n) “ = ” f(n) if we ignore multiplicative constants
and small values of n.
4. t(n) = o(f(n)) (read t(n) is in Little-Oh of f(n) or just t(n) is Little-Oh of f(n))
means that limn!1 t(n) = 0. f (n)
The intuitive meaning is that t(n) “< ” f(n) if we ignore small values of n. 5. t(n) = !(f(n)) (read t(n) is in Little-Omega of f(n) or just t(n) is Little-Omega of f(n)) means that limn!1 t(n) = 1. f (n) The intuitive meaning is that t(n) “> ” f(n) if we ignore small values of n.
8

3.1 How to establish the relative order of growth of two functions
We want to establish the asymptotic relation between f(n) and g(n). For that we use:
1. What we know about some common functions. Example n log n = o(n2) because we
know that log n = o(n).
2. We calculate limn!1 f(n)/g(n)
If the limit is some constant c > 0, then f(n) = ⇥(g(n)).
If the limit is c = 0, then f(n) = o(g(n)) and g(n) = !(f(n)). If the limit is +1, then f(n) = !(g(n)) and g(n) = o(f(n))
9

EXERCISES :

4 The Master Theorem
When we do divide-and-conquer algorithms, we typically need to solve recurrences of the form
t(n) = atn + f(n), b
where a 1, b > 1. This happens when we divide the problem of size n into a subproblems each of size (n/b) and do extra f(n) steps.
The Master Theorem gives the asymptotic solution for the above recurrence:
1. If f(n) = O(nlogb a✏) for some constant ✏ > 0, then t(n) = ⇥(nlogb a). 2. If f(n) = ⇥(nlogb a), then t(n) = ⇥(f(n) log n).
3. If f(n) = ⌦(nlogb a+✏) for some constant ✏ > 0, then t(n) = ⇥(f(n)).
So, in short, we compare f(n) and nlogb a, and see which one is bigger in the asymptotic sense. We call the bigger function, the winner, and the smaller function, the loser.
If there is a tie (case 2, above), the t(n) = ⇥(f (n) log n).
If the winner is bigger by the loser by some n✏ (cases 1 and 3), then t(n) = ⇥(winner).
10