1. (a) Wat is een verdeel-en-heers-algoritme? Leg de algemene aanpak van verdeel-en-heers-algoritmen uit. (6 punten)

(b) Gebruik de verdeel-en-heers-aanpak om een ​​algoritme te ontwerpen om het minimale element in een array van n elementen te vinden. Analyseer de tijdscomplexiteit van uw algoritme. (10 punten)

2. (a) Leg het concept van hashing en technieken voor het oplossen van botsingen uit. (6 punten)

(b) Beschouw een hashtabel van grootte m en een reeks van n elementen die moeten worden gehasht. Neem aan dat de elementen uniform verdeeld zijn over de m slots. Wat is de kans op een botsing als n =m/2? Analyseer het gemiddelde aantal vergelijkingen dat nodig is om alle elementen met succes in de hashtabel in te voegen met behulp van lineair onderzoek. (10 punten)

3. (a) Beschrijf het concept van dynamische programmering en leg uit hoe dit verschilt van de verdeel-en-heers-aanpak. (6 punten)

(b) Gebruik dynamische programmering om het staafsnijprobleem op te lossen, waarbij een staaf met lengte n in kleinere staven kan worden gesneden, en elke staaf met lengte i een prijs p[i] heeft. Het doel is om de maximale opbrengst te vinden die kan worden behaald door de hengel in kleinere stukken te snijden. Analyseer de tijd- en ruimtecomplexiteit van uw algoritme. (10 punten)

4. (a) Verklaar het concept van NP-volledigheid en de betekenis ervan in de analyse van algoritmen. (6 punten)

(b) Bewijs dat het volgende probleem NP-compleet is:Gegeven een verzameling van n items met hun respectievelijke gewichten en waarden, bepaal of er een subset van deze items bestaat waarvan het totale gewicht kleiner is dan of gelijk is aan een gegeven limiet en waarvan het totaal waarde wordt gemaximaliseerd. (10 punten)

5. (a) Verklaar het concept van een geamortiseerde analyse van algoritmen. Waarom wordt het gebruikt en wat zijn de voordelen ervan? (6 punten)

(b) Voer een geamortiseerde analyse uit van de stapelgegevensstructuur, waarbij push- en pop-bewerkingen de enige toegestane bewerkingen zijn. Bepaal de gemiddelde tijdscomplexiteit van elke bewerking. (10 punten)

6. (a) Beschrijf het algoritme van Kruskal voor het vinden van de minimaal opspannende boom van een gewogen, ongerichte grafiek. (6 punten)

(b) Pas het algoritme van Kruskal toe op de volgende grafiek en vind de minimaal opspannende boom:

```

(1)---2---(3)

/ |

/ |

5 / 4

-----------

(4)---6---(5)

```

Bereken het totale gewicht van de minimaal opspannende boom. (10 punten)

7. (a) Verklaar het concept van een topologisch soort gerichte acyclische graaf (DAG). (6 punten)

(b) Voer een topologische sortering uit op de volgende DAG:

```

(1) -> (2) -> (3)

\ /

-> (4)

```

Geef de volgorde van de hoekpunten in de topologische sortering op. (10 punten)

8. (a) Beschrijf het concept van binaire zoekbomen (BST's). Leg uit hoe BST's worden gebruikt voor efficiënte zoek- en invoegbewerkingen. (6 punten)

(b) Voeg de volgende elementen in een aanvankelijk lege BST in:20, 10, 30, 5, 15, 25, 35. Teken de resulterende BST en analyseer de tijdscomplexiteit van het zoeken naar een element in deze BST. (10 punten)

Vergeet niet om een ​​duidelijk begrip van de concepten aan te tonen, de juiste uitleg te geven en indien nodig de tijd- en ruimtecomplexiteit van algoritmen te analyseren.