[go: up one dir, main page]
Scribd
Upload
48 views32 pages

CSC-335 ADT's & Data Structures (Chapter 10 - ADT Implementation: Recursion, Algorithm Analysis, and Standard Algorithms)

The document discusses recursion, algorithms analysis, and standard algorithms in C++. It provides examples of recursion including towers of Hanoi and parsing. It also covers implementing recursion, algorithm efficiency, big O notation, and standard algorithms like sorting that are available in the C++ standard template library.

Uploaded by

frankjamison
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
48 views32 pages

CSC-335 ADT's & Data Structures (Chapter 10 - ADT Implementation: Recursion, Algorithm Analysis, and Standard Algorithms)

The document discusses recursion, algorithms analysis, and standard algorithms in C++. It provides examples of recursion including towers of Hanoi and parsing. It also covers implementing recursion, algorithm efficiency, big O notation, and standard algorithms like sorting that are available in the C++ standard template library.

Uploaded by

frankjamison
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 32

CSC-335 ADTs & Data Structures (Chapter 10 ADT I ple entation: !

!ecursion" Al#orith Anal$sis" an% Stan%ar% Al#orith s&


Instructor: Christos Kolonis

Chapter Contents
10'1 !ecursion 10'( )*a ples o+ !ecursion: To,ers o+ -anoi. /arsin# 10'3 I ple entin# !ecursion 10'0 Al#orith )++icienc$ 10'5 Stan%ar% Al#orith s in C11 10'2 /ro3in# Al#orith s Correct (4ptional&

Chapter 456ecti3es
!e3ie, recursion 5$ loo7in# at e*a ples Sho, ho, recursion is i ple ente% usin# a run-ti e stac7 8oo7 at the i portant topic o+ al#orith e++icienc$ an% ho, it is easure% Descri5e so e o+ the po,er+ul an% use+ul stan%ar% C11 +unction te plates in ST8 (4ptional& Intro%uce 5rie+l$ the topic o+ al#orith 3eri+ication

10'1 !ecursion
A +unction is %e+ine% recursi3el$ i+ it has the +ollo,in# t,o parts An anchor or 5ase case
The +unction is %e+ine% +or one or 3alues o+ the para eter(s& ore speci+ic

An in%ucti3e or recursi3e case


The +unction9s 3alue +or current para eter(s& is %e+ine% in ter s o+ pre3iousl$ %e+ine% +unction 3alues an%:or para eter(s&

!ecursi3e )*a ple


Consi%er a recursi3e po,er +unction double power (double x, unsigned n) { if ( n == 0 ) return 1.0; else return x * power (x, n-1); } ;hich is the anchor< ;hich is the in%ucti3e or recursi3e part< -o, %oes the anchor 7eep it +ro #oin# +ore3er<

!ecursi3e )*a ple


Fig 10.2

=ote the results o+ a call


!ecursi3e calls !esolution o+ the calls

A >a% ?se o+ !ecursion


@i5onacci nu 5ers 1" 1" (" 3" 5" A" 13" (1" 30 +1 B 1" +( B 1 C +n B +n -( 1 +n -1
A recursi3e +unction
double Fib (unsigned n) { if (n <= ) return 1; else return Fib (n ! 1) " Fib (n !

);

A >a% ?se o+ !ecursion


;h$ is this ine++icient<
=ote the recursion tree

?ses o+ !ecursion

>inar$ Search
See source co%e =ote results o+ recursi3e call

?ses o+ !ecursion
/alin%ro e chec7er
A palin%ro e has sa e 3alue ,ith characters re3erse% 1(303(1 racecar

!ecursi3e al#orith

+or an inte#er

I+ nu#$igit%s <= 1 return true )lse chec7 +irst an% last %i#its nu#&10nu#$igits-1 an% nu# ' 10
i+ the$ %o not atch return +alse

I+ the$ atch" chec7 ore %i#its Appl$ al#orith recursi3el$ to: nu# ' 10nu#$igits-1 an% nu#$igits -

10

!ecursion )*a ple: To,ers o+ -anoi


!ecursi3e al#orith especiall$ appropriate +or solution 5$ recursion

Tas7
Do3e %is7s +ro le+t pe# to ri#ht pe# ;hen %is7 o3e%" ust 5e place% on a pe# 4nl$ one %is7 (top %is7 on a pe#& o3e% at a ti e 8ar#er %is7 a$ ne3er 5e place% on a s aller %is7

11

!ecursion )*a ple: To,ers o+ -anoi I%enti+$ 5ase case: I+ there is one %is7 o3e +ro A to C In%ucti3e solution +or n E 1 %is7s
Do3e top ost n 1 %is7s +ro A to >" usin# C +or te porar$ stora#e Do3e +inal %is7 re ainin# on A to C Do3e the n 1 %is7 +ro > to C usin# A +or te porar$ stora#e

Fie, co%e +or solution" @i# 10'0

12

!ecursion )*a ple: To,ers o+ -anoi =ote the #raphical steps to the solution

13

!ecursion )*a ple: /arsin#


)*a ples so +ar are %irect recursion
@unction calls itsel+ %irectl$

In%irect recursion occurs ,hen


A +unction calls other +unctions So e chain o+ +unction calls e3entuall$ results in a call to ori#inal +unction a#ain

An e*a ple o+ this is the pro5le o+ processin# arith etic e*pressions

14

!ecursion )*a ple: /arsin#


/arser is part o+ the co piler Input to a co piler is characters
>ro7en up into eanin#+ul #roups I%enti+iers" reser3e% ,or%s" constants" operators

These units are calle% to7ens


!eco#niGe% 5$ le*ical anal$Ger S$nta* rules applie%

15

!ecursion )*a ple: /arsin#


/arser #enerates a parse tree usin# the to7ens accor%in# to rules 5elo,:

An e*pression: ter 1 ter H ter ter H ter A ter : +actor I +actor H +actor : +actor H +actor A +actor: ( e*pression & H letter H %i#it

Note Notethe theindirect indirect recursion recursion

16

10'3 I ple entin# !ecursion


!ecall section J'0" acti3ation recor% create% +or +unction call Acti3ation recor%s place% on run-ti e stac7 !ecursi3e calls #enerate stac7 o+ si ilar acti3ation recor%s

17

I ple entin# !ecursion


;hen 5ase case reache% an% successi3e calls resol3e%
Acti3ation recor%s are poppe% o++ the stac7

18

10'0 Al#orith
-o, %o ,e

)++icienc$

easure e++icienc$

Space utiliGation a ount o+ e or$ reKuire% Ti e reKuire% to acco plish the tas7

Ti e e++icienc$ %epen%s on :
siGe o+ input spee% o+ achine Kualit$ o+ source co%e Kualit$ o+ co piler

These Thesevary varyfro fro one one !"atfor !"atfor to toanother another

19

Al#orith

)++icienc$

;e can count the nu 5er o+ ti es instructions are e*ecute%


This #i3es us a al#orith easure o+ e++icienc$ o+ an

So ,e

easure co putin# ti e as:

T(n& B co putin# ti e o+ an al#orith +or input o+ siGe n B nu 5er o+ ti es the instructions are e*ecute%

20

)*a ple: Calculatin# the Dean


Tas7 L ti es e*ecute%

1' (' 3' 0' 5' 2'

InitialiGe the sum to 0 InitialiGe in%e* i to 0 ;hile i M n %o +ollo,in# a& A%% *NiO to su 5& Incre ent i 5$ 1 !eturn mean = sum/n Total

1 1 n11 n n 1 3n 1 0

21

Co putin# Ti e 4r%er o+ Da#nitu%e As nu 5er o+ inputs increases


T(n& B 3n 1 0 #ro,s at a rate proportional to n

Thus T(n& has the Por%er o+ a#nitu%eP n The computing time o+ an al#orith on input of size n,
T(n) sai% to ha3e order of magnitude f(n)" ,ritten T(n) is O(f(n))

i+ C there is some constant C such that


T(n& M C+(n& +or all su++icientl$ lar#e 3alues o+ n

22

>i# 4h =otation
Another ,a$ o+ sa$in# this: Q The complexity o+ the al#orith 4(+(n&&' Q is

)*a ple: @or the Dean-Calculation Al#orith : T(n& is O(n)

=ote that constants an% +actors are i#nore%'

ultiplicati3e

23

>i# 4h =otation
+(n& is usuall$ si ple: n" n(" n3" ''' (n 1" lo#(n n lo#(n lo#(lo#(n =ote #raph o+ co on co putin# ti es

24

>i# 4h =otation
Rraphs o+ co on co putin# ti es

25

Co

on Co putin# Ti e @unctions

lo#(lo#(n --0'00 1'00 1'5A ('00 ('3( ('5A 3'00 3'3( 0'3(

lo#(n 0 1 ( 3 0 5 2 A 10 (0

n 1 ( 0 A 12 3( 20 (52 10(0 100A5J2

n lo#(n 0 ( A (0 20 120 3A0 (00A 10(00 (0SJ15(0

n( 1 0 12 20 (52 10(0 00S2 25532 100A5J2 1'1)11(

n3 1 A 20 51( 00S2 3(J2A (2(100 12JJJ(12

(n ( 0 12 (52 25532 0(S0S2J(S2 1'A002J)11S 1'15JS()1JJ

1'0J)10S 1'A)130A 1'15)11A 2'J)131525(

26

Co putin# in !eal Ti e
Suppose each instruction can 5e %one in 1 icrosecon% @or n B (52 inputs ho, lon# +or 3arious +(n&
@unction lo#(lo#(n 8o#(n n n lo#(n n( n3 (n 3 A '(5 ( 25 Ti e icrosecon%s icrosecon%s illisecon%s illisecon%s illisecon%s 1J secon%s 3'J1)20 centuries!!

27

10'5 ST89s Al#orith s


ST8 has a collection o+ #eneric al#orith s' ore than A0

not e 5er +unctions o+ ST89s container classes %o not access containers %irectl$'

The$ are stan%-alone +unctions


operate on %ata 5$ eans o+ iterators '

Da7es it possi5le to ,or7 ,ith re#ular Cst$le arra$s as ,ell as containers'

28

)*a ple o+ sort Al#orith


Co es in se3eral %i++erent +or s 4ne uses the < operator to co pare ele ents !eKuires that oper(tor<() 5e %e+ine% on the %ata t$pe
5ein# sorte% )*a ple pro#ra " @i# 10'J See e*a ple" @i#' 10'A

The sort al#orith Sort al#orith

can 5e use% ,ith arra$s

can ha3e a thir% para eter

The na e o+ a 5oolean +unction to 5e use% +or a less than See @i#' 10'S

29

10'2 /ro3in# Al#orith s Correct


De%ucti3e proo+ o+ correctness reKuire% Dust speci+$
The P#i3enP or precon%itions The Pto sho,P or post con%itions Pre and Algorithm => Post

a$ 5e

In sa+et$-critical s$ste s ,here li3es at ris7

30

)*a ple: !ecursi3e /o,er @unction


@unction:
double power (double x, unsigned n) { if ( n == 0 ) return 1.0; else return x * power (x, n-1); }

/recon%ition:
Input consists o+ a real nu 5er x an% a nonne#ati3e inte#er n

/ostcon%ition:
)*ecution o+ +unction ter inates ;hen it ter inates 3alue returne% is *n

31

)*a ple: !ecursi3e /o,er @unction ?se athe atical in%uction on n

Sho, postcon%ition +ollo,s i+ n = 0

Assu e +or n = )" e*ecution ter inates an% returns correct 3alue
;hen calle% ,ith n = ) " 1" in%ucti3e case return x * power (x, n ! 1) is e*ecute% Falue o+ n ! 1 is ) It +ollo,s that ,ith n = ) " 1, returns x * x) ,hich eKuals x)"1

32

You might also like