COMP 3007
Outline
Lectures
Assignments
Final Exam
Schedule
debircsed sa krow tsum melborp gnidoc hcae ot srewsna ruoY .gnidarg launam dna citamotua fo noitanibmoc a yb detaulave eb lliw snoissimbuS
.nigeb uoy erofeb snoitcurtsni eht fo lla dootsrednu dna daer evah uoy taht erusnE
seluR maxE emoh-ekaT )!snoissimbus etal oN( mp55:11 @ ht72 lirpA yadseuT :euD
laniF emoh-ekaT – 7003 PMOC
…gnidarG tuobA
7003 PMOC EMOH
.dehsinfi evah uoy retfa neve ,murof cilbup yna ot tset siht morf srewsna ro snoitseuq tsop ton oD .)”2 retpahc ,seton erutcel esruoc morF” .g.e( detic eb dluohs )seton erutcel .g.e( secruos dezirohtua morf deipoc edoC .ecruos ruoy etic dluohs uoy ,snoitulos ruoy ni esruoc eht fo edistuo morf stpecnoc esu uoy fI .tcudnocsim cimedaca rof noitatic a dna ,tset eht no orez fo edarg a )muminim ta( ni tluser lliw ,tenretni eht ro sreep morf )laitrap ro elohw( snoitulos fo gniypoc ro ,gnirahs ,noitaroballoc ynA .maxe siht fo noitelpmoc eht ni dewolla si noitaroballoc on yletulosbA
…noitaroballoc tuobA .)ylno serutaef egaugnal eroc( snoitulos ruoy ni stropmi dezirohtuanu yna esu esu ton yam uoY .melborp
a yb neddibrof ylticilpxe ton era yeht taht dedivorp ,ekil
uoy setaciderp/snoitarepo/snoitcnuf ni-tliub yna esu yam uoY
…seirarbil dna sni-tliub tuobA .dedarg eb lliw segaugnal gnimmargorp rehto on ,)defiiceps sa( golorP ro emehcS ni dedoc eb tsum snoituloS .epyt tcerroc eht fo era deilppus stupni emussa yam uoy ,defiiceps esiwrehto sselnU
.snoitnevnoc gniman noitcnuf dna elfi debircserp lla wollof uoy taht erusnE
ylgnorts si krow ruoy gnitset dna gnitnemucod tub ,gnitset dna noitatnemucod rof ylticilpxe skram on era erehT )!snoitulos ruoy tseT( .snoitulos tcerroc yllaitrap ro ,tcerrocni ,etelpmocni ot dedrawa skram trap on eb lliw erehT .melborp hcae fo stniartsnoc nevig eht nihtiw stupni elbanosaer lla rof noitseuq hcae yb
…senilediug gnimmargorP .degaruocne
]latot skram 24[ A traP
parta_
parta_
split
(split ‘c ‘(a b c d e)) ((a b)(d e))
(split ‘0 ‘(1 0 1 1 0 2 0 0 1)) ((1)(1 1)(2)(1))
?-split(x,[1,2,x,4,5],R).
?-split(z,[8,3,2,6,1,4],R).
start
R = [[1,2],[4,5]].
R = [[8,3,2,6,1,4]].
slice
(slice ‘(0 1 2 3 4 5 6 7 8 9) 3 8) (3 4 5 6 7)
end
¡ú ,.g.E .segnar nevig eht ni seulav gnitsixe yna edulcni dluohs tsilbus denruter eht neht ,sdnuob fo tuo era secidni nevig eht fo rehtie fI .)evisulcxe( dna )evisulcni( secidni eht neewteb tsil tupni eht fo tsilbus a snruter dna stnemugra sa secidni regetni owt dna
tsil a sekat taht
dellac etaciderp/noitcnuf a etirW ]skram 4[ .2
¡ú ¡ú
,.g.E ,.g.E ,.g.E ,.g.E
¡ú
¡ú
.yek fo ecnatsni hcae neewteb stsilbus fo tsil a otni tsil tupni eht stilps dna stnemugra sa tsil a dna
yek a sekat taht dellac etaciderp/noitcnuf a etirW ]skram 5[ .1 :snoitseuQ ehT
.)eno tsuj ni gnivlos er’uoy fi neve( segaugnal htob rof selpmaxe egasu eht daer ot erus eB :piT .edarg mumixam eht eviecer lliw uoy ,traP siht rof edarg mumixam eht naht erom nrae uoy fI .)hcae ton ,latot( skram detats eht x5.1 htrow si segaugnal htob ni noitseuq a gnivloS .traP siht rof skram lluf dliey lliw ecno noitseuq yreve gnivlos yltcerroC .evoba edarg mumixam eht llfiluf ot ekil d’uoy sa wef sa ro ynam sa evloS
.skram orez eviecer lliw srewsna tcerrocnI .skram lluf eviecer lliw srewsna gnikrow yltcerroC .skram fo rebmun a htiw detoned si noitseuq hcaE dellac elfi a ni snoitulos golorP lla tuP dellac elfi a ni snoitulos emehcS lla tuP .)!htob ro( golorP ro emehcS gnisu traP siht fo snoitseuq eht evlos yam uoY
.
.
:seluR ehT ]latot skram 24[
(slice ‘(a b c d e f g h i j) 5 25) (f g h i j)
?-slice([a,b,c,d,e,f,g],1,3,R).
?-slice([0,1,2,3,4,5],-10,3,R).
n
R = [b,c].
R = [0,1,2].
infuse
infuse
n
(infuse ‘(a b c d e) 2 1 ‘(x y))
(infuse ‘(1 2 3 4 5) 2 0 ‘(x y))
(infuse ‘(a b c d e) 2 1 ‘()) ?-infuse([1,2,3],1,1,[a,b,c],R). ?-infuse([1,2,3],3,1,[a,b],R). ?-infuse([0,1,2,3,4,5,6,7],4,2,[],R). R =
[0,1,2,3,6,7].
fold_once
(fold_once ‘(6 2.5 9 1 5 7 8 4)) (10 10.5 16 6)
?-fold_once([1,2,3.5,4,5],R).
(pos_diffs ‘(6 2 9 1 5 7 8))
1)
(pos_diffs ‘(1)) () ?-pos_diffs([1,2,3,4,4,6],R).
R = [6,6,3.5]
pos_diffs
(-4 7 -8 4 2 1)
R = [1,1,1,0,2].
(7 4 2
(a b x y d e)
(1 2 x y 3 4 5)
(a b d e)
R = [1,a,b,c,3].
R = [1,2,3].
¡ú
,.g.E ,.g.E ,.g.E ,.g.E ,.g.E ,.g.E
¡ú
¡ú ¡ú
¡ú
¡ú
,.g.E ,.g.E
,.g.E .secnereffid evitagen eht fo yna tuohtiw tub ,tsil eht ni tnemele evisseccus hcae neewteb secnereffid eht fo tsil eht snruter dna tnemugra sa srebmun erom ro orez fo tsil
¡ú ¡ú
a sekat taht dellac etaciderp/noitcnuf a etirW ]skram 3[ .5
¡ú ,.g.E ,.g.E .ti ot gnihtyna dda ton od ,tnemele elddim ralugnis a si ereht fI …cte ,tnemele_tsal_dnoces + tnemele_dnoces ,tnemele_tsal + tnemele_tsrfi :smus gniwollof eht fo tsil a snruter dna tnemugra sa srebmun fo tsil
a sekat taht
dellac etaciderp/noitcnuf a etirW ]skram 5[ .4
¡ú
¡ú
.deretlanu gnieb tsil tupni eht ni tluser dluohs secidni dilavnI :etoN
lliw rewef neht elbaliava era smeti tegrat rewef fi ,rebmun dedivorp eht tsom ta eb dluohs devomer stnemele fo rebmun eht :etoN .noitacol taht ta smeti wen eht fo lla tresni dna ,xedni nevig eht ta tsil tupni eht morf smeti evomer dluohs noitcnuf ehT .smeti wen fo tsil a dna , regetni evitagen -non a ,xedni regetni na ,tsil tupni na :stnemugra sa gniwollof
eht sekat taht dellac etaciderp/noitcnuf a etirW ]skram 5[ .3
¡ú ¡ú
¡ú
,.g.E ,.g.E ,.g.E
¡ú
.devomer eb
(globs ‘(a a g g a a a a t c))
1) (c 1))
globs([t,t,t,a,a,c,g,t],R).
[g,1],[t,1]].
all_sums kn
(all_sums 2 7) (16 25 34 43 52 61 70) (all_sums 3 0) ()
?-all_sums(3,4,R). R =
[103,112,121,130,202,211,220,301,310,400]
prune
(prune ‘(1 2 () 3 4)) (1 2 3 4) (prune ‘(a (b () (c () d))()()(()) e))
e)
(prune ‘()) ()
(a (b (c d))
kn
?-prune([1,2,[],3,4],R). R = [1,2,3,4]. ?-prune([[],[],[[],1,[[]]]],R). R = [[1]].
minima
globs
((a 2) (g 2) (a 4) (t
R = [[t,3],[a,2],[c,1],
eht fo edistuo secidni ynA stnemele gniruobhgien yletaidemmi sti fo htob naht rellams si hcihw tnemele yna sa denfied si aminim lacol a ,melborp siht fo ekas eht roF .tsil eht ni aminim lacol lla fo secidni eht fo tsil a snruter dna tnemugra sa srebmun fo
tsil a sekat taht
dellac etaciderp/noitcnuf a etirW ]skram 5[ .9
¡ú
,.g.E
¡ú
¡ú
,.g.E ,.g.E ,.g.E
,.g.E .erutcurts dna redro lanigiro rieht ni eert tupni eht morf stnemele tsil -ytpme-non lla niatnoc dluohs eert gnitluser ehT .eert dedivorp eht edisni morf stsil ytpme lla sevomer dna tnemugra sa )tsil detsen(
eert a sekat taht dellac etaciderp/noitcnuf a etirW ]skram 5[ .8
.melborp siht rof stigid deredisnoc eb ton dluohs seorez gnidael :etoN .redro gnidnecsa ni , ot mus stigid esohw sregetni tigid- lla fo tsil a snruter dna ,stnemugra sa dna sregetni evitagen-non owt
¡ú
sekat taht dellac etaciderp/noitcnuf a etirW ]skram 6[ .7
¡ú
¡ú
,.g.E ,.g.E ,.g.E
¡ú
¡ú
¡ú ,.g.E
¡ú
.eulav taht fo tnuoc eht dna eulav eht fo )tsil tnemele-2( riap
a sa derots era tsil tupni eht morf seulav evitucesnoc fo secneuqes erehw tsil a snruter dna tnemugra sa )smota/(slobmys fo
tsil a sekat taht dellac etaciderp/noitcnuf a etirW ]skram 4[ .6
,.g.E
(minima ‘(1 5 9 3 5 4 8)) (3 5) (minima ‘(-42 25 -1)) (0 2) ?-minima([0,1,0,0,0,-1,1,1,-1,1,0,1],R).
[5,8,10].
?-minima([6,4,2,1,3,5],R). R = [3].
partb1_generator.scm
list-generator
R =
(define f (list-generator (lambda(x)#t) (lambda(x)x))) f #
((list-generator odd? (lambda(x)(* x 2))) 1 20 3) (2 14 26 38)
((list-generator (lambda(x)#t)(lambda(x)x)) 16 0 -4)
(16 12 8 4 0)
partb2_contour.scm
dellfi eb yam margaid eht yb debircsed ton edoc fo senil ynA .eno dnfi ylno deen uoy ,melborp siht ot snoitulos elbissop ynam era erehT
:setoN .margaid ruotnoc gniwollof eht ni detciped etats tnemnorivne eht etaerc ot etucexe lliw taht margorp
¡ú
¡ú
,.g.E ,.g.E
emehcS a etirw ,
dellac elfi a nI ]skram 7[ .2
,.g.E .tsil ytpme na nruter dluohs egnar ytpme ro dilavni na ni tluser dluow taht sllac ynA .eurt snruter noitcnuf etaciderp eht hcihw rof egnar nevig eht ni sregetni eht fo lla ot noitcnuf rotatum eht gniylppa fo tluser eht niatnoc dluohs stsil gnitluser ehT .noitamrofni dedivorp eht fo lla no desab seulav fo tsil a nruter dna ,stnemugra sa )eulav pets a dna ,eulav pots a ,eulav trats a( sregetni eerht ekat dluohs noitcnuf gnikam-tsil denruter ehT .noitcnuf gnikam-tsil a snruter dna tnemugra sa )rotatum a dna etaciderp a( snoitcnuf owt sekat taht dellac noitcnuf
emehcS a etirw , dellac elfi a nI ]skram 6[ .1 .selfi )defiiceps( nwo rieht ni trap siht morf smelborp lla rewsnA
¡ú
,.g.E ,.g.E ,.g.E
¡ú
B traP ,.g.E
¡ú
¡ú
.0 fo eulav a evah ot deredisnoc eb dluohs tsil tupni
eht fo edistuo secidni ynA .stnemele gniruobhgien yletaidemmi
¡ú
¡ú
partc1_infix.scm
tree := number
tree := (operator tree tree)
eval-prefix
nevig eht esrevart dluohs noitulos ruoY .eert noisserpxe xfierp nevig eht fo eulav detaulave eht nruter dluohs noitcnuf ehT
:mrof gniwollof eht htiw tnemugra sa eert noisserpxe xfierp a sekat taht dellac noitcnuf a etaerC ]skram 4[ .i
.elfi siht ni snoitseuq gniwollof eht ot srewsna ruoy ecalp dna dellac elfi a etaerC .1
.seman noitcnuf dna elfi dedivorp lla wollof ot erus eB .edarg ruoy sdrawot detnuoc eb lliw owt tseb ruoy ylno ,eerht lla evlos uoy fI .smelborp 3 gniwollof eht fo 2 yna evloS ]latot skram 03[
.elbissop eb lliw skram traP .kram latot eht fo tnuoma emos htrow si noitulos eht fo liated nettirw yltcerroc hcaE .)margaid eht yb defiiceps ton era stuptuo( rorre tuohtiw noitcnuf tsum melborp siht ot noitulos ruoY .)1 enil gnieb elfi eht fo enil tsrfi eht htiw( tcerroc deredisnoc eb ot elfi eht ni enil tcerroc eht no eb tsum noitulos ruoy fo seniL )srebmun enil dedivorp eht htiw noitulos ruoy ngila ot desu eb nac ecapsetihw ro ,stnemmoc ,edoc fo senil ,.e.i( tfi ees uoy sa
C traP
(eval-prefix ‘(+ (+ 1 2) 3)) 6
(eval-prefix ‘(* (+ 1 2) (* 1 (+ 1 (- 4 2))))) 9
parse-infix
infix := number
infix := (infix operator infix)
infix := (infix operator infix operator infix)
infix := (infix operator infix operator infix …)
(parse-infix ‘(10 – 5)) (- 10 5) (parse-infix ‘(1 + 2 – 3)) (- (+ 1 2) 3)
3))
(parse-infix ‘(1 + 2 * 3 – 4))
(parse-infix ‘(1 + (2 + 2) * 3))
(- (+ 1 (* 2 3)) 4)
(+ 1 (* (+ 2 2)
eval apply
eval let
let
lambda
lambda
(let ((a 1)(b 2))(+ a b))
let*
snaem sihT .snoisserpxe etaulave ylreporp nac ti taht os rehtruf noitatnemelpmi ICM dedivorp eht dnetxE ]skram 01[ .ii
:si noisserpxe tel elpmaxe nA .snoisserpxe etaulave ydaerla nac ICM eht dna , a sa desserpxe eb nac a :tniH .)s(reirrab noitcartsba tnaveler eht gnidliub dna ,noitcnuf eht gnidnetxe snaem sihT .snoisserpxe etaulave ylreporp nac
ti taht os noitatnemelpmi ICM dedivorp eht dnetxE ]skram 5[ .i
.elfi ruoy fo pot eht ta srebmun enil fo gnitsil trohs a gnisu ekam uoy segnahc eht lebal ylraelc ot erus eB .)elfi eht emaner ton od :etoN( .mcs.ratstel_icm_2ctrap :woleb smelborp
eht ot snoitulos ruoy htiw elfi gniwollof eht dnetxe dna daolnwoD .2
na sekat taht ¡ú
dellac noitcnuf a etaerC ]skram 11[ .ii
¡ú ¡ú
,.g.E ,.g.E ,.g.E ,.g.E
¡ú
¡ú
.dewollof eb dluohs selur ytivitaicossa dna ecnedecerp dradnatS .}/ ,* ,- ,+{ :tes eht fo eno eb yam srotarepO
:mrof gniwollof eht evah lliw seert noisserpxe xfinI .eert noisserpxe xfierp tnelaviuqe na snruter dna tnemugra sa eert noisserpxe xfini
,.g.E ,.g.E ./ ,* ,- ,+ :era snoitarepo ylno eht taht emussa yam uoY .snoitcnuf ro ni-tliub eht llac ton dluohs dna noisserpxe
¡ú
a b))
let* let*
let
(let* ((a 2)(b (+ a 1))) (*
eval
edge(SourceCity, DestinationCity, DistanceInKm).
sourceCity
DistanceInKm DestinationCity
connected(A,B)
?- connected(ottawa,gatineau). True. ?- connected(ottawa,toronto). False.
commuterPath(A,B,L)
ytic dna A ytic neewteb htap eht gnola seitic fo tsil eht si L fi sdeeccus taht etaciderp golorP a etaerC .yenruoj rieht gnola ecneirepxe lliw yeht taht srevopots eht fo gnitsil elpmis a htiw sretummoc ruo edivorp ot ekil dluow ew ,krowten levart ruo fo syawhtap gnignop-gnip cinosrepyh
eht fo stceffe gnitneirosid eht ecuder ot ,txeN ]skram 4[ .ii
¡ú ,.g.E
¡ú ,.g.E .B ytic ot A ytic morf segde erom ro 1 fo htap a si ereht fi sdeeccus taht etaciderp golorP a gnitaerc yb gniog er’yeht erehw teg nac yeht fi tuo dnfi sretummoc ruo pleh esaelP .esabegdelwonk dedivorp eht gniterpretni
setacidni %
ytlucffiid gnitroper era sretummoc ruo ,yltsriF ]skram 3[ .i
.smelborp gniwollof eht gnivlos yb gniog er’yeht erehw ot teg sretummoc ruo pleH
. ta yawa sretemolik
gnidne dna ni gnitrats stsixe egde detcerid a
:tamrof gniwollof eht ni ,krowten noitatropsnart ruo ni segde detcerid eht fo lla fo gnitsil eht stneserper esabegdelwonk dedivorp ehT .ward modnar yb ,elbissop yaw tseriaf eht ni dediced )ylbatterger( saw metsyS noitatropsnarT ebut-muucaV deepsrepyH wen eht rof snoitatS fo noitallatsni ehT
.)elfi eht emaner ton od :etoN( .lp.noitatropsnart_3ctrap :woleb smelborp
eht ot snoitulos ruoy htiw elfi gniwollof eht dnetxe dna daolnwoD .3
:si noisserpxe elpmaxe nA .snoisserpxe fo ecneuqes detsen a sa desserpxe eb nac a :tniH .)s(reirrab noitcartsba tnaveler eht dna ,noitcnuf eht gnidnetxe rehtruf
?- commuterPath(ottawa, gatineau, Path). Path = [ottawa, thunderBay, kelowna, gatineau].
pathLength(A,B,Dist)
?- pathLength(ottawa,gatineau,Len).
6835.209999999999.
getCycle(A,C)
?- getCycle(ottawa, Cycle). Cycle = [ottawa,edmonton,ottawa] ; False.
Len =
longestPath(A,L)
?- longestPath(ottawa,L). L = [ottawa, thunderBay, kelowna, gatineau, saskatoon, barrie, oshawa].
eldnah dluohs setaciderp eseht fo snoitatnemelpmi ruoY :seton emoS
¡ú ,.g.E .A ytic ta setanigiro taht krowten noitatropsnart ruo ni segde fo )mk
ni( htap tsegnol eht si L ffi sdeeccus taht
etaciderp golorP a etaerc ,eletneilc siht evres oT
!smelborp yldlrow rieht naht retsaf gnillevart nac ylbissop yeht sa emit hcum sa gnidneps tuoba erom dna ,gniog er’yeht erehw tuoba ssel erac sregnomerusaelp esehT .ssenisub ruo ot noitalupop eht fo tnemele gnikees-llirht a detcartta sah ecirp wol
-wol dexfi a rof levart cinosrepyh taht tuo snrut tI ]skram 2[ .v
¡ú ,.g.E .A ytic ta sdne dna setanigiro hcihw segde gnitsixe fo elcyc gnitaeper-non a si C fi sdeeccus taht etaciderp golorP a etaerc esaelp ,”sliated” eseht revo nrecnoc mlac pleh oT .emoh kcab teg ot yaw yna tuohtiw yrtnuoc eht ssorca sdeeps cinosrepyh ta deltruh gnieb fo tcepsorp eht htiw ysaenu er’yeht taht tuo
detniop evah scitirc gninrecsid erom ruo fo emoS ]skram 2[ .vi ¡ú ,.g.E
.B ytic dna A ytic neewteb htap eritne na fo )mK ni( ecnatsid latot eht si tsiD fi sdeeccus taht etaciderp golorP a etaerC .levart lliw yeht ecnatsid eht fo yratnemilpmoc a reffo ot ekil dluow ew ,sretummoc “pihsrebmeM
munitalP” ruo rof erutaef dednetxe na sA ]skram 4[ .iii
¡ú ,.g.E .)stsixe htap a hcus fi( B ytic dna A ytic neewteb htap eht gnola seitic fo tsil eht si L fi
.etad eud eht erofeb em tcatnoc ,noissimbus htiw seussi gnivah era uoy fI .golorP-IWS ni nur ot nettirw eb dluohs edoc golorP llA .)enil gnal# a edulcni ton oD( .SR5R ni nur ot nettirw eb dluohs edoc emehcS llA .noitseuq taht rof 0 fo kram a ni tluser lliw )snoitidnoc tluafed rednu golorp-IWS ro SR5R gnisu tekcaRrD ni( elbadaol/elbannur ton era taht selfi edoc ynA .yllufsseccus detelpmoc si noissimbus eht taht GNIRUSNE dna selfi lla gnittimbus rof elbisnopser era uoY !srewsna ruoy timbus ot tset eht fo etunim tsal eht litnu tiaw ton oD .dedarg eb lliw SNOISSIMBUS ETAL ON .etad eud eht erofeb nraeLuc gnisu tnemngissa ruoy timbuS
.noissimbus ruoy rof
dellac elfi piz. elgnis a otni selfi lla enibmoC
.)s(noitseuq detceffa eht rof orez fo edarg a ni tluser lliw snoitnevnoc gniman debircserp eht wollof ot eruliaF .noissimbus ruoy rof seman noitcnuf dna elfi dedivorp lla dna yna esu tsum uoY
.gnitset rof skrowten noitatropsnart elpmas rellams tcurtsnoc ot lufpleh eb yam tI .eriuqer uoy taht setaciderp repleh lanoitidda yna tcurtsnoc yam uoY .)krowten tropsnart eht fo etats tnerruc eht no desab snoitulos edocdrah ton od .ei( elbaegnahcnu era esabatad eht ni stcaf eht taht emussa ton dluohs setaciderp ruoY .)xetrev tsal dna tsrfi eht ylbissop tpecxe( setacilpud on htiw segde yb detcennoc secitrev fo ecneuqes a ot srefer htap A .spool etinfini ni kcuts gnitteg tuohtiw selcyc
noissimbuS