Tutorial 2 - Data Structures '10

Jonathan Cederberg <[e-mail]>

Description

Tutorial 2Data Structures ’10Jonathan Cederberg thWednesday, September 15 , 2010First assignment Probability Sorting Invariants Second assignment SlackOutline1 First assignment2 Probability3 Sorting4 Invariants5 Second assignment6 Slack2 DS’10 | Tutorial 2 (Data Structures ’10)First assignment Probability Sorting Invariants Second assignment SlackThings to rememberThe definitions of ;O:A sum grows according to its fastest growing term (the leftone)Polynomials grow faster than polylogsExponentials grow faster than polynomialsLarger exponent =) faster growthLarger base =) faster growth4 DS’10 | Tutorial 2 (Data Structures ’10)First assignment Probability Sorting Invariants Second assignment SlackReview of assignment 1 nn 3lgn 2n 4 n! lgn 2 (n +1)!23 n nn nlgn 2 n25 DS’10 | Tutorial 2 (Data Structures ’10)First assignment Probability Sorting Invariants Second assignment SlackCommentsI have still not received any questions on e-mail. Use thispossibility to influence these sessions.Deadlines are hard. Late submissions of the assignments willnot be considered. You just have to get the 24 points.When presenting proofs, use some words like “since” and“therefore”. The three dots are forbidden.Answers without explicit justifications give 0 pts in an exam.Numerical justification is no justification.6 DS’10 | Tutorial 2 (Data Structures ’10)First assignment Probability Sorting Invariants Second assignment ...

Informations

• Publié par: Cuvun
• Nombre de lectures: 24
• Langue: English

Extrait

Jonathan

Cederberg

Tutorial 2 Data Structures ’10

<u.seit.uonjahtaec.nbred@gre>

Wednesday, September 15 th , 2010

SD2attSurtcruse1’)0’10|Tutorial2(Da

Slack

6

4

Invariants

Second assignment

5

Outline

1

First assignment

2

Probability

3

Sorting

ignmentPFirstassoSytnitraborilibsSntonecnvgIiaaralkcneStgimnadss

curtSataD(2lairo

Things to remember

The definitions ofΩ,O.Θ A sum grows according to its fastest growing term (the left one) Polynomials grow faster than polylogs Exponentials grow faster than polynomials Larger exponent=⇒faster growth Larger base=⇒faster growth

)10s’retu|TutS’104D itilorySPrntabobissaemngFtsrignmentSlcondassiirnasteSitgnnIavkca

mnnessgikcStaliantnvarondasSecytilibabIgnitroSigsstarsrotPennm 5SD1’|0uTot

 3 2  n

nlgn2 n n∙2 n

n 3

4 lgn

n

lgn2 2 n (n+1)!

n!

Review of assignment 1

0)’1esurtcurtSataD(2lair Fi

cktSlanmenFirstaPtorabibssgimnnegIinarnvtylirtSoadnogisstnaiceSs )10s’re

Comments

I have still not received any questions on e-mail. Use this possibility to influence these sessions. Deadlines are hard. Late submissions of the assignments will not be considered. You just have to get the 24 points. When presenting proofs, use some words like “since” and “therefore”. The three dots are forbidden. Answers without explicit justifications give 0 pts in an exam. Numerical justification is no justification.

taD(2laiutcurtSa6DS’10|Tutor

tSlackntiaarnvgIinrtSonemngissadnoceSsssigrstaFiilytabibPtormnne aD(2lairtcurtSat0)’1esur

Ois not the same as≤! Exponentiation is right associative Use logarithms with care!

Comments

7DSTuto’10|

0 t 1 n T e | m t b u o r r o P a l i i 2 b l a D S ( y t t a itiorInngriva 9 t D s S a ’ n

Note thatE[∙]is a linear operator, i.e. X (a i ∙X i ) E " i= n 1 # = i= n X 1 (a i ∙E[X i ])

Review of probability theory Asample space Sis the set of all possible outcomes. Anevent Ais a subsetA⊆S A random variable is often denotedX Theexpected value E[X]of a random variableXis defined as E[X] = X x∙Pr{X=x} x

traStu F u i c r s s ’ t r a e s ) si 1 g 0 nkcalSntmegnsiasndcoSe

Unbiased-Random 1 while true 2do 3x←Biased-Random 4y←Biased-Random 5ifx6=y 6thenreturnx

Exercise: Bleaching You have a function, Biased-Random, that returns 1 with probabilitypand 0 with probability 1−p you do not. Sadly knowp a function Unbiased-Random that returns 1. Design with probability 1/2 and 0 with probability 1/2.

1’)0ruseurtcotuTlairaD(2tSatDS100|’1 FtsriissaemngrPtnobabilitySortingnIavirnasteSocdnmegnsiaskacSlnt

|Tutorial2(DataS1D1’S01curterut01’s

or vice versa. Since

Exercise (cont.): Bleaching Why does this work? Because Unbiased-Random only returns whenx=0 andy=1 Pr{Unbiased-Randomreturns0}= Pr{x=0∧y=1}= (1−p)p= p(1−p) = Pr{x=1∧y=0}= Pr{Unbiased-Randomreturns1} and there are no other outcomes, Unbiased-Random is fair. Note that this relies on that the calls to Biased-Random are independent.

) ProbmentitySabilgnnIroitnastavirriFngissatscoSeasndgnsintmecalSk

By the definition of expected value we have for any indicator random variableX A E[X A ] =E[I{A}] =1∙Pr{A}+0∙Pr{S\A} =1∙Pr{A}+0∙Pr{S\A} =Pr{A}

Definition Anindicator random variable I{A}of an eventAis a defined as I{A}=  0 1if ifA A rcoucsnotdoe soccur

0)urtSataD1’serutc0|TuDS’1al2(tori21 gissnemnorPtibabtylirtSogIinarnvaitnSscenoadssginmentSlacksratiF

airaSstnnocessadnmigtSenckla 1 gimnatss T o | r 0 a 1 b ’ n S e D P 3 t l t 2 y i S a o o b r i u l t i t g r I a n S v a r t t ( i D nrsFi 10)

Example: Flipping a coin S={H,T} A={H} X H =I{Flip isH}=  0 1 E[X H ] =E[I{Flip isH}] =1∙Pr{Flip isH}+0∙Pr{Flip is notH} =1∙(1/2) +0∙(1/2) =1/2

if flip isH if flip is notH

uctures’