Oefeningen voor de oefeningenles. Oefening 1

Oefeningen voor de oefeningenles Oefening 1

Gegeven een arbitraire binaire zoekboom T met n toppen en een (andere of gelijke) binaire zoekboom T 0 die ook n sleutels bevat. Beschrijf een algoritme dat in lineaire tijd (dus tijd O(n)) de boom T 0 zo verandert (door veranderen van de kinderen), dat T 0 isomorf is met T (maar nog altijd een zoekboom met dezelfde sleutels als vroeger is). • Defini¨eer eerst wat isomorf precies betekent. Denk aan de cursus Discrete Wiskunde. • Beschrijf het algoritme. Tip: bepaal eerst paren (x, y) met x ∈ T, y ∈ T 0 van toppen die gelijke posities in de verschillende bomen moeten hebben. Maar er zijn ook andere mogelijkheden om zo’n algoritme te ontwerpen. . . • Toon aan, dat het algoritme juist is – dus dat de boom die gebouwd wordt echt isomorf met T is.

Oefening 2

Verwijder sleutel 6 uit deze AVL-boom:

8

5 2

0

3

16

11

7 4

1

13

6

10 9

15

12 14

18 17

19 20

Oefening 3

In DA1 hebben jullie de hersteloperaties voor AVL bomen geformuleerd door middel van enkelvoudige rotaties en dubbele rotaties. In de les hebben jullie gezien dat je deelbomen kan vervangen door andere deelbomen met dezelfde sleutels. Herschrijf de regels voor het herstellen van AVL-bomen door de deelboomvervangmethode te gebruiken.

Oefening 4

Stel dat voor grote h het minimum aantal toppen t(h) van een boom met hoogte h voldoet aan t(h) ≥ 4h+2/8. Toon aan dat de boom logaritmische diepte heeft (dus h is O(log t) met t het aantal toppen) en bepaal de constanten.

Oefeningen voor de oefeningenles Oefening 5

Als je een element uit een splayboom verwijdert, wordt de ordening ook verstoord. Sleutels worden in de richting van de bladeren geschoven die misschien vrij vaak opgezocht worden. Om sleutels die dicht bij de wortel zitten daar te houden, lijkt het verstandig b.v. als je een blad verwijdert de boom helemaal niet te veranderen. Toon aan dat als je op deze manier sleutels verwijdert er reeksen van bewerkingen bestaan zodat n bewerkingen op een initi¨eel lege splayboom gemiddeld O(n) stappen per bewerking vragen (de hele reeks dus O(n2)).

Oefening 6

1. Geef een algoritme voor het bepalen van de sleutel in een gegeven binaire zoekboom die het dichtst bij een gegeven sleutelwaarde x ligt (dus x zelf als de sleutel erin zit). • Als de zoekboom een AVL-boom is, kan je dan garanderen dat je de sleutel in tijd O(logn) kan vinden? Toon aan dat jouw antwoord juist is. 2. Geef een algoritme voor het bepalen van alle sleutels in een gegeven binaire zoekboom die hoogstens d (met d > 0) van een gegeven sleutelwaarde x verschillen. • Als de zoekboom een AVL-boom is, kan je dan garanderen dat je de sleutels in tijd O(logn) kan vinden? Toon aan dat jouw antwoord juist is.

Oefening 7

Voeg de sleutels 10,20,30,25,40,5,2 in deze volgorde toe aan een 2-3 boom.

Oefening 8

Stel dat een algoritme A gegeven is. De functie f (n) geeft de grootste tijd die het algoritme vraagt als hij op een input van n bytes wordt toegepast. Je wil tonen, dat f (n) niet Θ(n2) is. Wat moet je precies tonen? De bedoeling is niet, het echt te tonen (dat is ook niet mogelijk, omdat je noch f () noch A kent), maar gewoon van de definitie van Θ(n2) te vertrekken en dan met de middelen die jullie in de logica les hebben geleerd uit te vissen wat je moet tonen. Geef de formule die het resultaat van deze berekeningen is en geef ook uitleg!

Oefeningen voor de oefeningenles Oefening 8 Deze oefening maakte deel uit van het examen van het vorige jaar. Als jullie dus helemaal alleen proberen deze oefening op te lossen krijgen jullie al een gevoel ervoor hoe het examen gaat zijn, hoeveel tijd jullie van zo’n oefening nodig hebben, etc.

a.) Wat is in het slechtste geval de diepte van een 2-3-boom met n sleutels en wat is de diepte in het beste geval ? Wat zijn de beste en slechtste gevallen ? (Geen bewijs vereist.) b.) Hoeveel vergelijkingen van sleutels zijn er in het beste geval nodig om een nieuwe sleutel aan een 2-3-boom met n sleutels toe te voegen ? Wat is het beste geval ? (Geen bewijs vereist.) c.) Schrijf voor elk van de drie bomen of hij een 2-3-boom is en in het geval van niet waarom niet. (1) 10 15

2

5

(2)

34 41 38

16

11

17

50

40

35 37

42

2

102

(3)

90

23

48 32

7

45

50 55

49

39

52 53

d.) Voeg de sleutel 24 toe aan de volgende 2-3-boom. Toon voldoende tussenstappen om te zien wat er gebeurt, maar voor de tussenstappen moet je niet elke keer de hele boom tekenen. 60 15 30

2

11

20 29

77 90

33 50

75

80

109

Oefening 9

In het boek is er jammer genoeg een tikfout: Er wordt geeist dat voor de sleutels in de linkerdeelboom geldt dat ze kleiner dan de eerste sleutel zijn en de sleutels in de middenste deelboom groter dan of gelijk aan de kleinste sleutel en kleiner dan de tweede sleutel zijn. De sleutels in de rechterdeelboom moeten groter dan of gelijk aan de tweede sleutel zijn. De andere voorwaarden zijn dezelfden. Als wij alleen maar sleutels willen opslaan die verschillend zijn, is er geen verschil met de definitie uit de les. Maar is de definitie in het boek ook goed als je verschillende kopie¨en van dezelfde sleutel wil opslaan? Wat zou er veranderen? Zou deze definitie problemen veroorzaken? Zouden de bewerkingen die in de les werden getoond nog mogelijk zijn? Indien niet: Waar loopt er iets fout? Anders: Zouden ze nog even effici¨ent zijn? Als je in de definitie nooit alleen maar kleiner of groter eist, maar altijd kleiner dan of gelijk aan of groter dan of gelijk aan zou je dan ook verschillende kopie¨en van dezelfde sleutel kunnen opslaan? Werken de in de les gezien bewerkingen nog?

Oefening 10

Voeg de sleutels 10,5,2,20,1,7 in deze volgorde toe aan een roodzwart-boom. Toon voldoende tussenstappen om te zien wat er gebeurt.

Oefening 11

In de les hebben wij een lemma gezien dat een benedengrens geeft voor het aantal toppen in een rood-zwart-boom als er b zwarte toppen op een pad van de wortel naar een blad zitten. • Kan je ook een benedengrens voor het aantal toppen bewijzen als er r rode toppen op een pad van de wortel naar een blad in een rood-zwart-boom zitten? • Kan je een bovengrens voor het aantal toppen bewijzen als er r rode toppen op een pad van de wortel naar een blad naar een blad in een rood-zwart-boom zitten?

Oefeningen voor de oefeningenles Oefening 12

De bedoeling van deze eerste oefening is om te zien dat de technieken die wij geleerd hebben wel intu¨ıtief zijn. Het gaat over een onderwerp dat jullie al kennen en waar jullie ook de complexiteit reeds van kennen. Door het toepassen van de nieuwe methoden op een bekend geval zien jullie hopelijk gemakkelijker wat het idee achter deze technieken is. Gegeven zijn twee enkelvoudige gelinkte gesorteerde lijsten met elk n objecten. Dus: je kent de twee eerste objecten en elk object bevat een referentie naar zijn opvolger. De tweede lijst moet gemerged worden in de eerste lijst zodat er op het einde een enkele gesorteerde lijst is. Dat gebeurt door een plaats-operatie: eerst word de plaats in de eerste lijst gezocht, waar het eerste element van de tweede lijst geplaatst moet worden en dan wordt het daar geplaatst. Als je de plaats voor het i-de element hebt gevonden, vertrek je van daar en zoek je de plaats voor het (i + 1)-de element. • Toon aan dat het plaatsen van ´e´en element in het slechtste geval O(n) stappen kan vragen (wat tot een complexiteit van O(n2) aanleiding zou geven). • Is er een vast getal k zodat er als je twee lijsten mergt ten hoogste k plaats-operaties kunnen zijn die tijd Θ(n) vragen? indien ja: bepaal k anders: toon aan dat k niet bestaat • Toon d.m.v. de aggregaatmethode aan dat de geamortiseerde complexiteit van alle n invoegbewerkingen gemiddeld O(1) per bewerking is. • Toon d.m.v. de potentiaalmethode aan dat de geamortiseerde complexiteit van alle n invoegbewerkingen samen O(n) is.

Oefening 13

Een bekende manier om met een array te werken is dat je elke keer dat je meer elementen wil toevoegen dan in de array passen dubbel zo veel ruimte voor de array alloceert en de oude array kopi¨eert. Stel nu, dat je zo weinig mogelijk geheugen wil gebruiken en dus niet altijd zoveel extra geheugen wil alloceren. Je begint met 1000 elementen en hebt de mogelijkheid ofwel elke keer en array met 500 elementen meer te alloceren ofwel elke keer een array met 20% meer ruimte dan de vorige. Wat is beter? Bereken de geamortiseerde tijd voor een reeks van m bewerkingen op een initi¨eel lege array. Je kan zelf kiezen welke methode je wil toepassen.

Oefening 14

Als je in een zoekboom een sleutel zoekt, moet je kijken of de sleutel in een top gelijk, kleiner of groter is aan de sleutel die je zoekt. Daarvoor heb je 2 vergelijkingen nodig (natuurlijk niet noodzakelijk 2 vergelijkingen van de sleutels...). Wij kijken nu alleen naar het toevoegen en zoeken. Stel nu dat je per top maar ´e´en vergelijking wil doen en elke sleutel maar ´e´en keer in de boom mag zitten. Dan kan je alle sleutels in bladeren plaatsen en de toppen met twee kinderen helpen je gewoon het juiste blad te vinden. Sleutels die gelijk zijn aan de waarde van een binnentop plaatsen wij altijd in zijn grotertak. Je voegt een top op dezelfde manier toe als gewoonlijk. Maar als je het als een kind van een blad hebt toegevoegd (en dus de ouder achteraf geen blad meer is) cre¨eer je als de nieuwe sleutel kleiner is dan de ouder twee kinderen van de ouder en plaats je een kopie van de ouder in het groterkind en de nieuwe sleutel in het kleinerkind. Als de nieuwe sleutel groter is, cre¨eer je ´e´en nieuw kind van de ouder waar je de nieuwe sleutel plaatst en dan nog twee kinderen van deze nieuwe top, waar je ´e´en keer een kopie van de sleutel in de ouder en ´e´en keer een kopie van de nieuwe sleutel plaatst (natuurlijk in de juiste volgorde). Op deze manier kan je een sleutel in een blad altijd vinden door in het grotertak te zoeken als hij gelijk is aan de sleutel in een binnentop. • Toon aan dat als n het aantal sleutels in de bladeren is dezelfde sleutel O(n) keer in de boom kan zitten – ook als hij maar ´e´en keer in een blad zit. • Toon aan dat het gemiddelde aantal keren dat een sleutel in de boom zit O(1) is. Gebruik ´e´en keer de aggregaat en ´e´en keer de accounting methode. • Bespaart deze nieuwe datastructuur altijd vergelijkingen ? Hier gaat het niet over het tellen van stappen maar elementen, maar toch kunnen de methoden gemakkelijk toegepast worden.

Inderdaad kan je het tweede deel van de oefening op een andere manier gemakkelijker oplossen, maar de bedoeling is vooral de methoden uit de les te oefenen – en dat natuurlijk niet op voorbeelden die te moeilijk zijn...

Oefeningen voor de oefeningenles

Oefening 13 werd de vorige keer niet opgelost. Zij moet eerst opgelost worden. Oefening 15

Bouw een leftist heap L1 door de elementen 19, 13, 8, 11, 1, 6, 7 (in deze volgorde) toe te voegen aan een initieel lege heap. Bouw vervolgens een tweede leftist heap L2 door de elementen 5, 22, 8, 4, 14, 17, 16, 9, 11, 18, 12 (in deze volgorde) toe te voegen aan een initieel lege heap. Merge vervolgens L1 en L2 en verwijder tenslotte de wortel.

Oefening 16

• In de les hebben wij gezien dat een reeks van n toevoegbewerkingen op een initieel lege binomiale heap geamortiseerd tijd O(n) vraagt. Geldt dat ook voor leftist heaps? Indien niet: Geef een goede bovengrens voor het aantal stappen (b.v. O(n log n) of O(n2)). • Omdat de stappen verschillend zijn voor leftist heaps en binomiale heaps tellen wij nu gewoon het aantal vergelijkingen van sleutels. Kan je dan voor elk n een reeks r1 van n sleutels aangeven zo dat als die in deze volgorde aan een initieel lege heap worden toegevoegd een leftist heap minder vergelijkingen vraagt dan een binomiale heap en een dergelijke reeks r2 van sleutels waarvoor een binomiale heap minder vergelijkingen vraagt?

Oefening 17

Bouw een skew heap L1 door de elementen 19, 13, 8, 11, 1, 6, 7 (in deze volgorde) toe te voegen aan een initieel lege heap. Bouw vervolgens een tweede skew heap L2 door de elementen 5, 22, 8, 4, 14, 17, 16, 9, 11, 18, 12 (in deze volgorde) toe te voegen aan een initieel lege heap. Merge vervolgens L1 en L2 en verwijder tenslotte de wortel. Het zijn dezelfde sleutels die je voor de leftist heap hebt gebruikt.

Oefening 18

Bestaat er voor elke leftist heap H een reeks van alleen toevoegbewerkingen die toegepast op een initieel lege heap als resultaat H opleveren? Hier gaat het alleen maar om de structuur van H. Exacter zou zijn: . . . die als resultaat een heap opleveren die isomorf is met H.

Oefeningen voor de oefeningenles Oefening 19

In de volgende figuur zijn de kosten van de bogen die met punten zijn getekend altijd 5. De kosten van de dikke lijnen zijn 1 als er niet expliciet iets anders staat.

a

w 2

3 c 2 b

v d

e

g 3 2

f

De vraag is of er een rondreis met kost ten hoogste 12 bestaat. Bepaal de oplossingenboom. Start ´e´en keer met v en ´e´en keer met w. Welke bounding criteria pas je toe?

Oefening 20

Kleuren van grafen Een consistente kleuring van de toppen van een graaf is een toekenning van een kleur aan elke top zodanig dat twee toppen die door een boog verbonden zijn, een verschillende kleur hebben. Geef een backtracking algoritme dat voor een graaf met toppen 1, . . . , n controleert of een gegeven graaf met twee kleuren kan gekleurd worden. Let op de volgorde waarop je de toppen kleurt. Wat is de complexiteit in het slechtste geval als je de toppen in volgorde 1, . . . , n kleurt en wat is de complexiteit voor de volgorde die jij hebt gekozen? Doe hetzelfde nog eens voor drie kleuren.

Oefening 21

Dit is een vraag uit een examen DA2. Ik stel voor dat iedereen alleen probeert deze oefening op te lossen om een indruk te krijgen hoe goed hij deze oefening in het examen opgelost zou hebben. Als het niet zou lukken: Niet aan jezelf twijfelen – het was wel ´e´en van de moeilijkere oefeningen – er gaan ook gemakkelijke oefeningen – zelfs drilloefeneingen – zijn. Een probleem vertalen: Een vertegenwoordiger moet n steden bezoeken en zoekt de snelste manier om dat te doen en terug te komen. Voor elk paar a, b van steden is de tijd bekend die nodig is om van a naar b te rijden zonder door ´e´en van de andere steden te gaan. Als het belangrijk is dat hij elke stad precies ´e´en keer bezoekt (bijvoorbeeld als hij echt slechte produkten verkoopt. . . ) dan is dit probleem equivalent met het handelsreizigersprobleem. Maar normaal is dat voor hem niet belangrijk — hij zoekt gewoon de kortste rondreis waarin elke stad tenminste ´e´en keer wordt bezocht. Vertaal dit probleem naar het normale TSP. Schets een polynomiaal algoritme dat als resultaat een input voor het normale TSP heeft, zodat als wij de lengte van een kortste Hamiltoniaanse cykel in dit TSP kennen, wij ook de lengte van een kortste rondreis voor de vertegenwoordiger kennen. Toon aan dat jouw algoritme aan de eisen voldoet.

Oefening 22

In het schaakspel kan een paard (of knight) op rij r en kolom k bewegen naar rij 1 ≤ r0 ≤ b en kolom 1 ≤ k 0 ≤ b (met b × b de grootte van het schaakbord), op voorwaarde dat ofwel |r − r0| = 2 en |k − k 0| = 1 ofwel |r − r0| = 1 en |k − k 0| = 2 . Een knight’s tour is een sequentie van zetten die elke plaats op het schaakbord precies eenmaal aandoet vooraleer terug te keren naar het startpunt. De volgende figuur geeft een knight’s tour voor een 8×8 schaakbord.

Een knight’s tour op een 8 × 8 schaakbord 1. Geef een backtracking algoritme dat een knight’s tour bepaalt. 2. Werk een deel van de oplossingenboom voor een 4 × 4 schaakbord voor jouw algorime uit. Kies een deel dat voldoende groot is om te tonen hoe jouw algoritme werkt.

3. Bewijs dat een knight’s tour voor een 4 × 4 schaakbord niet bestaat. Helpt dit bewijs het probleem beter te verstaan en een beter algoritme te ontwikkelen? Misschien een volgorde waarop je de volgende zet kiest of een bounding criterium ? Zijn er toppen in jouw uitgewerkte deelboom waar je zou hebben kunnen snoeien? 4. Vertaal dit probleem naar een TSP probleem. Dus: Voor een gegeven getal b definieer eerst een complete graaf G en gewichten op de bogen van G. Bepaal dan een getal x zodat voor G een rondreis bestaat met kost ten hoogste x als en slechts als er een knights tour voor een b × b schaakbord bestaat. Het berekenen van G en x moet een computer in tijd O(b4) kunnen doen. 5. Bewijs dat, als b oneven is, een knight’s tour voor een b × b schaakbord niet bestaat. 6. Bepaal een knight’s tour voor een 6 × 6 schaakbord.

Oefeningen voor de oefeningenles Oefening 23

In de les hebben wij gezien hoe je het TSP kan vertalen naar een lineair probleem en hoe je verschillende eisen in een vorm Ax ≤ b kan formuleren waarbij A een matrix is, x de vector van bogen en b een getal. Natuurlijk mag – behalve in het geval van maar 3 steden – een oplossing nooit driehoeken bevatten. Formuleer deze eis door een reeks van eisen in de vorm Ax ≤ b.

Oefening 24

Vertaal het volgende probleem naar een gekend probleem. Geef enkel aan hoe het probleem kan vertaald worden; het is niet nodig ook het algoritme uit te werken. Veronderstel dat n taken Tj (j = 1, . . . , n) moeten uitgevoerd worden op een machine, waarop slechts ´e´en taak tegelijk kan uitgevoerd worden. Veronderstel dat de taken in willekeurige volgorde kunnen uitgevoerd worden. De machine moet in een bepaalde toestand Sj gebracht worden om taak j te kunnen uitvoeren, ze is in toestand S0 bij het begin van de reeks taken, en ze moet terug in toestand S0 gebracht worden bij het einde van de reeks taken; een dergelijke toestand kan bijvoorbeeld beschreven worden door temperatuur, druk, of omwentelingen per minuut. Gegeven is de tijd wij , die nodig is om de machine om te schakelen van toestand Si naar toestand Sj , voor elke i en j; we veronderstellen dat wij = wji. Voor elke taak Tj is ook de tijd cj gegeven die nodig is om de taak uit te voeren wanneer de machine zich reeds in toestand Sj bevindt. Het is de bedoeling een volgorde voor de taken te bepalen zodanig dat de reeks in zo weinig mogelijk tijd kan afgewerkt worden.

Oefening 25

Werk de spelboom uit voor de volgende beginsituatie van drie-opeen-rij.

X

X O

O

X

O

Maar: De regels zijn een klein beetje gewijzigd: Je kan niet alleen maar winnen en verliezen maar de winst/het verlies is het aantal stenen die na de laatste zet op het bord aanwezig zijn. Dus hoe later je wint hoe meer je wint. Wat is de waarde van dit spel?

Oefeningen voor de oefeningenles Oefening 26

Een knikkerspelletje Beschouw het volgende spelletje : Twee spelers zitten aan een tafel met daarop 6 knikkers. Elke speler neemt om beurt ´e´en, twee of drie knikkers weg. De speler die de laatste knikker wegneemt, verliest het spel. 1. Teken de volledige spelboom voor dit spel. 2. Onderstel dat de boom systematisch afgelopen wordt met de minimax strategie, waarbij toppen met de configuraties met het kleinste aantal knikkers eerst doorzocht worden. Probeer het eindresultaat te bekomen door zo weinig mogelijk takken uit te werken (d.i. snoeien). Welke toppen worden dan weggesnoeid? 3. Wie wint het spel als beide spelers optimaal spelen?

Oefening 27

α-β-snoeien Oefening 10.2 in het boek: Gegeven is een hypothetische spelboom, waarbij in elk blad de waarde van de evaluatiefunctie voor die situatie ingevuld is. Bepaal de waarde van de wortel van de boom, en probeer daarbij zoveel mogelijk te snoeien, m.a.w. probeer zo weinig mogelijk interne toppen ook effectief te evalueren. Merk op: van bepaalde bladeren is de waarde irrelevant!

max

max

min

min

max

max

min 5 max

11 4

1

2

3

4

10

11

12

4 2

5

2 10 9

4

6

12 min max

3

5

10

2

12

8

8

7

6

2

4

5

7

5

6

1

4

3

Oefening 28

Nog een oefening uit een examen. Als jullie het ook deze keer zelfstandig oplossen en kijken hoeveel tijd jullie ervoor nodig hebben, kunnen jullie dat al veel beter inschatten als er echt examen is. Een wisselgeldspel Gegeven een bedrag b van eurocent en een getal m dat het maximale aantal zetten bepaalt. De regels zijn als volgt: In het begin ligt 0 cent op tafel. Speler X begint. Als een speler aan de beurt is en er ligt al een bedrag van t < b cent op tafel, moet hij er precies ´e´en munt bijleggen zodanig dat nog steeds ten hoogste een bedrag van b op tafel ligt (1 euro telt natuurlijk als 100 cent, etc). Het spel is gedaan als er b cent op tafel ligt. Als er op dit moment ten hoogste m munten liggen, mag speler X het bedrag houden, anders speler Y. De winst is natuurlijk, wat de andere speler op tafel legde. Stel nu dat alleen maar munten van 1, 2 en 10 cent toegelaten zijn (anders wordt de vertakking gewoon te groot om het op papier te doen). Wat is de waarde van het spel met b = 15 en m = 5. //Misschien kan je hier ook branch and bound en dynamisch programmeren toepassen //om niet de hele spelboom te moeten uitwerken. . .

Oefeningen voor de oefeningenles Oefening 29

Gebruik de Miller-Rabin test om te testen of 70 een priemgetal is. Werk in 3 groepen – ´e´en groep neemt als basis 11, ´e´en groep 12 en ´e´en groep 13.

Oefening 30

De volgende oefening lijkt sterk op het voorbeeld in de les, maar er zijn ook sommige belangrijke verschillen die een een beetje verschillende argumentatie vragen: Gegeven een verzameling V en V1, . . . , Vk ⊆ V zodat voor 1 ≤ i ≤ k geldt |Vi| ≥ r ≥ 3 en k ≤ 3r−1/2r+1. Gezocht is een kleuring met 3 kleuren zodat in elke verzameling elementen met alle drie kleuren aanwezig zijn. Let op: Dat is iets anders dan niet alleen maar ´e´en kleur aanwezig is. Beschrijf een Las Vegas algoritme dat in lineaire tijd met kans tenminste 1/2 zo’n kleuring vindt en toon aan dat jouw algoritme aan de eisen voldoet.

Oefening 31

De binomiaalco¨effici¨enten C(n, k) worden recursief als volgt gedefinieerd, voor n = 0, 1, 2, . . .: C(n, 0) = 1 , C(n, n) = 1 , C(n, k) = C(n − 1, k) + C(n − 1, k − 1) , voor 0 < k < n 1. Geef een recursief algoritme (in pseudocode) dat, voor een gegeven waarde van n en k, de binomiaalco¨effici¨ent C(n, k) berekent. Leg uit waarom dit recursieve algoritme ineffici¨ent is. 2. Geef een algoritme met dynamisch programmeren (in pseudocode) dat, voor een gegeven waarde van n en k, de binomiaalco¨effici¨ent C(n, k) berekent. Bespreek de tijds- en geheugencomplexiteit van dit algoritme met dynamisch programmeren.

Oefeningen voor de oefeningenles Oefening 32

Een gretig algoritme voor het (gewone) TSP kan bijvoorbeeld zo werken: Begin met de goedkoopste boog en maak het pad altijd langer maar kies altijd de goedkoopste boog, die het pad verlengt. Toon aan dat dit algoritme arbitrair slechte resultaten kan opleveren. Precies: Toon aan dat er voor elk getal k TSP’s zijn (dus gewogen complete grafen waarvoor een goedkoopste hamiltoniaanse cykel wordt gezocht), zodat dit algoritme Hamiltoniaanse cykels berekent die tenminste k keer duurder zijn, dan de goedkoopste.

Oefening 33

Dit is een oefening uit een examen – dus probeer het best ze zelfstandig op te lossen om te zien hoeveel tijd je nodig hebt. • Geef een voorbeeld waar first-fit dalend beter presteert dan best-fit dalend. • Geef een voorbeeld waar best-fit dalend beter presteert dan first-fit dalend. • Geef een oneindige reeks van voorbeelden (dus een reeks die afhankelijk is van bijvoorbeeld k) waar best-fit dalend en firstfit dalend allebei niet het optimum vinden.

Oefening 34

Vertaal het volgende probleem naar een gekend probleem. Geef enkel aan hoe het probleem kan vertaald worden; het is niet nodig ook het algoritme uit te werken. In een schrijnwerkerij moet een reeks planken van gegeven lengten x1, . . . , xn gezaagd worden uit stukken hout van een zekere vaste lengte x (in mm). Dit moet gebeuren met zo weinig mogelijk verspilling van hout en je kan stellen dat elke snede 2 mm breed is.

Oefening 35

Beschrijf een branch and bound algoritme dat voor een gegeven reeks van gewichten de optimale oplossing van het inpakprobleem vindt. Wat is de complexiteit?