Gegevensstructuren en Algoritmen

Ga naar: navigatie, zoeken

Samenvattingen

Klik hier om de samenvattingen te bekijken

Inleiding

Dit vak wordt sinds 2009-2010 gegeven door prof Dutré en prof Brown. Tot het academiejaar 2012-2013 werd dit vak aan de tweedejaars informatici gegeven. Vanaf dat academiejaar werd het een vak voor de eerstejaars en wordt het enkel gedoceerd door prof Dutré. Fysici kunnen het vak opnemen in hun derde jaar als onderdeel van de minoren informatica en sterrenkunde en informatica.

Videos

Videos met lessen van het MIT die gebruik maken van hetzelfde boek vind je hier op youtube.

Extra videos die bij het boek horen gemaakt door Sedgewick hier.

Examenvragen

2017-2018

Vragen Toledo

Samenvatting van de typische examenvragen die op toledo worden meegegeven bij elke les.
Typische Examenvragen 2018

2015-2016

Juni

  1. Partieel ingevulde transitietabel voor eindige toestandsmachine bij Knuth-Morris-Pratt algoritme. Vul aan en geef in de laatste rij ook de string die bij de transitietabel hoort.
  2. Heap algoritme toepassen.
  3. Array: Longest Common Subsequence.
  4. Sorteeralgoritmen: hoe vaak worden twee elementen vergeleken voor Selection-, Insertion-, Merge- en Quicksort.
  5. Quicksort tijdscomplexiteit.
  6. Bespreek: CountingSort algoritme = Key-Indexed Sorting.
  7. Bespreek: Prim en Kruskal: Priority Queue.
  8. Strategieën om collisions in hashtabellen op te lossen (voor- en nadelen).
  9. Huffman-codering

2013-2014

Vrijdag 13 juni (9:00)

  1. Complexiteit van een aantal geneste lussen bepalen (zoals in de oefenzitting)
  2. Gegeven: De code van het GnomeSort algoritme. Bepaal de best/worst/average-case tijdscomplexiteit
  3. DFA-tabel opstellen voor een gegeven string
  4. Gegeven: Gewogen graaf.
    1. Bepaal de volgorde waarin de knopen worden toegevoegd volgens zowel Prim als Kruskal
    2. Tussen 2 gegeven knopen wordt een nieuwe boog toegevoegd, bereken het maximale gewicht waarvoor deze boog nog tot de MST behoord
  5. Gegeven: Hashtabel van bepaalde grootte met lineair probing, een aantal objecten met hun hashwaarde die aan de hashtabel worden toegevoegd en 3 situaties van de hashtabel die alle waarden bevat. Geef voor elke situatie of deze het resultaat kan zijn van het invoeren van de gegeven objecten in de hashtabel
  6. Wat is het worst case aantal vergelijking bij Mergesort voor een array van grootte 6, is dit aantal theoretisch optimaal?
  7. Een Young-tabel is een m*n matrix waarvoor geldt dat in elke rij de waarden van links naar rechts oplopen en voor elke kolom de waarden van onder naar boven oplopen. Het is duidelijk dat de kleinste waarde zich dan op positie (0,0) bevindt. posities die geen waarde bevatten krijgen het label "oneindig"
    1. Ontwerp een algoritme in (pseudo)-code dat de minimale waarde uit een youngtabel verwijderd en daarna de tabel opnieuw geldig maakt. Je algoritme moet lopen in een tijd evenredig met n+m.
    2. Ontwerp een algoritme (pseudo)-code dat een nieuwe waarde in een youngtabel invoegt, opnieuw met tijdscomplexiteit n+m
    3. Beschrijf (geen code) hoe je met behulp van een youngtabel en lijst van n² getallen kan sorteren in een tijd O(n³)

2012-2013

Donderdag 13 juni (13:00)

  1. Leg uit hoe het heapsort algoritme werkt (werkingsprincipe, tijdscomplexiteit, ...). Zou het mogelijk zijn om een variant van heapsort te implementeren die gebaseerd is op een (perfect) gebalanceerde ternaire boom (elke knoop heeft 3 vertakkingen) en waarbij de kinderen van knoop respectievelijk op posities , en in de array te vinden zijn. Bespreek voor- en nadelen van dergelijke heapsort variant.
  2. Leg de werkingsprincipes (t.t.z. verschillende essentiële operiaties) van 2-3 bomen uit. Welke voordelen bieden 2-3 bomen t.o.v. binaire bomen?
  3. Leg het algoritme van Boyer-Moore uit voor string-matching. Vergelijk Boyer-Moore met de naïeve aanpak (exhaustief alle mogelijkheden bekijken) m.b.t. complexiteit van beide algoritmen.
  4. Bespreek het gebruik van hash-tabellen. Bespreek tevens verschillende strategieën om collisions in hash-tabellen zoveel mogelijk te vermijden.

Woensdag 12 juni

  1. Leg Counting ut, pseudo, complexiteit en heel de bazaar
  2. 2-3 bomen beschrijf de elementaire operaties bijvraag link rb bomen
  3. KMP beschrijf en vergeliekt me dien exhaustieven (complexiteit)
  4. Jet e visscherssloep en je e matrix me kansen voe te gan visschen op bepaalde dagen in e meer (=Vertex) Geef e algorimte da in d dage zo veel mogelijk visch lat vangen. Ipletten tis gerichte!

2010-2011

Maandag 17 januari (13:00)

Het examen werd afgelegd bij prof. Dutré

  1. Counting sort
    1. Leg kort uit
    2. Geef (pseudo-)code
    3. Bespreek de complexiteit
    4. Voor- en nadelen
    5. Praktisch voorbeeld geven
  1. Gegeven een graaf met 9 nodes en 19 edges (met alle gewichten, etc)
    1. Geef volgorde waarin Kruskal de MST berekent
    2. Stel dat er een bepaalde (gegeven) edge wordt toegevoegd, maakt deze deel uit van de MST? Vanaf welk gewicht wel/niet?
    3. Geef volgorde waarin Prim de MST berekent
    4. Als je een edge x-y met een gewicht w toevoegt aan een graaf G met V vertices, kan de MST veranderen. Geef een algoritme dat zegt of de MST verandert of niet en uitvoert in tijd ~V.
  1. KMP
    1. Bereken de DFA van een gegeven string (aacaaab) (Waarbij ook de eerste stap was gegeven.)
    2. Bespreek de complexiteit van KMP.
  1. Dynamic, greedy of geen van beide?
    1. QuickSort
    2. Convex Hull berekening
    3. Dijkstra
    4. Insertion in een 2-3 boom
    5. Bellman-Ford
    6. Rabin Karp

2009-2010

vrijdag 10 september (13:00)

1. Counting sort
- Kort uitleggen
- pseudo code
- complexiteit
- Voor en nadelen
- Praktisch voorbeeld geven

2. Red-Black-Trees
- kort uitleggen
- 3 basisoperaties bespreken (insert, delete, search)
- Complexiteiten basisoperaties

3. Netwerk
- Vaste netwerk
Bespreek hoe deze op te bouwen en welk algoritme
- Veranderend netwerk
Welk algoritme?
Welke data wordt verstuurd?
Hoe paden up to date houden?
Complexiteit van algoritme? En waarom?

4. Dynamic, greedy of geen van beide?
- Radix Sort
- Heapsort
- Currency exchanger
- Dijkstra
- Bellman-Ford
- TSP

vrijdag 27 augustus (8:00)

1. Counting sort
- Kort uitleggen
- pseudo code
- complexiteit
- Voor en nadelen
- Praktisch voorbeeld geven

2. Binary searchtree
- kort uitleggen
- 3 basisoperaties bespreken (insert, delete, search)
- Complexiteiten basisoperaties (beste, slechtste en gemiddeld)

3. Netwerk
- Vaste topologie
Bespreek hoe deze op te bouwen en welk algoritme
- Veranderende topologie
Welk algoritme?
Welke data wordt verstuurd?
Hoe paden up to date houden?
Complexiteit van algoritme? En waarom?

4. Dynamic, greedy of geen van beide?
- Traveling salesman
- Quicksort
- longest common subsequence
- Kruskal
- Dijkstra
- Rabin karp

vrijdag 29 januari (8:00)

Enkel professor Brown was aanwezig, je moest de vragen bij hem beantwoorden.

  1. Leg Radix sort uit en leidt de complexiteit uit.
  2. Leg het Rabin-Karp string matching algoritme uit. Vergelijk ook met het naïve sting matching algoritme qua complexiteit.
  3. Gegeven: een boom bestaat uit 2/3 en 4-knopen, waarbij dus een 2-knoop idem is als bij een binaire boom, een 3-knoop bevat 2 cijfers, en 3 kinderen (links = kleiner, midden= tussen beide, rechts= groter) en een 4-knoop heeft 3 cijfers en 4 kinderen.
    1. Bewijs dat je van zo een boom een rood-zwartboom kan maken.
    2. *gegeven een algoritme om een knoop toe te voegen* bewijs dat de boom nog steeds gebalanceerd is.
    3. Voor de 3 gevallen (knoop toevoegen aan een 2/3-knoop, knoop toevoegen aan een 4-knoop met ouder een 2/3-knoop en knoop toevoegen aan een 4-knoop met ouder een 4-knoop): geef een voorbeeld en leg het verband met een rood-zwartboom uit.
  4. Convexe veelhoek:
    1. Construeer een algoritme dat een convexe veelhoek on O(n log n) construeert uit een gegeven verzameling punten P.
    2. Leg uit hoe je (jouw) algoritme zou kunnen gebruiken voor het sorteren van een rij getallen. (hint: je mag ze voorstellen volgens hun x-coördinaten).
    3. Geef enkele eigenschappen.

maandag 25 januari (13:00)

  1. Leg Radix sort uit en leidt de complexiteit af.
  2. Hashing: Leg uit. Wat zijn collisions? (Mondeling: geef mij een goede hashfunctie)
  3. DHL - leveringsroutes : Geef een sorteer algoritme + datastructuur. Geef de complexiteitsanalyse.
    1. Verschillende situaties en settings over hoe een levering te maken
    2. 1 koerier - onbeperkt aantal koeriers
    3. zo weinig mogelijk afstand berijden
    4. zo efficiënt mogelijk
    5. etc.
  4. Convexe figuren: Hoe construeren van de lijnen tussen de punten? De inwendige hoeken groter dan 180° verwijderen? Dit constructie mechanisme kan men ook gebruiken als sorteeralgoritme.

dinsdag 12 januari (8:00)

  1. Leg Bucket-sort uit en leidt de complexiteit af.
  2. Red-Black Trees:
    1. Wat zijn rotaties?
    2. Toon het inserten van nodes aan op boom (figuur komt) door waarden 3 tot en met 6 toe te voegen.
  3. Minimal-Spanning-Tree uit boom-met-lus en paal-graaf. Figuren komen nog
    1. Geef de tijd van Kruskal of Prim om een MST te berekenen.
    2. Geef een efficiënt algoritme om een MST te vinden in een boom-met-lus en toon de correctheid aan.
    3. Geef een efficiënt algoritme om een MST te vinden in een paal-graaf en toon de correctheid aan.
  4. Een deelnemer aan de Elfstedentocht zou graag weten bij welke bevoorradingspunten hij zijn fles warme drank moet aanvullen. Hij heeft een kaart met de verschillende bevoorradingspunten op. Stel dat hij M km kan afleggen met een volle fles (1l). Wat is het minimaal aantal stops dat hij zal moeten maken. Toon aan dat dit een optimale oplossing is en geef de uitvoeringstijd.

vrijdag 15 januari (8:00)

Alleen professor Dutré was aanwezig en je moest ook alle vragen bij hem dan uitleggen

    1. Welk sorteeralgoritme gebruik je het best bij een rij waarbij de elementen slechts enkele plaatsen van zijn juiste positie kan bevinden? (bv. kan max 5 plaatsen van zijn juiste plaats verwijderd zijn)
    2. wat als deze maximale afstand mag variëren? Verandert je keuze van sorteeralgoritme dan?
    1. wat zijn binaire zoekbomen? (geef search, insert en delete)
    2. Leid hun complexiteit af voor best case, worst case en average case
    3. geef een voorbeeld van bestcase insert en worstcase insert voor de integers 1...7 in een (lege) binaire zoekboom.
    4. kan je dit veralgemenen? Ook voor andere objecten zoals bv strings?
    1. leg de algoritmen van Kruskall en Prim uit.
    2. geef hun complexiteit.(ook uitleggen vanwaar die complexiteit komt!)
    3. geven kruskall en prim altijd dezelfde MST? zo nee, verklaar
    1. Leg uit hoe het String matching algoritme Knuth-Morris-Pratt werkt.
    2. vergelijk met het naive algoritme m.b.v. uitvoeringstijden (uitgebreid over verschillende gevallen)

2008-2009

vrijdag 23 januari (14:00)

  1. Geef een overzicht van alle sorteeralgoritmes.
  2. Geef de definitie van een binaire zoekboom en die van rood-zwart bomen. Wat zijn de voordelen en nadelen van een rood-zwart boom t.o.v. een gewone binaire zoekboom?
  3. Leg string matching uit met behulp van een eindige automaat. Gegeven een kort patroon en tekst: pas het algoritme hier op toe.

vrijdag 23 januari (8:00)

  • Hetzelfde examen als op maandag 14 januari (8:00) van 2007-2008, maar ligt anders geformuleerd.*
  1. Leg zonder veel details het algoritme 'Quicksort' uit. Bespreek de complexiteit in het beste, gemiddelde en slechtste geval. In het slechtste geval moet je de hele recursiebetrekking opstellen en uitwerken.
  2. Leg aan de hand van de stackoperaties PUSH, POP en MULTIPOP de technieken van geamortizeerde analyse uit:
    1. geaggregeerde analyse
    2. boekhoudmethode
    3. potentiaalmethode
  3. Definieer een B-boom. Waarvoor wordt een B-boom gebruikt? Leg het invoeren en verwijderen van elementen in een B-boom uit en illustreer met kleine voorbeelden. Je moet ook 1 element verwijderen uit een gegeven B-boom.

maandag 12 januari (14:00)

  1. Binaire hoop
    • Wat is een (binaire) hoop (heap)?
    • Hoe kan men een hoop representeren met een array?
    • Leg gedetailleerd (in woorden of pseudocode) het algoritme 'Heapsort' uit om een array van sleutels te sorteren van klein naar groot.
    • Toon aan dat uw algoritme correct is.
    • Bepaal de complexiteit van dit algoritme (slechtste geval, beste geval).
    • Vergelijk de complexiteit van dit algoritme met de complexiteit van andere sorteeralgoritmes die u kent.
    • Pas het algoritme toe op de array A = [3 7 2 5 8 1 9 4].
  2. Beschrijf verschillende technieken van open adressering om botsingen op te lossen in hashtabellen. Bij open adressering worden alle elementen in de hashtabel zelf opgeslagen.) Vergelijk de technieken met elkaar wat betreft efficiëntie. U kan hierbij gebruik maken van de parameter α = n/m met m de grootte van de hashtabel en n het aantal opgeslagen elementen.
  3. Geef (zonder te veel details) een overzicht van algoritmes voor string matching. Vergelijk de algoritmes met elkaar wat betreft complexiteit.

maandag 12 januari (8:00)

  1. Beschrijf de verschillende algoritmes die u kent voor het volgende probleem: Gegeven een verzameling A met n (verschillende) getallen en een getal i, 1 ≤ i ≤ n (speciaal geval i = n). Bepaal het element x∈A dat groter is dan exact i-1 andere elementen van A. Bespreek de complexitiet van de algoritmes.
  2. Leg het Rabin-Karp algoritme uit voor het matchen van een string in een tekst. Wat is de complexiteit? In het slechtste geval? Gemiddeld? Pas dit algoritme toe op:
    1. alfabet = {a,b,c}
    2. tekst T = ?
    3. patroon P = aba
    4. priemgetal q = 5
  3. Hashtabel van lengte m = 11. Gebruik dubbel hashing met primaire functie h1(k)= k mod m en secundaire hashfunctie h2(k)=1+(kmod(m-1)) om achtereenvolgens de sleutels 4, 10, 15, 22, 5 en 49 in te voegen, vertrekkende van een lege tabel.

2007-2008

vrijdag 1 februari (14:00)

  1. Geef een overzicht van sorteeralgoritmes. Beschrijf (zonder te veel details) hoe de algoritmes werken. Vergelijk de algoritmes met elkaar wat betreft complexiteit.
  2. Beschrijf verschillende technieken van open adressering om botsingen op te lossen in hashtabellen. Bij open adressering worden alle elementen in de hashtabel zelf opgeslagen.) Vergelijk de technieken met elkaar wat betreft efficiëntie. U kan hierbij gebruik maken van de parameter α = n/m met m de grootte van de hashtabel en n het aantal opgeslagen elementen.
  3. Geef de definitie van een B-boom. Waarvoor worden B-bomen gebruikt? Leg invoegen en verwijderen van een element uit een B-boom uit. Illustreer de verschillende gevallen met kleine voorbeelden. Verwijder 12 uit de boom met t = 2. (Deze boom werd in bijlage bij het examen gevoegd.)

dinsdag 22 januari (8:00)

  1. Geef een overzicht van sorteeralgoritmes. Leg kort uit wat ze doen en vergelijk hun complexiteit.
  2. Geef de definitie van een binaire zoekboom. Geef ook de definitie van een rood-zwart boom. Geef de voordelen (en eventuele nadelen) van een rood-zwart bomen tegenover binaire zoekbomen.
  3. Je krijgt de pseudocode van het Knuth-Morris-Pratt string matching algoritme. Leg het algoritme gedetailleerd uit en geef alle tussenstappen die nodig zijn om tot de pseudocode te komen. Geef ook de complexiteit van het algoritme. Je moet ook het algoritme uitvoeren op een gegeven tekst met patroon.

woensdag 20 januari (8:00)

  1. Binaire hoop
    • Wat is een (binaire) hoop (heap)?
    • Hoe kan men een hoop representeren met een array?
    • Leg gedetailleerd (in woorden of pseudocode) het algoritme 'Heapsort' uit om een array van sleutels te sorteren van klein naar groot.
    • Toon aan dat uw algoritme correct is.
    • Bepaal de complexiteit van dit algoritme (slechtste geval, beste geval).
    • Vergelijk de complexiteit van dit algoritme met de complexiteit van andere sorteeralgoritmes die u kent.
    • Pas het algoritme toe op de array A = [3 7 2 5 8 1 9 4].
  2. Soorten van open adressing uitleggen.
  3. String matching door middel van een eindige automaat uitleggen.

vrijdag 18 januari (14:00)

  1. Binaire hoop
    • Wat is een (binaire) hoop (heap)?
    • Hoe kan men een hoop representeren met een array?
    • Leg gedetailleerd (in woorden of pseudocode) het algoritme 'Heapsort' uit om een array van sleutels te sorteren van klein naar groot.
    • Toon aan dat uw algoritme correct is.
    • Bepaal de complexiteit van dit algoritme (slechtste geval, beste geval).
    • Vergelijk de complexiteit van dit algoritme met de complexiteit van andere sorteeralgoritmes die u kent.
    • Pas het algoritme toe op de array A = [3 7 2 5 8 1 9 4].
  2. Wat is 'dynamisch programmeren'? Leg de verschillende stappen van dynamisch programmeren uit om de optimale volgorde van bewerkingen te vinden voor de vermenigvuldiging van een ketting van matrices: A_1 x A_2 x ... x A_n met compatibele dimensies. Gebruik hierbij eventueel de functie m[i,j] = minimaal aantal scalaire vermenigvuldigingen voor de berekening van A_i x A_i+1 x ... x A_j met 1 <= i <= j <=n.
  3. Geef (zonder te veel details) een overzicht van algoritmes voor string matching. Vergelijk de algoritmes met elkaar wat betreft complexiteit.

maandag 14 januari (8:00)

  1. Leg zonder veel details het algoritme 'Quicksort' uit. Bespreek de complexiteit in het beste, gemiddelde en slechtste geval. In het slechtste geval moet je de hele recursiebetrekking opstellen en uitwerken.
  2. Leg aan de hand van de stackoperaties PUSH, POP en MULTIPOP de technieken van geamortizeerde analyse uit:
    1. geaggregeerde analyse
    2. boekhoudmethode
    3. potentiaalmethode
  3. Definieer een B-boom. Waarvoor wordt een B-boom gebruikt? Leg het invoeren en verwijderen van elementen in een B-boom uit en illustreer met kleine voorbeelden. Je moet ook 1 element verwijderen uit een gegeven B-boom.

2006-2007

maandag 29 januari (8:00)

  1. Beschrijf hoe men (binaire en niet-binaire) bomen kan voorstellen.
  2. Leg aan de hand van de stackoperaties PUSH, POP en MULTIPOP de technieken van geamortizeerde analyse uit:
    1. geaggregeerde analyse
    2. boekhoudmethode
    3. potentiaal methode
  3. Leg het Rabin-Karp algoritme uit voor het matchen van een string in een tekst. Wat is de complexiteit? In het slechtste geval? Gemiddeld? Pas dit algoritme toe op:
    1. alfabet = {0,1,2,3,4,5,6,7,8,9}
    2. tekst T = 52312121221
    3. patroon P = 121
    4. priemgetal q = 11

maandag 15 januari (14:00)

  1. Geef alle sorteeralgoritmes en vergelijk ze qua complexiteit (worst case, average case, best case).
  2. Rood-zwart bomen
    1. Wat zijn rood-zwart bomen?
    2. Je kreeg de code voor INSERT en FIXUP. Leg uit.
    3. Bewijs de correctheid van deze algoritmes.
    4. Wat is de complexiteit?
    5. Bouw een rood-zwart boom op door in volgorde 10, 20, 30, 40, 50 en 60 toe te voegen.
  3. Dynamisch programmeren en demonstreren aan de hand van het voorbeeld in verband met matrixvermenigvuldiging.

maandag 15 januari (8:00)

  1. Binaire hoop
    • Wat is een (binaire) hoop (heap)?
    • Hoe kan men een hoop representeren met een array?
    • Leg gedetailleerd (in woorden of pseudocode) het algoritme 'Heapsort' uit om een array van sleutels te sorteren van klein naar groot.
    • Toon aan dat uw algoritme correct is.
    • Bepaal de complexiteit van dit algoritme (slechtste geval, beste geval).
    • Vergelijk de complexiteit van dit algoritme met de complexiteit van andere sorteeralgoritmes die u kent.
    • Pas het algoritme toe op de array A = [3 7 2 5 8 1 9 4].
  2. Hashtabel van lengte m = 11. Gebruik dubbel hashing met primaire functie h1(k)= k mod m en secundaire hashfunctie h2(k)=1+(kmod(m-1)) om achtereenvolgens de sleutels 4, 10, 15, 22, 5 en 49 in te voegen, vertrekkende van een lege tabel.
  3. Leg kort alle algoritmes uit voor string matching en vergelijk ze op gebied van complexiteit.

2005-2006

Dit academiejaar werd er nog gewerkt met een ander handboek. De vragen kunnen daarom ietwat vreemd overkomen.

Oude examenvragen via Toledo

maaandag 23 januari (8:00)

  1. De ADT heap
    1. Beschrijf de ADT heap.
    2. Beschrijf een array-implementatie van de ADT heap.
    3. Voeg een bepaald getal in in een gegeven heap.
    4. Verwijder een getal uit de dan bekomen heap.
    5. Geef de algoritmes die je voor het invoegen en verwijderen hierboven hebt gebruikt (in pseudocode).
  2. Beschrijf het 'Heapsort'-algoritme en pas dit toe op een gegeven rij. Wat is de tijdscomplexiteit van dit algoritme?
  3. Wat is hashing? Geef de verschillende manieren die je hebt gezien om botsingen op te lossen. Wat is de efficiëntie?
  4. Geef het string match algoritme dat gebruik maakt van eindige automaten. Je moet de gedachte zelf opbouwen, zonder echter de gedetailleerde bewijzen te geven van de gebruikte eigenschappen. Wat is de tijdscomplexiteit ervan? Gegeven een tekst en een patroon, gebruik het algoritme om het patroon in de tekst te herkennen.

dinsdag 24 januari (8:00)

  1. De ADT priority queue
    1. Beschrijf de priority queue.
    2. Geef een implementatie ervan.
    3. Voeg elementen 1-6 toe en verwijder dan een element.
  2. Beschrijf 'Quicksort' en implementeer het (pseudocode). Wat is de tijdscomplexiteit en pas het algoritme toe op een gegeven rij.
  3. Geef de definitie van een 2-3-4 boom, wat zijn de voordelen ervan ten opzichte van een 2-3 boom. Geef ook een aantal toevoegingen en verwijderingen (goed kiezen).
  4. Beschrijf het algoritme dat breekpunten verwijdert met zo minimaal mogelijk flippings om een permutatie in een identieke permutatie te veranderen. Wat is de efficientie van dat algoritme. Pas het algoritme toe op enkele gegeven getallen.

maandag 30 januari (8:00)

  1. De ADT queue
    1. bespreek de verschillende implementaties van een queue.
    2. Geef de efficiëntie van deze implementaties.
  2. Beschrijf 'Merge sort' & 'Selection sort'. Wat is de tijdscomplexiteit en pas het algoritme toe op een gegeven rij.
  3. Geef de definitie van een AVL boom, wat zijn de voordelen ervan ten opzichte van een binaire zoek boom? Voeg de elementen (1-8) toe in een lege AVL boom. Verwijder 4 en 7 uit de bekomen boom.
  4. Beschrijf het Knuth-Morris-Pratt matching algoritme. Je moet de gedachte zelf opbouwen, zonder echter de gedetailleerde bewijzen te geven van de gebruikte eigenschappen. Wat is de tijdscomplexiteit ervan? Gegeven een tekst en een patroon, gebruik het algoritme om het patroon in de tekst te herkennen.

woensdag 23 augustus

  1. De ADT stack
    1. Bespreek de verschillende implementaties van de stack.
    2. Geef een algoritme gebaseerd op de ADT stack dat formules in infix omzet in formules in prefix.
    3. Pas het algoritme toe op een voorbeeldje.
  2. Heapsort
    1. Geef het algoritme van 'Heapsort'
    2. Bespreek de complexiteit van dit algoritme.
    3. Pas het toe op een voorbeeldje.
  3. Hashing
    1. Leg uit.
    2. Geef de verschillende manieren om "botsingen" op te lossen en bespreek hun efficiëntie.
  4. String matching
    1. Bespreek het Rabin-Karp algoritme.
    2. Wat is de complexiteit van dit algoritme?
    3. Pas het toe op een voorbeeldje.