tutorial

Description

TutorialQuestion 1Review the deflnitions of the basic notations such as £, O, ›, o, and !.O-notationFor a given function g(n), denoted by O(g(n)) the set of functions.O(g(n)) =ff(n): there exist positive constants c and n such that00• f(n)• cg(n) for all n‚ n g.0›-notationFor a given function g(n), denoted by ›(g(n)) the set of functions.›(g(n)) =ff(n): there exist positive constants c and n such that00• cg(n)• f(n) for all n‚ n g.0£-notationFor a given function g(n), denoted by £(g(n)) the set of functions.£(g(n)) =ff(n): there exist positive constants c , c , and n such1 2 0that 0• c g(n)• f(n)• c g(n) for all n‚ n g.1 2 0o-notationFor a given function, g(n), we denote by o(g(n)) the set of functions.o(g(n)) = ff(n): for any positive constant c > 0, there exists aconstant n > 0 such that 0• f(n) < cg(n) for all n‚ n g.0 0The implication of this, is that f(n) becomes insigniflcant relativeto g(n) as n approaches inflnity:f(n)lim = 0n!1 g(n)!-notationFor a given function, g(n), we denote by !(g(n)) the set of functions.!(g(n)) = ff(n): for any positive constant c > 0, there exists aconstant n > 0 such that 0• cg(n) < f(n) for all n‚ n g.0 0The implication of this is that g(n) becomes insigniflcant relative tof(n) as n approaches inflnity:166f(n)lim =1n!1 g(n)Question 2What is the difierence between O and o as well as › and !?The difierence between O and o is that O represents an upper boundof the solution for a problem, which may also be ...

Informations

• Publié par: Mephar
• Nombre de lectures: 22
• Langue: English

Extrait

Question 1

Tutorial

Review the definitions of the basic notations such asΘ,O,Ω,o, andω.

O-notation For a given functiong(n), denoted byO(g(n)) the set of functions. O(g(n)) ={f(nexist positive constants): there candn 0 such that 0≤f(n)≤cg(n) for alln≥n 0 }. Ω-notation For a given functiong(n), denoted by Ω(g(n)) the set of functions. Ω(g(n)) ={f(n): there exist positive constantscandn 0 such that 0≤cg(n)≤f(n) for alln≥n 0 }. Θ-notation For a given functiong(n), denoted by Θ(g(n)) the set of functions. Θ(g(n)) ={f(nexist positive constants): there c 1 ,c 2 , andn 0 such that 0≤c 1 g(n)≤f(n)≤c 2 g(n) for alln≥n 0 }. o-notation For a given function,g(n), we denote byo(g(n)) the set of functions. o(g(n)) ={f(n): foranypositive constantc >0, there exists a constantn 0 >0 such that 0≤f(n)< cg(n) for alln≥n 0 }. The implication of this, is thatf(n) becomes insignificant relative tog(n) asnapproaches infinity:

f(n) lim = 0 g(n) n→∞

ω-notation For a given function,g(n), we denote byω(g(n)) the set of functions. ω(g(n)) ={f(n): foranypositive constantc >0, there exists a constantn 0 >0 such that 0≤cg(n)< f(n) for alln≥n 0 }. The implication of this is thatg(n) becomes insignificant relative to f(n) asnapproaches infinity:

1

Question 2

f(n) lim =∞ g(n) n→∞

What is the difference betweenOandoas well asΩandω?

The difference betweenOandois thatOrepresents an upper bound of the solution for a problem, which may also be the tight bound of solving that problem, whileoclearly indicates that it is an upper bound but definitely not the tight bound. 2 2 2 For example, 2n=o(n) but 2n6=o(n). For the Omegas. . . 2 2 2 For examplen /2 =ω(n) butn /26=ω(n).

Question 3

2 3/0 2 4 .7n Rank the following functions in the order of growth:nlogn,nlogn,3, p √ ∗2 1 /log n 1/ log3 log n lognlogn,n,nlogn,n,n

First, work out that the following is actually a constant. . .

1 logn n 2

= = = = =

lg 2 n lgn log 2 n n logn n 2 1 2 2

1/logn (5)n→2 ∗2 (4) lognlogn→logn p 1/ 3 1/6 (6)nlogn→n √ 1/2 (8)n→n 3/ 2 4 3/2 (2)nlogn→n 2 2 (1)nlogn→n log lognlog logn (7)n→n 0.7n n (3) 3→3 Note that “Log star of n” is iterated logarithm. ∗i logn= min{i≥0 : logn≤1}

2

Question 4

Use the divide-and-conquer paradigm to explain the basic steps of the quicksort algorithm.

The divide-and-conquer strategy divides a problemAinto a number of sub- problems of roughly equal sizes. Then each subproblem is solved recursively. The base case being a subproblem that is small enough to solve without further dividing. Next, the solutions of the subproblems are combined to obtain the solution for the original problem. For the case of quicksort:

1. (DIVIDE) Pick an elementx=a i Usually theto be the pivot element. first elementa 1 is picked. 2. (DIVIDE) Partition the sequence into two disjoint subsequences: S 1 ={a i :a i ≤x}, and S 2 ={a j :a j > x}. 3. (CONQUER) SortS 1 andS 2 recursively using quicksort. 4. (MERGE) Merge the sortedS 1 ,{x}, andS 2 original sequence is. The sorted.

Question 5

Review the four techniques for bounding the summations. Use one of the intro- P ∞ k duced techniques to bound k . k=1 5 The four techniques for bounding summations are as follows.

1.Mathematical induction What is mathematical induction? series: 1 + 2 + 3 +. . .+n

For example, binding the

P(n) says: 1 + 2 + 3 +. . .+n

IfP(n) is true, isP(ntrue?+ 1)

=

P(nsays: 1 + 1) + 2 + 3 +. . .+n+ (n+ 1)

3

n(n+ 1) 2

=

=

=

n(n+ 1) + (n+ 1) 2 (n+ 1)(n+ 2) 2 (n+ 1)((n+ 1) + 1) 2

ThereforeP(n)⇒P(n+ 1). 1(1+1) Now, show our base case.P(1) is true because 1 = = 1. 2 And sinceP(1) is true,P(2) must be true, soP(3) is true, and so on. . . 2.Splitting summations For example, finding the lower bound. We can changektonand find the upper bound:

n X k k=1

≤

= =

n X n k=1 2 n 2 O(n)

To find the lower bound we split the summation:

n X k k=1

=

≥

=

=

n/2 n X X k+k k=1 k=n/2+1 n/2 n X X 0 +n/2 k=1 k=n/2+1 2 n 4 2 Ω(n)

3.Approximation by integrals P q For example, if we havef(x), then the sum really is the x=p area under the curvef(x) forp≤x≤qcan use inte-. We gration to find the area under a curve. Thus the summation is R q approximately equal tof(x). p 4.Bounding terms We now apply the bounding terms to show the upper bound of

k Leta k = k 5 Then. . .

∞ X k k 5 k=1

k a k+1 k5+ 1 k+ 1 =×= k+1 a k 5k5k

4

This is maximum whenk. .= 1, so.

1 + 1 r≤ 5 2 r≤ 5 P ∞ k Given that the first terma 1 = 1/5, k can be bounded k=1 5 by the sum to infinity of the geometric series.

Question 6

∞ X k k 5 k=1

≤

=

=

1 1 × 2 5 1 − 5 1 1 × 3 5 5 1 3

Review the two approaches for solving recurrences, and apply them to solve the following recurrences.

•Substitution method:guess a bound and then use mathematical in- duction to prove that the guess is correct.

•Iteration method:convert the recurrence into a summation and then use the techniques for bounding summations to solve the recurrence.

Question 6(a)

4/3 T(n) =T(n/3) +n

Using the iterative method. . .

T(n)

= =

=

=

4/3 n+T(n/3) n n 4/3 4/3 n+ ( ) +T( ) 2 3 3 n n n 4/3 4/3 4/3 n( ) + ( +) + T( ) 2 3 3 3 3 n n n 4/3 4/3 4/3 4/3 n( ) ) + ++ ( . . .)+ ( 2k 3 3 3

5

T(n)

1 Let constantc= 1 1− 4/3 3

If you want to find k. . .

Question 6(b)

=

=

<

<

T(n)

n k 3 k

k µ ¶ 4/3 X 1 4/3 n i 3 i=0 k µ ¶ i X 1 4/3 n 4/3 3 i=0 ∞ µ ¶ i X 1 4/3 n 4/3 3 i=0 1 4/3 n 1 1− 4/3 3

< =

= =

T(n)≤T(n/4) +T(n/5 + 57) + logn 2

4/3 cn 4/3 O(n)

1 logn 3

Using the substitution method, first. . .

n/4 n

≥ ≥

n/5 + 57 1140

Sincen/4≥n/when5 + 57 n≥1140,T(n/4) will dominateT(n/5 + 57) whenn≥we simplify the recurrence into:1140. So

T(n)≤2T(n/4) + logn 2

GUESS 1: Now we guess that the solution is:

√ T(n)≤c n

6

Assuming that this holds forT(n/4):

p T(n/4)≤c n/4 1 √ =c n 2 Substitute this into our originalT(n):

T(n)

≤

=

µ ¶ 1 √ 2c n+ logn 2 2 √ c n+ logn 2

This doesn’t agree with our guess. √ GUESS 2: Revise our guess toT(n)≤c n+blogn 2 p AssumeT(n/4)≤c n/4 +blog (n/4) 2 Substitute:

T(n)

≤ = =

³ ´ p 2c n/4 +blog (n/log4) + n 2 2 √ c n+ 2blogn−2b+ loglog 4 n 2 2 2 √ c n+ (2b+ 1) logn−4b 2

Still doesn’t agree with our guess. √ GUESS 3: Revise our guess toT(n)≤c n+blogn+a 2 p AssumeT(n/4)≤c n/4 +blog (n/4) +a 2 Substitute:

T(n)

≤ = =

³ ´ p 2c n/4 +blog (n/4) +a+ logn 2 2 √ c n+ 2blogn−2b+ loglog 4 n+ 2a 2 2 2 √ c n+ (2b+ 1) logn+ 2a−4b 2

Since this is the same form as our guess, we solve forbanda.

2b+ 1 b

2a−4b a a

7

= =

= = =

b −1

a 4b −4

Thus, the inequality holds whenb=−1 anda=−4. For alln <1140, let theT(n) be bounded by a constantR. Solve forcwhenn= 4096:

√ T(4096)≤c4096−log 4096−4 2 √ 2T(1024) +log 2 4096≤c4096−log 4096−4 2 2R+ 12≤64c−12−4 2R+ 28 c≥ 64 √ 2R+28 Thus, 0≤T(n)≤c n−logn−4 whenc≥for alln≥1140 2 64 √ T(n) =O(n)

Question 6(c) iterative √ T(n) =T(bnc) + 3n Using the iterative method. . .

T(n)

k k 1 ( 2 ) n µ ¶ k 1 lgn 2 µ ¶ k 1 2 k 2 klg 2 k

= =

=

=

= = =

= = =

√ 3n+T(bnc) 1/2 1/4 3n+ 3n+T(bnc) 1 1 2 1k ( ) ( ) ( ) 3n+ 3n+ 3n+. . .+ 3n 2 2 2

no. of times we can square rootnuntil it is 2 2

lg 2

lg 2 lgn lgn lg lgn lg lgn

T(n)

≤ ≤ ≤ =

3n×(k+ 1) 3n×(lg lgn+ 1) 3nlg lgn+ 3n O(nlg lgn)

8

Question 6(c) changing variables √ T(n) =T(bnc) + 3n

An alternative method is to use “changing variables” together with the iterative method. m Letn= 2 . Substituting this into the recurrence, we get:

m T(2 )

=

m/2m T(2 ) + 3×2 Note that square root is essentially halving the power.

m RenameS(m) =T(2 ):

m S(m) =S(m/2) + 3×2

This is possible because now we have changed the “problem size” variable tom. Note that work done at each level of the recursion is m still 3×32 = n. So using the iterative method to solveS(m). . .

S(m)

Findk:

= = =

=

m S(m/2) + 3×2 m m/2 2 3×32 + ×2 +S(m/2 ) 2k m m/2m/2m/2 3×32 + ×2 + 3×2 +. . .+ 3×2 k X i m/2 3 2 i=0

k m/2 2 k m/2 k

= = =

2 1 logm 2

Since the biggest element in the summation is wheni= 0, we can i m/2m bind the summation by replacing 2 with 2 .

S(m)

≤ =

m 3×2 logm 2 m O(2 logm) 2

9

T(n)

= = = =

m T(2 ) S(m) m O(2 logm) 2 O(nlog logn) 2 2

10