Maart 2017
Veel is te vinden in het dictaat. Ik werk niet alles uit.


1.a) De PQ is een verzameling elementen, die elk een prioriteit hebben, afgezien van eventuele andere data.

Standaard operaties zijn Init, IsLeeg, VoegToe, GeefMax, deleteMax.
Minder standaard zijn Merge (is inefficient voor de meeste PQ implementaties) en IncreaseKey (nodig voor Dijkstra, maar dan moeten we het element aan kunnen wijzen).

NB. De elementen worden alleen gevonden op basis van hun prioriteit. Er hoeft geen explicite ordening opgeslagen te worden, en daarom is de structuur niet echt 'lineair': er is geen voor- of achterkant, en pop en push zijn ongebruikelijke namen voor de instructies. 

b) Binaire bomen, met beperking op de plaatsing van de sleutels en de structuur van de boom. 
De *ordening* van de waarde in de knopen is als bij een heap: de knoop-waarde is altijd groter dan die van de kinderen.
De *structuur* van de boom wordt beperkt door de kortste afstand tot een "extern" blad in elke knoop. (Dat heet de nul-pad-lengte in het college.) Deze is steeds voor het rechter kind kleiner of gelijk aan die voor het linker kind van een knoop.

We verwijderen altijd het maximale element, dat is de wortel. Rits daarna de twee deelbomen van de wortel weer aan elkaar.
Bij toevoegen nemen we een boom bestaande uit een knoop (het nieuwe element) en ritsen deze aan de bestaande boom.


2. a) (i) Voordeel. Er kan een boomwandeling gemaakt worden zonder recursie of externe datastructuur (stapel). 
Nadeel. Bij dynamisch gebruik van de boom (toevoegen en verwijderen) moeten ook de draden steeds op de juiste manier aangepast worden.

(ii) 8->4, 4->2, 9->5, 5->1, 12->3, 13->11, 11->nil

NB. "makkelijker" boomwandelen is geen goed antwoord, het verklaart niets.
"meer ruimte nodig voor de draden" is gedeeltelijk OK, maar de draden staan op de plek van de takken, dus slechts een bit per knoop.

b) Als er een draad van x naar y loopt, is x de laatste knoop uit de linker subboom van y. Dus we vinden x vanuit y door eerst links te gaan en dan zo vaak rechts als mogelijk. Geef een "algemeen" schetsje van de situatie.
Dat dit niet werkt bij een tak kun je laten met een voorbeeld uit de getekende boom. (Maar je kunt ook beargumenteren dat het *nooit* werkt, zo kun je -heel inefficient- draden van takken onderscheiden als er geen bits zijn.)


3. a) (i) Verwijderen gebeurt altijd in een blad. Daarvoor eerst verwisselen met de voorganger of opvolger van de knoop. 
(ii) Eerst 11 verwijderen (en concluderen dat de boom nog AVL is). Daarna 15 verwijderen en roteren. Waar?

NB. Net zolang op goed geluk roteren totdat de boom weer goed is, is geen oplossing.  Dat lukt ook slecht in een programma.

b) (i) De oplossing wordt gesuggereerd in het plaatje. Bij een AVL boom van hoogte h heeft een van de kinderen hoogte h-1 en het andere kind ook hoogte h-1 of, in het slechtste geval hoogte h-2. Idem daaronder. Dat betekent dat als de wortel hoogte h heeft, de twee knopen daaronder hoogte tenminste h-2, de vier knopen daaronder tenminste hoogte h-4. In stapjes van 2 nemen de hoogtes af, maar tenminste h/2 nivo's zijn helemaal gevuld.

NB. Aangeven dat het klopt in de getekende boom (h=5) is geen bewijs.

(ii) Als de boom n gevulde nivo's heeft, zijn er dus tenminste 2^0 + 2^1 + ... 2^{h-1} knopen in de boom, dus totaal 2^h-1 knopen.

NB. De opgave suggereert door "nu we dit weten" gebruik te maken van deel (i). Als je de recursie van "minimale" AVL-bomen uitlegt is het ook goed.


4. a) Initialiseer pad[i,j] als true wanneer er een pijl/lijn van i naar j is (en anders false).
Dan binnen de drie loops:
                 if ( pad[i,k] and pad[k,j] ) then pad[i,j] = true fi 
                 // de waarde kan al true zijn, maar dat maakt niet uit.

NB. "transitieve afsluiting" wordt in de opgave uitgelegd, mocht je het vergeten zijn. Testen of pad true is door gebruikt te maken van de dist wordt niet op prijs gesteld. Lees "Werk direct met Booleans en logische operaties"

b) Twee mogelijkheden. (A) Houdt een waarde via[i,j] bij. Dat is de hoogste k waarbij het matrix element verandert. Zo kun je recursief het pad bepalen. Beschrijf hoe.
(B) Houdt een waarde volg[i,j] bij, die de eerste knoop is op het pad van i naar j. Wordt aangepast als er een beter pad gevonden wordt. Geef aan hoe.

Methode (A). (3 --> 1) Pad van 3 naar 1 moet via k=4, want dat is het laatste moment dat a^k op dat element veranderd werd. 
Recursie:
(3 --> 4) Via 2.
    (3 --> 2) Nooit gewijzigd: is een tak. (2 --> 4) Idem.
(4 --> 1) Idem.

Dus 3 -> 2 -> 4 -> 1.

NB. Kortste pad is niet hetzelfde als de lengte van dat pad. Die staat al in de laatste matrix.
NB. Alle paden opslaan in een matrix lijkt me te veel werk. Denk aan grafen met honderdduizenden knopen. 


5. a) Lineair zoeken (in een ongeordende lijst) is slecht.
(i) Bij een hash-tabel met veel clustering gebeurt dat (bv. bij te veel sleutels, of veel synoniemen.) Ook bij een BZB met een lineaire structuur, zig-zaggend bijvoorbeeld.
(ii) Een gegarandeerd gebalanceerde boom. AVL, B-boom. Of rood-zwart. 
NB. Splay trees zijn vaak ook beter, maar niet gegarandeerd.
(iii) Een goede hash-tabel vindt de sleutel in een constant aantal stappen, onafhankelijk van het aantal sleutels (de tabel groeit mee). Bij een BZB is dat altijd logaritmisch.

b) Bij het verwijderen van een sleutel, kan die sleutel ook andere sleutels onvindbaar maken, ook sleutels die geen synoniem zijn. Zoekpaden liggen door elkaar dat is niet handig op te lossen. Lazy deletion is de oplossing. Markeer de sleutel als verwijerd. Bij laatsen telst dat als 'vrij', bij zoeken als 'bezet'.


6. a) Van klein naar groot.
b) Op een moment zijn er twee boompjes met gewicht 11. Sleutel b, en de combinatiea+c+d+e. Het agoritme voegt naar keuze een van deze samen met sleutel f.

Bij een van de oplossingen liggen sleutels b,e,f op hetzelfde nivo. We kunnen deze wisselen en krijgen een boom die even goed is, maar met een combiatie die niet gevonden zou worden.
NB. Slutels van verschillend nivo omwisselen geeft een slechtere boom als die sleutels niet dezelfde frequentie hebben.