Gegevensstructuren en Algoritmen

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

Examenvragen

2008-2009

maandag 12 januari (8:00)

1. 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
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.

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

• 23 augustus 2006
• 30 augustus 2006

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.