l1 algorithmique

8/15/2019 l1 algorithmique

1/54


2/54

L1.2

Welcome to Introduction to

Algorithms, Spring 2004ando!ts

1. Course Information

2. Course Calendar

3. Problem Set 1

4. Akra-Bazzi Handout

http://theory.lcs.mit.edu/classes/6.046/handouts/course-information.pdfhttp://theory.lcs.mit.edu/classes/6.046/handouts/calendar.pdfhttp://theory.lcs.mit.edu/classes/6.046/handouts/calendar.pdfhttp://theory.lcs.mit.edu/classes/6.046/handouts/course-information.pdf


3/54

L1.3

"o!rse information

1. Staff

2. Prereuisites

3. Le!tures " #e!itations4. Handouts

$. %e&tbook 'CL#S(

). *ebsite

+. ,&tra Hel

. #e/istration

10.Problem sets11.es!ribin/ al/oritms

12.radin/ oli!

13.Collaboration oli!

http://theory.lcs.mit.edu/classes/6.046/staff.htmlhttp://theory.lcs.mit.edu/classes/6.046/recitation.htmlhttp://theory.lcs.mit.edu/classes/6.046/handouts.htmlhttp://www.amazon.com/exec/obidos/ASIN/0262032937/qid=999563592/sr=1-3/ref=sc_b_3/002-9233126-5488026http://theory.lcs.mit.edu/classes/6.046/collaboration.htmlhttp://theory.lcs.mit.edu/classes/6.046/collaboration.htmlhttp://www.amazon.com/exec/obidos/ASIN/0262032937/qid=999563592/sr=1-3/ref=sc_b_3/002-9233126-5488026http://theory.lcs.mit.edu/classes/6.046/handouts.htmlhttp://theory.lcs.mit.edu/classes/6.046/recitation.htmlhttp://theory.lcs.mit.edu/classes/6.046/staff.html


4/54

L1.4

What is co!rse a#o!t$

The theoretical study of design and

analysis of computer algorithms

Basi! /oals for an al/oritm56 al7as !orre!t6 al7as terminates6 %is !lass5 erforman!e Performan!e often dra7s te line bet7een

7at is ossible and 7at is imossible.


5/54

L1.$

Design and %nal&sis of %lgorithms

6 Analysis: redi!t te !ost of an al/oritm in

terms of resour!es and erforman!e

6 Design: desi/n al/oritms 7i! minimize te

!ost


6/54

L1.8

'he pro#lem of sorting

Input: seuen!e 〈a19 a29 :9 an〉 of numbers.

E(ample)

Input: + 2 4 3 )

Output: 2 3 4 ) +

Output: ermutation 〈a' 1 , a' 2 , : , a' n〉 su!tat a' 1 ≤ a' 2 ≤ : ≤ a' n .


7/54L1.+

*nsertion sort

I ;S,#%I


8/54L1.

E(ample of insertion sort

+ 2 4 3 )


9/54L1.10


+ 2 4 3 )


10/54L1.11


+ 2 4 3 )

2 + 4 3 )


11/54L1.12


+ 2 4 3 )

2 + 4 3 )


12/54L1.13


+ 2 4 3 )

2 + 4 3 )

2 4 + 3 )


13/54L1.14


+ 2 4 3 )

2 + 4 3 )

2 4 + 3 )


14/54L1.1$


+ 2 4 3 )

2 + 4 3 )

2 4 + 3 )

2 4 + 3 )


15/54L1.1)


+ 2 4 3 )

2 + 4 3 )

2 4 + 3 )

2 4 + 3 )


16/54L1.18


+ 2 4 3 )

2 + 4 3 )

2 4 + 3 )

2 4 + 3 )

2 3 4 + )


17/54L1.1+


+ 2 4 3 )

2 + 4 3 )

2 4 + 3 )

2 4 + 3 )

2 3 4 + )


18/54L1.1


+ 2 4 3 )

2 + 4 3 )

2 4 + 3 )

2 4 + 3 )

2 3 4 + )

2 3 4 ) + done


19/54L1.20

+!nning time

6 %e runnin/ time deends on te inut5 analread sorted seuen!e is easier to sort.

6 DaEor Simlifin/ ConFention5 Parameterize te runnin/ time b te size ofte inut9 sin!e sort seuen!es are easier tosort tan lon/ ones.

%A'n( time of A on len/t n inuts

6 enerall9 7e seek uer bounds on terunnin/ time9 to aFe a /uarantee of

erforman!e.


20/54L1.21

,inds of anal&ses

Worst-case) 'usuall(6 T 'n( ma&imum time of al/oritm

on an inut of size n.

%erage-case) 'sometimes(6 T 'n( e&e!ted time of al/oritm

oFer all inuts of size n.6 ;eed assumtion of statisti!al

distribution of inuts./est-case) ';,G,#(

6 Ceat 7it a slo7 al/oritm tat

7orks fast on some inut.


21/54L1.22

achine-independent time

What is insertion sort’s orst!case time"

/*G *DE%S)

6 Ignore machine dependent constants , oter7ise imossible to Ferif and to !omare al/oritms

6 Look at growth of T 'n( as n .

1%s&mptotic %nal&sis


22/54L1.23

-notation

6 ro lo7-order termsJ i/nore leadin/ !onstants.

6 ,&amle5 3n3 K 0n# $n K )04) Θ'n3(

DEF:Θ' g 'n(( M f 'n( 5 tere e&ist ositiFe !onstants c19 c29 and

n0 su! tat 0≤

c1 g 'n(≤

f 'n(≤

c2 g 'n( for all n ≥ n0 N

Basic manipulations:


23/54L1.24

%s&mptotic performance

n

T 'n(

n0

.

6 Asmtoti! analsis is a

useful tool to el tostru!ture our tinkin/to7ard better al/oritm

6 *e souldnOt i/nore

asmtoti!allslo7er al/oritms9

o7eFer.6 #eal-7orld desi/n

situations often !all for a

*en n /ets lar/e enou/9 a Θ'n2( al/oritmalays beats a Θ'n3( al/oritm.


24/54L1.2$

*nsertion sort anal&sis

Worst case: Inut reFerse sorted.

( )∑=

Θ=Θ=n

j

n jnT 2

2('('

Aerage case: All ermutations euall likel.

( )∑=

Θ=Θ=n

j

n jnT 2

2(2'('

$s insertion sort a fast sorting algorithm"6 Doderatel so9 for small n.6 ;ot at all9 for lar/e n.

=aritmeti! series>


25/54L1.2)

E(ample 2) *nteger

!ltiplication

6 Let Q A B and R C 7ere A9B9C

and are n2 bit inte/ers

6 Simle Detod5 QR '2nP2AKB('2nP2CK(

6 #unnin/ %ime #e!urren!e

%'n( 4%'n2( K 100n

6 Solution %'n( θ'n2(


26/54L1.28

/etter *nteger !ltiplication

6 Let Q A B and R C 7ere A9B9C and

are n2 bit inte/ers

6 Taratsuba5QR '2nP2K2n(ACK2nP2'A-B('C-( K '2nP2K1( B

6 #unnin/ %ime #e!urren!e

%'n( 3%'n2( K 100n

6 Solution5 θ'n(


27/54L1.2+

E(ample 3)erge sort

E+GE-S+' A=1 . . n>

1. If n 19 done.

2. #e!ursiFel sort A= 1 . . n2 > and A= n2K1 . . n > .

3. !erge te 2 sorted lists.

"ey su#routine: E+GE


28/54

L1.2

erging two sorted arra&s

20

13

8

2

12

11

1


29/54

L1.30


20

13

8

2

12

11

1

1


30/54

L1.31


20

13

8

2

12

11

1

1

20

13

8

2

12

11


31/54

L1.32


20

13

8

2

12

11

1

1

20

13

8

2

12

11

2


32/54

L1.33


20

13

8

2

12

11

1

1

20

13

8

2

12

11

2

20

13

8

12

11


33/54

L1.34


20

13

8

2

12

11

1

1

20

13

8

2

12

11

2

20

13

8

12

11

8


34/54

L1.3$


20

13

8

2

12

11

1

1

20

13

8

2

12

11

2

20

13

8

12

11

8

20

13

12

11


35/54

L1.3)


20

13

8

2

12

11

1

1

20

13

8

2

12

11

2

20

13

8

12

11

8

20

13

12

11


36/54

L1.38


20

13

8

2

12

11

1

1

20

13

8

2

12

11

2

20

13

8

12

11

8

20

13

12

11

20

13

12

11


37/54

L1.3+


20

13

8

2

12

11

1

1

20

13

8

2

12

11

2

20

13

8

12

11

8

20

13

12

11

20

13

12

11

11


38/54

L1.3


20

13

8

2

12

11

1

1

20

13

8

2

12

11

2

20

13

8

12

11

8

20

13

12

11

20

13

12

11

11

20

13

12


39/54

L1.40


20

13

8

2

12

11

1

1

20

13

8

2

12

11

2

20

13

8

12

11

8

20

13

12

11

20

13

12

11

11

20

13

12

12


40/54

L1.41


20

13

8

2

12

11

1

1

20

13

8

2

12

11

2

20

13

8

12

11

8

20

13

12

11

20

13

12

11

11

20

13

12

12

%ime Θ'n( to mer/e a totalof n elements 'linear time(.


41/54

L1.42

%nal&5ing merge sort

E+GE-S+' A=1 . . n>

1. If n 19 done.

2. #e!ursiFel sort A= 1 . . n2 > and A= n2K1 . . n > .

$% &!erge' te 2 sorted lists

T 'n(

Θ'1(

2T 'n2(

Θ'n(

(loppiness: Sould be T ' n2 ( K T ' n2 ( 9 but it turns out not to matter asmtoti!all.


42/54

L1.43

+ec!rrence for merge sort

T 'n( Θ'1( if n 1J

2T 'n2( K Θ'n( if n @ 1.

6 *e sall usuall omit statin/ te base!ase 7en T 'n( Θ'1( for suffi!ientlsmall n9 but onl 7en it as no effe!t onte asmtoti! solution to te re!urren!e.

6 Le!ture 2 roFides seFeral 7as to find a/ood uer bound on T 'n(.


43/54

L1.44

+ec!rsion tree

SolFe T 'n( 2T 'n2( K cn9 7ere c @ 0 is !onstant.


44/54

L1.4$

+ec!rsion tree


T 'n(


45/54

L1.4)

+ec!rsion tree


T 'n2( T 'n2(

cn


46/54

L1.48

+ec!rsion tree


cn

T 'n4( T 'n4( T 'n4( T 'n4(

cn2 cn2


47/54

L1.4+

+ec!rsion tree


cn

cn4 cn4 cn4 cn4

cn2 cn2

Θ'1( :


48/54

L1.4

+ec!rsion tree


cn

cn4 cn4 cn4 cn4

cn2 cn2

Θ'1( :

h l/ n


49/54

L1.$0

+ec!rsion tree


cn

cn4 cn4 cn4 cn4

cn2 cn2

Θ'1( :

h l/ n

cn


50/54

L1.$1

+ec!rsion tree


cn

cn4 cn4 cn4 cn4

cn2 cn2

Θ'1( :

h l/ n

cn

cn


51/54

L1.$2

+ec!rsion tree


cn

cn4 cn4 cn4 cn4

cn2 cn2

Θ'1(

:

h l/ n

cn

cn

cn

:


52/54

L1.$3

+ec!rsion tree


cn

cn4 cn4 cn4 cn4

cn2 cn2

Θ'1(

:

h l/ n

cn

cn

cn

UleaFes n Θ'n( :


53/54

L1.$4

+ec!rsion tree


cn

cn4 cn4 cn4 cn4

cn2 cn2

Θ'1(

:

h l/ n

cn

cn

cn

UleaFes n Θ'n(

%otal = Θ'n l/ n(

:


54/54

"oncl!sions

6 Θ'n l/ n( /ro7s more slo7l tan Θ'n2(.

6 %erefore9 mer/e sort asmtoti!all

beats insertion sort in te 7orst !ase.6 In ra!ti!e9 mer/e sort beats insertion

sort for n @ 30 or so.

Documents

l1 algorithmique