[SOLVED] CS DNA 12/18/2020 UCLA CS 131 lecture 2020-12-09

12/18/2020 UCLA CS 131 lecture 2020-12-09

https://ccle.ucla.edu/mod/kalvidres/view.php?id=3476138
1/7
keew slaniF 0202 llaF
90-21-0202 erutcel 131 SC ALCU / 01 keeW / 1-131ICSMOC-F02 / setis yM ELCC
sneppah tahw sereH
ylno eulav yb llac seod C tahw od :hcaorppa rehtonA
dewolla si noitatnemelpmi rehtie edoc tsaf etareneg nac srelipmoc os
,gnisaila od ton dluohs smargorp :nartroF pu evig :hcaorppa enO
sretsiger otni seulav ehcac tnac edoc a doog sa etareneg tnac relipmoc snaem * sremmargorp ot gnisufnoc erom edoc sekam * elbairav emas eht rof seman owt *
.3 snruter syawla llac ralucitrap siht tuB .3 ot tnemugra eht tes neht ,eulav taht ot i tes dna ,eno sulp gra nruter yas dluow edis dnah tfel fo gnidaer evian A .A ?eulav nruter eht ot dedda eulav dlo eht gnitteg saw ti daetsni tub ?eulav i tsetal eht htiw tluser eht gnitcepxe saw noitcnuf eht fo rellac eht taht melborp eht saw ,elpmaxe tsif eht yb desufnoc tib a llits ma I .Q
;)i&(f nruter
;)i(f nruter :rellac
;i nruter ;3 = a* ;1 + a* = i
}} ;i nruter ;3 = a ;1 + a = i
)a* tni( f tni ;01 = i tni
{{ )a& tni( f tni ;01 = i tni :ees uoy tahw sereH
)gnisaila :melborp a sah( )ycneiciffe yb detavitom( ecnerefer llac eulav yb llac
sliated etunim-tsal yna revoc ot )trats fo emit seificeps rartsigeR( trats eht ta noisses mooZ
:gnisailA
gnissap retemaraP
ELCC no slanif tsap tsop llI noissucsid gnirud weiver
flah dn2 gnizisahpme ,ssalc elohw eht srevoC .wodniw ruoh-42 a nihtiw sruoh eerht kcip uoY
mretdim eht ekil maxe laniF .stnemngissa rof yad tsal si yadirF
ffuts nimda 90-21-0202 erutcel 131 SC ALCU
TREGGE-1-131ICSMOC- 0202llaF segaugnaL gnimmargorP

12/18/2020 UCLA CS 131 lecture 2020-12-09

https://ccle.ucla.edu/mod/kalvidres/view.php?id=3476138
2/7
emit elipmoc ta rucco yaw psiL lausu eht ni margorp tneserper taht atad emehcS
snekot fo secneuqes ++C ,C margorp ruoy fo seceip era stnemugra
eruliaf litnu tsael ta emas eht stnemugra owt eht sekam hcihw eellac dna rellac neewteb hctam nrettap
.selbairav labolg htiw ro rehto hcae htiw palrevo sretemarap on hcihw ni edoc etirW .A ?gnisaila tuohtiw ecnerefer yb llac gnisu fo elpmaxe eht si tahW .Q
) ,emehcS ,++C ,C( sllac orcam
)golorP( noitacifinu yb llac
smelborp gnisaila on tneiciffe ssel
rellac eht ot eellac morf kcab deipoc seulav snruter ,setupmoc eellac
eellac ot rellac morf deipoc seulav tluser yb llac + eulav yb llac = tluser-eulav yb llac
.ylevitcepser ,xcr% ,xbr% ,xar% ni era stluseR .ylirassecen ton tub ,retniop aiv enod eb nac tI .A
?lufpleh yllaer ton si tluser yb ssap ro ,elbissecca ton si taht retniop a ssap ot evah ew snaem taht seod ,tluser yb llac roF .Q
.remmargorp eht ot elbissecca ton era sretniop gniylrednu esuaceb refaS
))v ,nidts( daer( fi ;v rahc
} ;eurt nruter ;]++i[fub>-tupni = rahc_tupni
{ )rahc_tupni tluser rahc ,tupni* ELIF( daer loob
rellac eht ot kcab deipoc si eulav taht snruter eellac eht nehw ti ot gningissa yb tnemugra eht senimreted eellac
tnemugra eht etaulave tnseod rellac tluser yb llac
)adA( hcaorppa rehtonA
{ )b& tni ,a& tni( f tni
ELCC
secnerefer tnaw uoy fi sretniop ssap nac uoy
;)y ,x(f ;y ,x tni
} ;2 + i = b ;1 + b = a
;i tni

12/18/2020 UCLA CS 131 lecture 2020-12-09

https://ccle.ucla.edu/mod/kalvidres/view.php?id=3476138
3/7
,llac evisnepxe na si retemarap lautca eht taht eb dluoc tI .eussi ycneiciffe siht lla htiw melborp a serehT
.enod eb ot deen yllautca tnod taht ffo sgniht tup uoy fi ,niw a eb nac noitaulave yzaL
.krow lliw eman yb llac
tub ,hsarc lliw eulav yb llac ,0 == ezis fI
;)ezis / mus ,ezis( egareva_tnirp
} ;)gva ,nd% si egarevA(ftnirp
)gva tni ,n tni( egareva_tnirp tni elbailer erom eb nac eman yb llaC
} ;]i[ra*]i[ra nruter
;)p(pumus nruter ;)]i[ra*]i[ra(pumus nruter
{ )diov(nufym tni ;]0001[ra tni
{ )diov(nufym tni ;]0001[ra tni
)++i ;0001<i ;0=i( rof;a tni;e =+ a )++i ;0001<i ;0=i( rof))diov( )e*( tni(pumus tni)e eman tni(pumus tni ;i tni ;i tniv knuht;a nruter ;)(e =+ a}} ;a nrutersretniop : ecnerefer yb llac :: snoitcnuf : eman yb llac .eman yb llac!cipot txen ym stahT .A ?otni llaf noitcnuf kcabllac seod erehW .Q1+2+x margorp a fo eceip rehtona teg ot )2+x ,1(m dnapxE 2+x margorp a fo eceip a teg ot )2(n dnapxE.dednapxe-orcam era sretemarap eht tub ,seY .A ?sehcaorppa yb-llac rehto eht fo yna ot desoppo sa ,sretemarap eht fo noitaulave on od nac ti ,emit elipmoc ta enod sti ecniEs ,LsllCacCorcam htiw oS .Qesle ;)”n*”(ftnirp)diov(p tni }})0 == n( fi{{;a tni {{))2(n ,1(m 12/18/2020 UCLA CS 131 lecture 2020-12-09 https://ccle.ucla.edu/mod/kalvidres/view.php?id=34761384/7)ekatsim a saw ti – ecnamrofrep rof drowyek retsiger a evah C ,++C :edisA()tlas esu ro noitcnuf gnihsah terces a esu :osesac lamron rof rewols tub ,siht rof retteb si eirt ?siht evlos ot woh :edisA(4223433 = )”kcolB eneG”(h 4223433 = )”7fgdsapvbhcx.rewq794c”(h 4223433 = )”*&#038;*&#038;(ds41″(h”7fgdsapvbhcx.rewq794c” ,”*&#038;*&#038;(ds41″ yreuq eussi noitcnuf hsah eht ta kool.nwod elgooG gnirb ot gniyrt si rotitepmoc elgooG a esoppuS .eno dab a si noitcnuf gnihsah eht esoppuS… tsil rehtona = ]”kcornielK neL”[d srewsna fo tsil = ]”kcolB eneG”[dsehcraes nommoc fo stluser sehcac d yranoitcid sihT yas ,”kcolB eneG”sehcraes bew ni rucco sesarhp nommoc ynaM nohtyP ni revres bew hcraes elgooG niaM gnihsah rof nommoc si dezitroma )1(O ~.elbat hsah a fo taht si ledom tsoc gniylrednu 79 = ]’hgfed'[d72 = ]’cba'[d .seiranoitcid nohtyP rof ledom tsoc ,.g.E.tnemeganam paeh ,.g.E .ekas sycneiciffe roF .skrow margorp ruoy woh fo ledom latnem a evah ot tnatropmi stI.doog ytterp si deen yb llac ,stceffe edis kcal uoy fI .deen yb llac htiw krow ton dluow elpmaxe pumus eht ,seY .A?thgir ,esac taht ni krow ton dluoc gnihcac os ,dellac si ti emit yreve segnahc knuht eht yb denruter tluser eht )pumus( elpmaxe tsrif eht htiw tuB .Q?))d(nel(O ?)1(O ]’cba'[d nruter.elbatrop eb ton thgim yehT .etelosbo emoceb yehT:sledom tsoc fo edisnwoD)tnirp ,.g.e( tsum yletulosba ti litnu ti fo yna od tnseod ti dna,tsil od-ot suomrone na setupmoc margorp ruoYpots neht tub ]3[s ,]2[s ,]1[s ,]0[s etupmoc // )]3[s( tnirp )… srebmun emirp lla fo tes …( = s tel.noitaulave yzal hsup yeht – tceffe taerg ot siht esu lleksaH ekil segaugnal gnimmargorp lanoitcnuFecno tsom ta knuht eht sekovni eellac tluser eht ehcac + eman yb llac = deen yb llac.E e v iL s n eC p xC e o o t e b n a c s i h T .emit yreve esnepxe taht rucni lliw eellac eht ossledom tsoC 12/18/2020 UCLA CS 131 lecture 2020-12-09https://ccle.ucla.edu/mod/kalvidres/view.php?id=34761385/7.)R ,C ,E(m % ]11=rr ,01=w ,5=v[ ,.g.e ,sriap eulav-eman fo tsil a si C txetnoc A % .R eulav eht si ,C txetnoc a ni ,E fo gninaeM %!psiL ni nettirw reterpretni na si psiL rof scitnames lanoitarepo cissalc ehTyrotcafsitasnu si siht yllacihposolihp ?pots ew od nehw snaem margorp LM na tahw dnatsrednu nac uoy os.LM fo tesbus a rof scitnames lanoitarepo na sedivorp rebbeWsegaugnal lanoitcnuf ot dnopserroc .noitcnuf gninaem eht ylppA sgninaem ot smargorp morf noitcnuf a edivorpsegaugnal cigol ot dnopserroc .ekil uoy seitreporp revetahw evorP egaugnal eht rof ecnerefni fo selur dna smoixa evig)1rpxE(batmys -< )3rpxE(batmys )1rpxE(batmys -< )2rpxE(batmystni = )3rpxE(epyt & tni = )2rpxE(epyt fi -< )1rpxE(epyt 3rpxE + 2rpxE > 1rpxE
gninaem eht tuoba ofni su evig taht selur citnames )xatnys eht tuoba( elur rammarg hcae htiw etaicossa
ereh timil a sedivorp melborP gnitlaH eht redrah *seod* ti tahw gnivresbo yb
*snaem* ti tahw wonk ot margorp eht nur ot deen uoy scitnames cimanyd reisae
swonk relipmoc a tahw
snur margorp eht erofeb ecuded ylisae nac uoy tahw scitnames citats
mrof fo evitcepserri ,margorp a fo gninaem scitnames melborp devlos margorp a fo mrof )skeew 2 tsrif( xatnys
.)E(regetni -: )E ,_ ,E(m
elcitra etinifed eht :*eht* :yranoitciD hsilgnE
,golorP wonk uoy si noitpmussa :si aedI .golorP ni nettirw
segaugnal evitarepmi ot dnopserroc .reterpretni eht no margorp eht eht nuR egaugnal eht rof reterpretni na evig
taolf esle tni neht
:aedi cisab htunK srammarg etubirtta
lanoitatoned
:elpmaxe scitnames citats
?*naem* margorp a seod tahW scitnameS
ELCC
)smelborp emas eht fo emos sah enilni(
citamoixa
lanoitarepo scitnames cimanyd

12/18/2020 UCLA CS 131 lecture 2020-12-09

https://ccle.ucla.edu/mod/kalvidres/view.php?id=3476138
6/7
segaugnaL gnimmargorP 007 txeN ehT repap s0691 .segaugnal gnimmargorp fo yrotsih A !retpahc tsaL
.evisnepxe eb nac sfoorp eseht gnioD
.noisrucer htiw siht od osla nac uoY .margorp eht fo etats eht no tniartsnoc a evah uoy ,pool eht fo dne eht ta eurt fI
pool eht fo trats eht ta laivirT
)++n ;0001 < n ;0=n( rof .evitisop si ]i[a ,n<i=<0 roFpool eht hguorht emit hcae eurt – stnairavni pooL !seY .A ?stnairavni evorP .Q.D.C.G setupmoc yllautca )b,a(dcg taht evorp uoy ,smargorp fo seitreporp evorp uoy stel tI ereht laed gib a era scitnames citamoixa.gnipocs citats ton ,gnipocs cimanyd % .)R ,]C|laV=X[ ,E(m ,)laV ,C ,A(m ,))E,X(nuf ,C ,F(m————– .gnipocs cimanyd ton ,gnipocs citats % .)R ,]fC|laV=X[ ,E(m ,)laV ,C ,A(m ,))fC,E,X(nuf ,C ,F(m031 SC ni siht tuoba eroM-: )R ,C ,)A,F(llac(m AF%.))E,X(nuf ,_ ,)E,X(nuf(m E>-X nuf %
ELCC
-: )R ,C ,)A,F(llac(m AF%
.))C,E,X(nuf ,C ,)E,X(nuf(m E>-X nuf %

.)R ,]C | 1V=raV[ ,E(m ,)1V ,C ,laV(m
-: )R ,C ,)E,laV,raV(tel(m E ni laV=raV tel %
.)C ,laV=raV(rebmem -: )laV ,C ,raV(m
.2V+1V si R ,)2V ,C ,2E(m ,)1V ,C ,1E(m
-: )R ,C ,2E+1E(m

12/18/2020 UCLA CS 131 lecture 2020-12-09
0:00 / 1:44:32 1x

https://ccle.ucla.edu/mod/kalvidres/view.php?id=3476138
7/7

ppa elibom eht teG
)SPAC( cvShcysP/snuoC ytilibisseccA ALCUyM rartsigeR ALCU | sknil ALCU thgirypoC ycavirP tuobA tcatnoC stnegeR CU 0202
kniL mooZ A1 noissucsiD
70-21-0202 erutcel 131 SC ALCU
ELCC
ot pmuJ