Algoritmen: Parate Kennis

Cursus P. Simoens, UGent. Sectieverwijzingen (§) volgen de nummering van deze cursusversie; de leerstoffiche 2025-2026 nummert het NP-hoofdstuk als 14 (hier hoofdstuk 13). Let op: ook de slides van het gastcollege zijn examenleerstof en zitten niet in dit document.

DEEL 0: TRANSVERSALE TABELLEN

Tabel 1: Gegevensstructuren

Opmerkingen bij meerdimensionale structuren (de O()-uitdrukkingen van hun woordenboekoperaties zijn geen leerstof, onderstaande feiten wel):

• Rasterstructuur: efficiëntie hangt af van celgrootte versus lijstlengte; bij sterk geclusterde data degenereert range search tot O(n). Regelmatig raster enkel geschikt voor uniform verdeelde punten (§3.2).
• Point quadtree: bij random toevoegvolgorde zijn zoeken en toevoegen gemiddeld O(lg n), slechtst O(n). Statische constructie met medianen (lexicografisch sorteren): hoogte O(lg n), bouwkost O(n lg n) (§3.3.1).
• k-d tree: dynamisch toevoegen geeft gemiddelde hoogte O(lg n), slechtst O(n) (degeneratie tot lijst). Geen rotaties mogelijk door de alternerende dimensies, dus herbalanceren = deelboom reconstrueren. Statische bouw: dimensie met grootste spreiding + mediaan als wortel (mediaan via Quickselect, gem. O(n)); met presortering O(k n lg n) (§3.4).

Tabel 2: Algoritmen

DP-voorbeelden (hoofdstuk 11):

Tabel 3: Standaardrecurrenties (herken ze op zicht)

Tabel 4: Bewijzenregister

De afleiding van de gevallen van het master theorema staat bewust niet in dit register: ze valt onder het stuk "Intuïtie in het mastertheorema" (§6.2.3) en is volgens de leerstoffiche niet te kennen.

Variantentraining per bewijs: noteer claim, techniek, kerninvariant, en waar elke aanname het bewijs binnenkomt. Wie weet waar een aanname gebruikt wordt, kan ze vervangen wanneer het examen een variant vraagt.

H2: ROOD-ZWARTE BOMEN

Definitie (§2.2), de 5 regels:

1. Elke knoop is rood of zwart.
2. Elke virtuele knoop (nullpointer) is zwart.
3. Een rode knoop heeft twee zwarte kinderen (geen twee opeenvolgende rode knopen op een weg).
4. Elke weg van een knoop naar een virtuele knoop telt evenveel zwarte knopen: de zwarte hoogte z (knoop zelf niet meegeteld, virtuele knoop wel).
5. De wortel is zwart (niet strikt nodig, wel handig).

Eigenschappen (§2.3): minstens 2^z - 1 inwendige knopen; hoogte h ≤ 2 lg(n+1), dus alle woordenboekoperaties O(lg n). Een RZ-boom simuleert een 2-3-4-boom: 3-knoop wordt 2 binaire knopen, 4-knoop wordt 3; originele verbindingen zwart, nieuwe rood.

Figuur 2.1: 2-3-4-boom en equivalente rood-zwarte boom

Rotaties (§2.4): lokale operatie rond een ouder-kindverbinding, O(1) (handvol pointers). Behouden de inorder volgorde en dus de zoekboomeigenschap; kleuren wijzigen niet. Linksrotatie rond x met rechterkind y: linkerdeelboom van y wordt rechterdeelboom van x (ordening klopt: die deelboom ligt tussen x en y).

Figuur 2.2: Rotaties

Toevoegen bottom-up (§2.5), beslisboom bij double red (kind c, ouder p, grootouder g, oom u):

• Oom u rood: recoloring van g, p en u (g wordt rood, p en u zwart), probleem schuift naar g, herhaal omhoog. Wortel altijd zwart maken.

Figuur 2.3: Rode oom: recoloring

• Oom u zwart, c-p-g niet op 1 lijn (driehoek): roteer c boven p, herleid tot lijngeval.

Figuur 2.5: Rood kind langs binnen (driehoek): eerst rotatie c boven p

• Oom u zwart, c-p-g op 1 lijn: roteer p boven g plus kleurwissel tussen p en g. Klaar.

Figuur 2.4: Rood kind langs buiten (lijn): rotatie p boven g plus kleurwissel

Nieuwe knoop wordt steeds rood toegevoegd (zwart zou regel 4 breken op alle wegen).

Verwijderen bottom-up (§2.5), de gevallen bij een dubbel zwart probleem (na het verwijderen van een zwarte knoop telt een weg een zwarte knoop te weinig; we duiden de plek aan als dubbel zwart en werken dat weg), met broer b en neven:

Figuur 2.6: Zwarte broer, zwarte neven: recoloring, probleem schuift omhoog

Figuur 2.7: Zwarte broer, rode neef langs buiten: rotatie plus kleurwissels, klaar

Figuur 2.8: Zwarte broer, rode neef langs binnen: eerst herleiden tot het buitengeval

Figuur 2.9: Rode broer: rotatie herleidt tot een geval met zwarte broer

Vereenvoudigde RZ-bomen (§2.7): een AA-boom is een RZ-boom waarbij enkel een rechterkind rood mag zijn. Minder toegelaten vormen betekent minder gevallen in de herstelcode bij toevoegen en verwijderen, ten koste van iets meer rotaties. Een binary B-tree is hetzelfde idee avant la lettre: een 2-3-boom voorgesteld als binaire boom, met dezelfde beperking maar zonder kleurterminologie.

Geaugmenteerde bomen (§2.8): extra veld per knoop voor bijkomende operaties. Voorbeeld size (aantal inwendige knopen in de deelboom, NIL = 0). Kleurwissels raken size niet, rotaties wel. Bij rechtsrotatie van x met linkerkind y (na de rotatie zelf):

• y.size = x.size (deelboom als geheel onveranderd)
• x.size = x.left.size + x.right.size + 1 Valkuil (examen 2024): gebruik de toestand NA de rotatie en vergeet het rechterkind van y niet.

INTERACTIEF: ROOD-ZWARTE BOOM VISUALISER

Volledige rood-zwarte boom volgens §2.2 t.e.m. §2.5: bottom-up toevoegen (rode oom: recoloring; zwarte oom: driehoek- en lijnrotaties) en bottom-up verwijderen (dubbel zwart: de vier broer/neef-gevallen van figuren 2.6 t.e.m. 2.9). Knopen die door de laatste operatie geherkleurd of geroteerd werden, lichten op. Oefenroutine: voorspel op papier welk geval optreedt, klik dan pas.

H3: MEERDIMENSIONALE GEGEVENSSTRUCTUREN

Queries (§3.1): point query (specifiek punt), range search (alle punten in een zoekgebied; point query is er een speciaal geval van), nearest neighbour (dichtste punt bij querypunt q, algemener: k dichtste). Triviale methode: alles overlopen, O(n), enkel zinvol bij kleine n of grote zoekgebieden.

Figuur 3.1: De nearest-neighbour en range search

Rasterstructuur (§3.2): raster van hyperrechthoeken, gelinkte lijst per cel. Range search: vind overlappende cellen, doorloop hun lijsten. Compromis celgrootte versus lijstlengte; aantal cellen best een constante fractie van n, vuistregel √n x √n. Faalt bij geclusterde data (alles in 1 cel: O(n)).

Figuur 3.2: Rastercellen die de zoekrechthoek overlappen; geclusterde data degenereert

Point quadtree (§3.3.1): meerdimensionale uitbreiding van een BST. Elke knoop bevat een punt dat zijn cel in 4 (ongelijke) rechthoeken splitst; kinderen NW, NE, SW, SE. Vorm hangt af van toevoegvolgorde. Statische, evenwichtige bouw via lexicografische sortering en medianen: O(n lg n). Verwijderen is lastig: deelboom heropbouwen.

Figuur 3.3: Point quadtree en de bijhorende opdeling van de zoekruimte

INTERACTIEF: POINT QUADTREE VISUALISER

Point quadtree volgens §3.3.1 in een begrensd zoekgebied van 100 x 100. Links de zoekruimte: elk punt splitst zijn cel in vier ongelijke rechthoekige kwadranten (NW, NE, SW, SE). Rechts de bijhorende boom met vier kindposities per knoop. Klik in de ruimte om een punt toe te voegen en zie beide weergaven samen evolueren; de vorm hangt af van de toevoegvolgorde. Verwijderen ontbreekt bewust: dat vereist heropbouw van de deelboom (§3.3.1).

PR quadtree (§3.3.2): splitst cellen steeds in 4 gelijke kwadranten (splitspunt hoeft niet opgeslagen, kan berekend worden op de zoekweg), tot elke cel max 1 punt bevat. Punten enkel in bladknopen. Vorm onafhankelijk van toevoegvolgorde, wel van de puntenverdeling. Vereist begrensd gegevensgebied.

Figuur 3.4: Point-region quadtree en de bijhorende opdeling

INTERACTIEF: PR QUADTREE VISUALISER

Point Region quadtree volgens §3.3.2, in hetzelfde begrensde zoekgebied van 100 x 100. Het contrast met de point quadtree hierboven: cellen splitsen steeds in vier gelijke kwadranten rond het celmidden (dat hoeft dus niet opgeslagen te worden), punten zitten uitsluitend in bladeren (max. 1 per blad), en de vorm hangt enkel af van de puntenverdeling, niet van de toevoegvolgorde. Twee dicht bijeen gelegen punten dwingen herhaald splitsen tot ze in verschillende kwadranten vallen. Test de volgorde-onafhankelijkheid met de husselknop.

k-d tree (§3.4): binaire boom, per knoop splitsing volgens 1 dimensie (klassiek: circulair alternerend). Toevoegen aan een blad creëert een nieuwe splitsing. Geen rotaties mogelijk, dus herbalanceren = reconstrueren; verwijderen via lazy deletion.

Figuur 3.5: Toevoegen van een knoop aan een k-d tree creëert een nieuwe splitsing

Query-recept op een k-d tree (§3.4.1, §3.4.2; examenvraag 2024):

1. Associeer elke knoop met zijn cel (resterend zoekgebied); de wortelcel is de volledige ruimte.
2. Recursieve methode op een knoop. Basisgevallen: lege knoop, of cel volledig buiten het (eventueel verkleinde) zoekgebied. Snoeitests in het basisgeval afhandelen, niet vóór de oproep: vermijd recursion at arm's length.
3. Test of het punt van de knoop binnen het zoekgebied ligt en het beste tussenresultaat verbetert; update dan best.
4. Verklein het zoekgebied bij elk beter tussenresultaat (bv. bovengrens verlagen tot het gevonden punt).
5. Bezoek de kinderen in slimme volgorde: eerst het kind aan de kant van q volgens de splitsingsdimensie. Het andere kind wordt automatisch gesnoeid door het basisgeval als zijn cel buiten het zoekgebied valt.

Figuur 3.7: De zoekrechthoek kan geheel, gedeeltelijk of niet overlappen met de cel van een knoop

Figuur 3.8: Orthogonal range search in een k-d tree: bezochte knopen en gesnoeide deelbomen

Nearest neighbour: zelfde skelet; zoekgebied is de cirkel/bol rond q met straal = afstand tot het beste punt tot nu toe; snoei elke cel die verder ligt dan die straal.

Figuur 3.9: Te doorzoeken gebieden bij nearest neighbour

INTERACTIEF: K-D TREE VISUALISER

k-d tree volgens §3.4, met circulair alternerende splitsing: knopen op even diepte splitsen verticaal op x, op oneven diepte horizontaal op y. Dit is de structuur van examenvraag 2024. Drie operaties om mee te oefenen: een point query, een orthogonal range query (§3.4.1: sleep een rechthoek in de ruimte) en nearest neighbour (§3.4.2). Bij beide queries toont de boom welke knopen bezocht werden (blauw) en hoeveel er dus gesnoeid zijn; bij NN zie je ook de krimpende zoekcirkel als gevolg van elk beter tussenresultaat. De knop "x oplopend" toont de degeneratie tot O(n) die zonder rotaties niet te herstellen valt.

H4: EFFICIËNTIE VAN ALGORITMEN (basiskennis)

Dit hoofdstuk levert de bouwstenen; de effectieve stappenplannen voor analyses staan in H5 (iteratief) en H6 (recursief).

Raamwerk (§4.1), de drie bouwstenen van elke analyse:

1. Invoermaat: de grootte n waarin je de uitvoeringstijd uitdrukt. De exacte keuze maakt meestal weinig uit (graad versus aantal termen van een veelterm); matrixproblemen zijn de uitzondering (dimensie n versus aantal elementen n² geeft andere exponenten).
2. Basisoperaties = het kostenmodel: de operaties waarin je de uitvoeringstijd telt. Typisch de operaties in de diepst geneste lus; bij sorteren en zoeken klassiek enkel de sleutelvergelijking.
3. Afhankelijkheid van de invoerwaarde: hangt het aantal basisoperaties enkel af van de grootte van de invoer, of ook van de waarde? In het tweede geval splits je de analyse uit in beste, gemiddelde en slechtste geval, en leg je uit waarom.

Asymptotische notatie (§4.2), exacte definities:

• f(n) = O(g(n)): er bestaan strikt positieve c en n0 zodat 0 ≤ f(n) ≤ c g(n) voor alle n ≥ n0. Bovengrens.
• f(n) = Ω(g(n)): er bestaan c, n0 > 0 zodat 0 ≤ c g(n) ≤ f(n) voor alle n ≥ n0. Ondergrens.
• f(n) = Θ(g(n)): er bestaan c1, c2, n0 > 0 zodat c1 g(n) ≤ f(n) ≤ c2 g(n) voor alle n ≥ n0. Strakke grens.

Figuur 4.2: Asymptotische bovengrens: f(n) = O(g(n))

Figuur 4.3: Asymptotische ondergrens: f(n) = Ω(g(n))

Figuur 4.4: Boven- en ondergrens: f(n) = Θ(g(n))

Rekenregels: O(f) + O(g) = O(max(f, g)); O(f) . O(g) = O(f . g). Veelterm van graad k is O(n^k). Elke polynomiale n^ε (ε > 0) domineert lg n (gebruikt in examen 2021 vraag 1c: n² lg n verslaat n^2.32 voor grote n).

Groeiordes, klein naar groot: 1, lg lg n, lg n, n^ε, n, n lg n, n², n³, 2ⁿ, n!.

Andere criteria (§4.3): de asymptotische benadering is niet de enige maatstaf. Verborgen constanten tellen in de praktijk (0.1n² en 2¹⁰⁰ n² zijn beide O(n²)), de benadering geldt enkel voor voldoend grote n, en daarnaast wegen ook geheugengebruik, eenvoud van implementatie en numerieke stabiliteit mee (denk aan Strassen, §8.1).

Figuur 4.5: Typische ordes van toename op lineaire en log-log schaal

H5: ANALYSE VAN ITERATIEVE ALGORITMEN

Stappenplan iteratieve analyse (cursuskader bij de start van H5; gebruik de bouwstenen uit §4.1):

1. Kies een geschikte invoermaat.
2. Identificeer de basisoperaties; typisch in de diepst geneste lus.
3. Controleer of het aantal uitvoeringen van de basisoperatie enkel afhangt van de grootte van de invoer. Zo niet: splits stappen 4 en 5 uit in slechtste, gemiddelde en beste geval.
4. Stel een sommatie op die uitdrukt hoe vaak de basisoperatie wordt uitgevoerd.
5. Werk de sommatie uit met de somformules tot een gesloten uitdrukking, of bepaal minstens de orde van toename.

Voorbeelden in §5.2: enkele lus, geneste lussen.

Somformules (§5.1): som van 1 over i=1..n is n; over i=l..r is r - l + 1; som van i over 1..n is n(n+1)/2; som van i² is van orde n³/3 (formularium). Let altijd op start- en stopwaarde.

Selection sort (§5.3): zoek telkens het minimum van de restrij en wissel het naar voren. Aantal sleutelvergelijkingen onafhankelijk van de invoer: Θ(n²) in alle gevallen. Niet stabiel (de wissel kan gelijke sleutels voorbijsteken).

Figuur 5.1: Stappen van selection sort

INTERACTIEF: SELECTION SORT VISUALISER

Selection sort volgens §5.3: zoek in de restrij het minimum (oranje), wissel het naar de eerste vrije positie, en breid zo het gesorteerde prefix (groen) uit. Volg de teller: het aantal sleutelvergelijkingen is n(n-1)/2, exact hetzelfde voor elke invoer, ook een al gesorteerde. Vergelijk dat met insertion sort, die op gesorteerde invoer O(n) haalt. Laad een eigen lijst of genereer er een, en speel af of stap manueel.

Insertion sort (§5.3): schuif elk element naar links tot het op zijn plaats zit; prefix is steeds gesorteerd. Gesorteerde invoer: 1 vergelijking per element, O(n). Slechtst (omgekeerd gesorteerd) en gemiddeld: O(n²). Stabiel, ter plaatse.

Figuur 5.3: Enkele iteraties van insertion sort

INTERACTIEF: INSERTION SORT VISUALISER

Insertion sort volgens §5.3 en §7.1: neem het volgende element (oranje, "in de hand"), schuif alle strikt grotere elementen van het gesorteerde prefix een plaats op naar rechts, en voeg het element in op de vrijgekomen plek. Hier zie je het grote verschil met selection sort hierboven: het aantal vergelijkingen hangt WEL af van de invoer. Laad de oplopende preset en je krijgt exact n-1 vergelijkingen (het O(n) beste geval), laad de aflopende en je zit op n(n-1)/2 (het slechtste geval). Merk ook op dat het groene prefix gesorteerd is maar uit de EERSTE elementen van de invoer bestaat, niet uit de kleinste: dat is de vingerafdruk voor herkenningsvragen.

Optimalisatie (§5.4): de voorstelling van data beïnvloedt de efficiëntie sterk. Cursusvoorbeeld: een uitslagtabel rechtstreeks doorzoeken per rang kost O(n²); de tabel eenmalig inverteren naar een indextabel maakt elke opvraging O(1) en het geheel O(n).

H6: ANALYSE VAN RECURSIEVE ALGORITMEN

Stappenplan recursieve analyse (zelfde stappen 1 t.e.m. 3 als bij H5; dit is wat examen 2024 vraag 4 bedoelt met "doorloop alle stappen van een algoritmische analyse"):

1. Kies een geschikte invoermaat.
2. Identificeer de basisoperaties.
3. Controleer of het aantal uitvoeringen afhangt van de waarde van de invoer; zo ja, splits uit in beste, gemiddelde en slechtste geval en leg uit waarom.
4. Stel de recurrente betrekking op voor T(n), met basisgeval.
5. Werk de betrekking uit tot een gesloten uitdrukking (backward substitution) of bepaal de orde via de recursieboom, het master theorema of een gekende afschatting. Lees goed wat de vraag eist: een gesloten uitdrukking is sterker dan een afschatting.

Recurrentie opstellen (§6.1): tel de recursieve oproepen, hun probleemgrootte, en het niet-recursieve werk per oproep. Vergeet het basisgeval niet. Vereenvoudigingen die je mag maken (en moet vermelden): neem n een macht van b zodat floor en ceiling wegvallen.

Iteratieve methode, backward substitution (§6.2.1): vul de betrekking herhaald in zichzelf in, toon minstens twee expliciete substituties, herken het patroon T(n) = T(n/2^k) + ..., kies k zodat het basisgeval bereikt wordt (k = lg n), en werk uit tot gesloten vorm. Het examen quoteert op de tussenstappen: rechtstreeks naar het patroon springen kost punten.

Recursieboom (§6.2.2): teken de boom van recursieve oproepen (figuur 6.2), bepaal het werk per niveau en sommeer over de lg n of log_b n niveaus. Dit is het denkmodel achter het master theorema.

Figuur 6.2: Algemene vorm van de recursieboom voor T(n) = aT(n/b) + f(n)

Master theorema (§6.2.3), volledig (het theorema en zijn toepassing zijn leerstof; het stuk "Intuïtie in het mastertheorema" binnen deze sectie, met de afleiding van de gevallen, is dat niet): Voor T(n) = a T(n/b) + f(n) (n ≥ n0), T(n) = d (n < n0), met a ≥ 1, b > 1, d ≥ 0:

1. Als f(n) = O(n^c) voor een c < log_b(a), dan T(n) = Θ(n^{log_b a}).
2. Als f(n) = Θ(n^{log_b a} . lg^k n) voor een k ≥ 0, dan T(n) = Θ(n^{log_b a} . lg^k+1 n).
3. Als f(n) = Ω(n^c) voor een c > log_b(a), EN de regulariteitsvoorwaarde geldt: a f(n/b) ≤ k f(n) voor een constante k < 1 vanaf voldoend grote n, dan T(n) = Θ(f(n)).

Werkwijze op het examen (2021 en 2024 quoteren hierop): controleer eerst de vorm, bereken log_b(a) expliciet, kies en benoem het geval, toon de voorwaarde (geef een concrete ε of c), en verifieer bij geval 3 de regulariteitsvoorwaarde met een concrete k < 1 (voorbeeld 2024: a=3, b=5, f(n)=n² geeft 3(n/5)² = (3/25)n² ≤ k n² met k = 4/25).

H7: DECREASE-AND-CONQUER

Drie varianten (§7): verminderen met een constante, met een constante factor, met een variabele grootte.

Verminderen met een constante (§7.1): insertion sort als recursief geformuleerd probleem van grootte n-1 plus tussenvoegen.

Verminderen met een constante factor (§7.2): binair zoeken. Recurrentie slechtste geval: T(n) = T(floor(n/2)) + 2, T(0) = 0 (twee sleutelvergelijkingen per stap). Gesloten vorm voor n macht van 2: T(n) = 2(lg n + 1). Zie bewijzenregister #5.

Varianten op binair zoeken (§7.2), beide O(lg n):

1. Zoeken in een cyclisch gerangschikte sequentie: een stijgende rij die op een onbekende index i is "rondgedraaid" (x_i is het kleinste element). Vergelijk de randelementen x_l en x_r: is x_l < x_r dan ligt het draaipunt niet in (l, r], is x_l > x_r dan wel. Zo elimineer je telkens de helft, dus O(lg n).
2. Zoeken in een gerangschikte rij van onbekende lengte (exponential of galloping search): vergelijk y met x₁, x₂, x₄, x₈, ..., dus verdubbel het bereik tot je voorbij y bent. Na O(lg k) stappen weet je dat y tussen x_(2^j-1) en x_(2^j) ligt; binair zoeken in dat interval kost nog eens O(lg n). Totaal O(lg n). Nuttig als elementen duur te berekenen zijn en je er zo weinig mogelijk wil aanraken.

Verminderen met variabele grootte (§7.3):

• Quickselect (§7.3.1): vind het k-de kleinste element via partitionering; recursie enkel op de relevante deelrij. Best O(n) als de pivot meteen raak is, gemiddeld O(n), slechtst O(n²) (steeds slechtste pivot). Gemiddeld geval: enkel de betrekking kunnen opstellen.

Figuur 7.2: Lomuto-partitionering

INTERACTIEF: QUICKSELECT VISUALISER

Quickselect volgens §7.3.1 zoekt het k-de kleinste element (de k-de orderstatistiek) zonder volledig te sorteren. Het partitioneert rond een pivot met de methode van Lomuto (figuur 7.2): het eerste element wordt pivot, de rij wordt verdeeld in kleiner-dan-pivot links en groter-of-gelijk rechts, en de pivot komt op zijn definitieve positie s. Daarna telt enkel die positie: ligt k links van s, dan recursie naar links; ligt k rechts, dan naar rechts; valt k op s, dan is het element gevonden. Het verschil met quicksort is precies dat: maar EEN kant wordt verder behandeld. Daardoor gemiddeld O(n), slechtst O(n²). Kies k en speel af.

• Interpolerend zoeken (§7.3.2): schat de positie van de sleutel via lineaire interpolatie in plaats van het midden te nemen. Gemiddeld O(lg lg n) bij uniform verdeelde sleutels, slechtst O(n).

Figuur 7.3: Positieberekening bij interpolerend zoeken

INTERACTIEF: INTERPOLEREND ZOEKEN VISUALISER

Interpolerend zoeken volgens §7.3.2 gebruikt wel de waarde van de elementen, in tegenstelling tot binair zoeken. In de deeltabel v[l..r] wordt verondersteld dat de waarden lineair toenemen, op de lijn tussen (l, v[l]) en (r, v[r]). De testpositie m is de afgeronde x-coördinaat van het punt op die lijn met y-coördinaat s (de gezochte sleutel), dus m = l + floor((s - v[l]) / (v[r] - v[l]) * (r - l)). De onderste grafiek toont die interpolatielijn (figuur 7.3): bij een gelijkmatige verdeling springt m bijna meteen naar de juiste plaats, vandaar gemiddeld O(lg lg n). Probeer ook de scheve verdeling om het slechtste geval O(n) te zien.

Implementatie van recursie (§7.4, §7.5): recursie kost stackruimte evenredig met de recursiediepte. Staartrecursie (laatste instructie is de recursieve oproep) kan omgezet worden naar een lus: geheugen van O(diepte) naar O(1). Lineaire recursie: code bevat meerdere oproepen maar voert er per uitvoering maar 1 uit. Vermijd recursion at arm's length: test condities in het basisgeval van de oproep zelf, niet vooraf bij de aanroeper (dupliceert code en tests).

Recursief of iteratief kiezen (§7.5): beide zijn even expressief (elke recursie wordt iteratief door de call stack zelf te simuleren; elke lus wordt staartrecursie). Recursie wint op leesbaarheid en elegantie; iteratie wint op geheugen (geen stackframes) en snelheid (geen oproepkost). Vuistregel: bij enkelvoudige recursie verkies je iteratief; bij meervoudige recursie (twee of meer effectieve oproepen, zoals mergesort) heb je meestal geen keuze en blijf je recursief.

H8: DIVIDE-AND-CONQUER

Strassen (§8.1): matrixvermenigvuldiging met 7 in plaats van 8 deelproducten: T(n) = 7T(n/2) + Θ(n²) geeft Θ(n^{lg 7}) ~ Θ(n^2.81). De formules zelf worden op het examen gegeven. Nadelen: pas sneller voor zeer grote n, moeilijk paralleliseerbaar, numeriek instabiel.

Mergesort (§8.2): splits in twee helften, sorteer recursief, voeg samen (merge). T(n) = 2T(n/2) + cn geeft Θ(n lg n), alle gevallen. Merge is stabiel (bij gelijke sleutels eerst uit de linkse deeltabel), dus mergesort is stabiel, zowel top-down als bottom-up. Niet ter plaatse: hulptabel O(n), plus O(lg n) stack bij de recursieve versie. Verbeteringen: kleine deeltabellen met insertion sort; merge overslaan als de deelrijen al aansluiten.

• Top-down: recursief halveren, mergen bij het terugkeren.
• Bottom-up: iteratief, merge deelrijen van lengte 1, 2, 4, 8, ...

Figuur 8.2: Mergesort top-down

Figuur 8.4: Mergesort bottom-up

INTERACTIEF: MERGE SORT VISUALISER

Mergesort volgens §8.2, top-down. Bovenaan zie je de recursieboom: elke knoop is een deelrij [lo..hi] die in twee helften wordt gesplitst tot je bij deelrijen van 1 element komt (per definitie gesorteerd). Daarna worden de helften terug samengevoegd. De onderste weergave toont dat samenvoegen zelf: de twee gesorteerde helften worden naar een hulptabel gekopieerd (de bron), en tabel A (de bestemming) wordt van links naar rechts opnieuw gevuld door telkens het kleinste kopelement te kiezen. Twee zaken om op te merken, allebei examenstof: de hulptabel maakt mergesort niet ter plaatse (Θ(n) extra geheugen), en omdat we bij gelijke sleutels altijd eerst uit de linkerhelft kiezen is mergesort stabiel. Laad de oplopende preset en kijk naar de teller: de hoeveelheid werk blijft Θ(n lg n), ook bij al gesorteerde invoer, want de recursiestructuur hangt enkel af van n en niet van de waarden. Dat is precies het verschil met insertion sort, die op gesorteerde invoer naar O(n) zakt.

Quicksort (§8.3): kies een pivot, partitioneer (kleiner links, groter rechts, pivot op zijn definitieve plaats), sorteer beide deelrijen recursief. Best en gemiddeld O(n lg n), slechtst O(n²) wanneer de partitie steeds 1 en n-1 elementen oplevert (analyse best/slechtst: §8.3.4; de gemiddelde-gevalanalyse §8.3.5 is geen leerstof). Eerste element als pivot: slechtste geval treedt op bij (omgekeerd) gesorteerde invoer. Random pivot of median-of-three: slechtste geval blijft O(n²) maar wordt zeer onwaarschijnlijk. Conclusie van §8.3.6, het enige dat daarvan leerstof is: een random pivot belandt gemiddeld op een kwart tabellengte van het midden, dus verwacht je opdelingen rond n/4 tegenover 3n/4; de recursieboom is daardoor maar een factor ~2,5 dieper dan in het beste geval, en de kans op het echte slechtste geval wordt verwaarloosbaar klein voor grote n. Dit verklaart ook waarom quicksort in de praktijk sneller is dan mergesort: iets meer vergelijkingen, maar veel minder verplaatsingen. Niet stabiel (de partitie steekt gelijke sleutels voorbij). Sorteert ter plaatse: O(1) hulpgeheugen (examenantwoord 2024). Partitioneren kan met de methode van Lomuto (een index loopt door de rij, kleiner-dan-pivot wordt naar voren gewisseld) of van Hoare (§8.3.2: twee indices lopen naar elkaar toe en wisselen foute paren; minder wissels). Verbeteringen: median-of-three (pivot = mediaan van het eerste, middelste en laatste element, meteen ter plaatse gerangschikt), kleine deelrijen met insertion sort.

Quicksort-varianten (kort). Pivotkeuze: eerste element, willekeurig, of median-of-three (mediaan van eerste, middelste en laatste element); een betere pivot maakt het slechtste geval onwaarschijnlijker. Partitioneren: Lomuto (een loper, pivot op vaste eindplaats) of Hoare (twee lopers, minder wissels, §8.3.2). Driewegspartitionering bij veel duplicaten: elementen gelijk aan de pivot komen apart in het midden. Kleine deelrijen afwerken met insertion sort.

Figuur 8.6: Partitioneren met de methode van Hoare

INTERACTIEF: QUICKSORT VISUALISER

Quicksort volgens §8.3, met een schakelaar tussen de twee partitiemethodes uit de cursus. Lomuto (figuur 7.2): een leeswijzer j loopt door de deelrij, de grens s schuift mee, elk element kleiner dan de pivot wordt naar voren gewisseld, en op het einde wisselt de pivot naar positie s, zijn definitieve plaats. Hoare (figuur 8.6, pseudocode 8.2, spilelement links): twee lopers i en j bewegen van buiten naar binnen tot ze elkaar kruisen; elementen aan de verkeerde kant worden gewisseld, ook elementen gelijk aan de pivot (dat balanceert duplicaten), en de deelrij wordt op de index j gesplitst. Een belangrijk verschil: bij Hoare komt de pivot NIET op een vaste eindplaats, dus de twee deelrijen [lo..j] en [j+1..hi] dekken samen alle n elementen, terwijl Lomuto er telkens één (de pivot) definitief vastzet. Beide gebruiken het eerste element als pivot, sorteren ter plaatse en zijn niet stabiel. Laad de oplopende preset: met het eerste element als pivot wordt de opsplitsing bij beide methodes erg onevenwichtig, de recursieboom ontaardt tot een ketting en je krijgt het slechtste geval O(n²). Wissel daarna van methode en vergelijk het aantal vergelijkingen en wissels.

H9: TRANSFORM-AND-CONQUER

Idee: transformeer de invoer naar een representatie waarop het probleem makkelijk is.

Heapsort (§9.1): bouw een max-heap van de tabel (O(n), zie bijlage B.2), verwijder dan n keer de wortel en plaats die achteraan in het gesorteerde deel. Totaal O(n lg n), alle gevallen. Ter plaatse, O(1) extra geheugen, niet stabiel. Herkenningspunt: na de constructiefase is de tabel een heap (grootste element vooraan), na k verwijderstappen staan de k grootste elementen gesorteerd achteraan.

Figuur 9.2: Tweede fase van heapsort: wortel vervangen en laten zakken

H10: UITVOERINGSTIJD VERSUS GEHEUGENGEBRUIK

Ondergrens vergelijkingssorteren (§10.1): elk algoritme dat enkel sleutelvergelijkingen gebruikt is een binaire beslissingsboom; inwendige knopen zijn vergelijkingen, bladeren zijn de mogelijke uitkomsten (permutaties van de invoer), dus minstens n! bladeren. De ondergrens geldt in twee gevallen, beide Ω(n lg n):

1. Slechtste geval = langste weg wortel-blad = hoogte. Bewijs (inductie, ook h = 0) dat een volle binaire boom met hoogte h hoogstens 2^h bladeren heeft, dus h ≥ lg(n!), en via de afschatting van Stirling (lg(n!) ~ n lg n - 1.44n) volgt h = Ω(n lg n). Zie bewijzenregister #4 (examen 2021).
2. Gemiddelde geval = gemiddelde weglengte wortel-blad, bij gelijk waarschijnlijke permutaties. Hier gebruik je het uitwendige-weglengte-lemma (register #3): de som van alle wegen wortel-blad in een volle binaire boom met b bladeren is minstens b lg b, dus de gemiddelde weglengte is minstens lg(n!) = Ω(n lg n).

Dit heet de informatietheoretische ondergrens: k uitkomsten onderscheiden via binaire testen vereist soms ceil(lg k) vragen. De grens is tight: mergesort haalt in het slechtste geval n lg n sleutelvergelijkingen.

Figuur 10.1: Beslissingsboom van een vergelijkingssorteerder

Counting sort (§10.2): vereist gehele sleutels uit een beperkt interval van lengte k. Tel per waarde de voorgangers (cumulatieve telling) en plaats elk element direct op zijn eindpositie. Θ(n + k) tijd, O(n + k) geheugen. Stabiel implementeren is essentieel (duplicaten). Geen vergelijkingssorteerder, dus de Ω(n lg n) grens geldt niet.

Figuur 10.2: Counting sort: invoer A, frequentietabel C, uitvoer B

Bucket sort (§10.3): verdeel de sleutels over buckets volgens hun waarde, sorteer per bucket, plak aaneen. Gemiddeld Θ(n) bij uniform verdeelde sleutels, slechtst O(n²) (alles in 1 bucket). De afleiding van het gemiddelde geval is geen leerstof, de conclusie wel.

Figuur 10.3: Bucket sort met gelinkte lijsten per deelinterval

H11: DYNAMISCH PROGRAMMEREN

Toepasbaar als (§11.4): het probleem een optimale deelstructuur heeft (de optimale oplossing is uit te drukken in optimale oplossingen van deelproblemen) en deelproblemen overlappen.

Vast recept (gebruik dit bij elke creatievraag, zie examens 2021 en 2024):

1. Karakteriseer de oplossing: wat is een kandidaatoplossing, wat is haar waarde, wat optimaliseren we?
2. Definieer notatie en stel de recursieve betrekking op, met expliciete basisgevallen, en leg uit hoe je eraan komt (gevallenonderscheid op de laatste keuze).
3. Kies de gegevensstructuur voor deelresultaten (1D of 2D tabel volgens het aantal indices) en de vulvolgorde (welke cellen hangen van welke af).
4. Geef aan waar het eindresultaat staat en hoe je de oplossing zelf reconstrueert (extra tabel b met de gemaakte keuzes, terugwandelen vanaf het einde).

Memoisation versus tabulation (§11.1): memoisation is top-down (recursie plus cache, berekent enkel benodigde deelproblemen), tabulation is bottom-up (tabel volledig invullen in afhankelijkheidsvolgorde, geen recursie-overhead).

De betrekkingen per cursusvoorbeeld:

• Fibonacci (§11.2): F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1. Naief Θ(φⁿ) met φ ~ 1.618 (gulden snede), dus exponentieel; met DP O(n).
• Binomiaalcoëfficiënten (§11.3): C(n, k) = C(n-1, k-1) + C(n-1, k); randen C(n, 0) = C(n, n) = 1. Driehoek van Pascal, O(n k).

Figuur 11.3: Berekening van een binomiaalgetal: vulvolgorde van de tabel

• Muntselectie (§11.5; munten op een rij, geen twee buren kiezen, maximale waarde): F(n) = max(c_n + F(n-2), F(n-1)), F(1) = c₁, F(0) = 0. Gevallenonderscheid: laatste munt wel of niet gekozen.

Figuur 11.4: Muntselectie stap voor stap: F[i] en de gemaakte keuzes

• Langste gemeenschappelijke deelsequentie (§11.6): c[i, j] = c[i-1, j-1] + 1 als x_i = y_j; anders max(c[i-1, j], c[i, j-1]); c[i, 0] = c[0, j] = 0. Tabel (n+1) x (m+1), vul rij per rij van links naar rechts. Reconstructie via tabel b, O(n + m). Een tabel zoals op p. 150 met c[i, j]-waarden voor twee gegeven strings moet je kunnen opstellen.
• Optimale binaire zoekboom (§11.7): gekende sleutels met zoekfrequenties (ook voor afwezige sleutels: bladeren b₀..b_n); minimaliseer de verwachte zoektijd. Deelprobleem: optimale boom voor sleutels s_i..s_j; probeer elke sleutel als wortel, links en rechts optimaal. Vul de tabel per diagonaal (toenemende intervallengte). O(n³) tijd, O(n²) geheugen.

Figuur 11.5: Twee zoekbomen voor dezelfde 5 sleutels met verschillende verwachte zoektijd

• Examenpatronen: tekstcodering met woordenboek (2021): C(i) = min over codewoorden c die prefix zijn van suffix S_i van [1 + C(i + |c|)], C(n+1) = 0. Langste palindroom-deelsequentie (2024): L(i, j) = 2 + L(i+1, j-1) als x_i = x_j, anders max(L(i+1, j), L(i, j-1)); L(i, i) = 1, L(i, j) = 0 voor j < i; vul per subdiagonaal; O(n²).

H12: COMBINATORISCHE PROBLEMEN

Backtracking (§12.1): stel oplossingen voor als tuples (v₁, ..., v_k); breid kandidaat-deeloplossingen stapsgewijs uit (zoekboom); voldoet een deeloplossing niet meer aan de voorwaarden, keer terug (snoeien). Vindt gegarandeerd alle oplossingen. Schoolvoorbeelden: n-queens, TSP.

Figuur 12.1: Zoekboom voor n-queens (n = 4) met gesnoeide deeloplossingen

Snoeitechnieken (ken ze alle vijf, met de namen):

1. Variabelen ordenen: kies dynamisch de variabele met de minste resterende geldige waarden (Least Remaining Values, fail-fast); tie-breaker: de variabele die de andere het meest beperkt (Most Constraining Variable). Beïnvloedt de grootte van de boom.
2. Waarden ordenen: probeer eerst de waarde die het meeste opties open laat (Least Constraining Value). Beïnvloedt enkel de volgorde, relevant als 1 oplossing volstaat.
3. Forward checking: na elke toekenning testen of elke resterende variabele nog minstens 1 geldige waarde heeft.
4. Symmetrieën: deelbomen die equivalente oplossingen geven overslaan (TSP: alle rondritten starten evengoed in stad A).
5. Branch-and-bound: enkel bij optimalisatie; breek af zodra de deeloplossing onmogelijk nog beter kan worden dan de beste gevonden oplossing.

Inhalige (greedy) algoritmen (§12.2): bouw de oplossing op met lokaal beste keuzes die nooit herzien worden. Snel, maar enkel correct als de gretige keuze bewijsbaar veilig is (exchange argument: verwissel in een veronderstelde optimale oplossing twee elementen en toon dat ze niet slechter, dus tegenspraak of evengoed).

• Taakplanning, minimale gemiddelde eindtijd (§12.2.1): voer taken uit volgens niet-afnemende uitvoeringstijd (kortste eerst). Bewijs via exchange argument. Variant met P processoren: zelfde idee. Minimale totale eindtijd op P processoren is daarentegen NP-compleet.
• Activiteitenselectie (§12.2.2): maximaal aantal onderling compatibele activiteiten: sorteer op eindtijd, kies telkens de vroegst eindigende compatibele activiteit.

Metaheuristieken (§12.3): algemene recepten voor optimalisatieproblemen; vertrekken van volledige kandidaatoplossingen (niet van deeloplossingen) en vereisen een representatie plus een evaluatiefunctie.

• Lokaal zoeken (§12.3.1): definieer de omgeving N(s) (alle oplossingen op 1 kleine wijziging van s); ga steeds naar de beste buur (steepest hill climbing). Risico: lokale optima.
• Simulated annealing (§12.3.2): accepteer een slechtere buur met kans afhankelijk van temperatuur T (hoge T: veel exploratie; T daalt volgens een afkoelschema). Betere buren altijd accepteren. Ontsnapt aan lokale optima.

Figuur 12.3: Invloed van de temperatuursparameter op de acceptatiekans

• Genetische algoritmen (§12.3.3): populatie van kandidaatoplossingen; selectie, crossover (recombinatie), mutatie; geïnspireerd op evolutie.

Figuur 12.5: Genetisch algoritme: overgang naar een volgende generatie

H13: NP-COMPLETE PROBLEMEN

Reductie (§13.1): probleem A is in polynomiale tijd reduceerbaar naar probleem B als elke instantie van A in polynomiale tijd omgevormd kan worden naar een instantie van B, zodat de oplossing van B vertaald kan worden naar een oplossing van A. Richting onthouden: A reduceren NAAR B betekent dat B minstens zo moeilijk is als A (B oplossen lost A op).

Figuur 13.3: Een deel van de reductieboom vanuit SAT

Figuur 13.4: NP-compleetheid bewijs je via reductie van een gekend NP-compleet probleem naar jouw probleem

Klassen (§13.2, §13.3):

• P: beslissingsproblemen oplosbaar in polynomiale tijd.
• NP: beslissingsproblemen waarvan een voorgestelde oplossing verifieerbaar is in polynomiale tijd.
• NP-compleet: (1) het probleem zit in NP, en (2) elk probleem in NP is er in polynomiale tijd naar reduceerbaar. Eerste bewezen NP-compleet probleem: SAT (Cook).
• NP-hard: enkel voorwaarde (2), hoeft zelf niet in NP te zitten.

Reductierecept voor een NP-compleetheidsbewijs (verbetersleutel examen 2021, vier verplichte onderdelen):

1. Toon dat het probleem in NP zit: beschrijf de verificatie van een geclaimde oplossing en toon dat die polynomiaal is.
2. Beschrijf een reductie vanuit een gekend NP-compleet probleem A naar jouw probleem B (let op de richting: van gekend naar nieuw).
3. Toon dat het omvormen van invoer en uitvoer polynomiaal is.
4. Toon de equivalentie in beide richtingen: uit een oplossing van A volgt een oplossing van B, en elke oplossing van B vertaalt naar een geldige oplossing van A. Goede vertrekproblemen volgens de cursus: 3SAT, vertex cover, independent set, (integer) partition, clique, Hamiltonian circuit. Voorbeeld uit het examen 2021: integer partition naar knapsack via W = V = T/2 met v_i = w_i = s_i.

Redeneerpatronen waar/vals (examen 2024):

• X NP-compleet impliceert X in NP (per definitie, voorwaarde 1).
• X NP-compleet en Y in NP: Y is polynomiaal reduceerbaar naar X (per definitie, voorwaarde 2).
• Polynomiaal algoritme voor een NP-compleet probleem impliceert P = NP.
• X NP-compleet en X polynomiaal reduceerbaar naar Y (met Y in NP): dan is Y ook NP-compleet, en een polynomiaal algoritme voor Y geeft eveneens P = NP.
• P ≠ NP: onbewezen, in beide richtingen.

De dertien probleemdefinities (§13.4; op naam kunnen neerschrijven):

1. SAT: gegeven logische variabelen en clausules (of-verbindingen van atomen x_i of niet-x_i). Bestaat er een waardetoekenning die alle clausules tegelijk waar maakt?
2. 3SAT: SAT waarbij elke clausule hoogstens drie atomen bevat. Elke SAT-instantie is ernaar herleidbaar door clausules op te splitsen met nieuwe variabelen.
3. Set Cover: gegeven verzameling S en collectie deelverzamelingen C. Gevraagd het kleinste aantal deelverzamelingen uit C zodat elk element van S tot minstens een gekozen deelverzameling behoort.

Figuur 13.5: Set cover

1. Exact Cover: idem, maar elk element van S moet tot precies een gekozen deelverzameling behoren. Toepassingen: betegeling, sudoku, allocatie.

Figuur 13.6: Exact cover: elk element precies een keer gedekt

1. Set Packing: gegeven S en collectie C. Gevraagd het grootst mogelijke aantal onderling disjuncte (mutueel exclusieve) deelverzamelingen. Niet alle elementen hoeven gekozen.
2. Subset Sum: gegeven elementen met positieve gehele grootten en een geheel getal k. Bestaat er een deelverzameling met som exact k? Pseudopolynomiaal oplosbaar met DP: polynomiaal in de waarde van de getallen, maar exponentieel in hun bitlengte, dus geen echt polynomiaal algoritme.
3. Integer Partition: gegeven een zak positieve gehele getallen. Kan die gesplitst worden in twee deelverzamelingen met gelijke som? (Pseudopolynomiaal oplosbaar met DP.)

Figuur 13.8: Integer partition

1. Bin Packing: gegeven n objecten met afmetingen en bakken met capaciteiten. Sla alle objecten op in zo weinig mogelijk bakken. Heuristiek 1D: first-fit decreasing (sorteer de objecten dalend, plaats elk object in de eerste bak waar het nog past), O(n lg n), hoogstens ~22% bakken te veel.
2. Knapsack: gegeven objecten met afmeting en waarde, en een rugzak met capaciteit. Kies objecten binnen de capaciteit met maximale totale waarde. Beslissingsversie: bestaat een selectie met gewicht ≤ W en waarde ≥ V? Fractioneel: gretig optimaal; 0/1 met kleine gehele afmetingen: DP.

Figuur 13.9: Knapsack

1. Vertex Cover: gegeven een ongerichte graaf. Gevraagd de kleinste verzameling knopen die van elke verbinding minstens een eindknoop bevat. (Complement van een independent set.)
2. Graph Coloring (vertex coloring): kleur de knopen met zo weinig mogelijk kleuren zodat de eindknopen van elke verbinding verschillend gekleurd zijn. Toepassing: planning, allocatie (workloads op servers, examen 2024).
3. Independent Set: gevraagd de grootste verzameling knopen zonder onderlinge verbindingen.
4. Hamiltonian Circuit: bestaat er een circuit dat elke knoop precies eenmaal bevat? (Hamiltonpad: idem, niet gesloten. Contrast: Eulercircuit, elke verbinding eenmaal, is wel efficiënt oplosbaar.)

Figuur 13.12: Hamiltonian circuit

Plus: Travelling Salesman: gegeven steden en onderlinge afstanden, gevraagd de kortste rondrit die elke stad eenmaal bezoekt.

Omgaan met NP-complete problemen (§13.5): exacte methodes voor kleine instanties (backtracking met snoeien), pseudopolynomiale DP waar mogelijk, benaderingsalgoritmen met garantie, heuristieken en metaheuristieken, en speciale gevallen die wel in P zitten (bv. tweeledige of planaire grafen bij kleuring, 2-elementsverzamelingen bij set cover).

BIJLAGEN A EN B: BINAIRE BOOM EN HEAP

Binaire boom (bijlage A): complete binaire boom in een tabel (niveau per niveau): kinderen van index i staan op 2i en 2i+1, ouder op floor(i/2) (1-gebaseerd). Hoogte van een complete boom met n knopen: floor(lg n).

Heap (bijlage B): complete binaire boom met heapvoorwaarde (max-heap: ouder ≥ kinderen), opgeslagen in een tabel.

• Toevoegen (B.1): nieuwe knoop achteraan (index n+1), schuif ouders omlaag tot het element past (zelfde principe als insertion sort, maar langs de weg naar de wortel). O(lg n).
• Wortel vervangen (B.1): houd de wortel vrij, schuif telkens het grootste kindelement omhoog tot het nieuwe element past. O(lg n).
• Wortel verwijderen (B.1): element van de laatste knoop naar de vacante wortel, dan wortel vervangen in de verkleinde heap. O(lg n).
• Constructie (B.2): bottom-up, vanaf de laatste inwendige knoop elke knoop laten zakken. Totale kost gesommeerd over de niveaus is O(n), niet O(n lg n): de meeste knopen staan onderaan en zakken bijna niet. Zie bewijzenregister #10. Contrast: n keer toevoegen is O(n lg n).

Figuur B.1: Stijgende heap: nieuw element schuift langs de weg naar de wortel

SORTEERHERKENNING (examen 2021, vraag 2)

Gegeven een tussentijdse tabeltoestand, herken het algoritme aan zijn vingerafdruk:

Checklist bij zo'n vraag: (1) vergelijk met de invoerkolom en de gesorteerde kolom, (2) zoek gesorteerde prefixen en bepaal of het de kleinste elementen zijn (selection) of de originele eerste elementen (insertion), (3) zoek gesorteerde blokken van machten van 2 (bottom-up mergesort), (4) test de heapvoorwaarde op de eerste posities, (5) zoek een element waarvoor alles links kleiner en alles rechts groter is (quicksortpivot).