1. (a) Hvad er en del-og-hersk-algoritme? Forklar den generelle tilgang til del-og-hersk-algoritmer. (6 mark)

(b) Brug opdel-og-hersk tilgangen til at designe en algoritme til at finde minimumselementet i en række af n elementer. Analyser tidskompleksiteten af ​​din algoritme. (10 mark)

2. (a) Forklar begrebet hashing og kollisionsopløsningsteknikker. (6 mark)

(b) Overvej en hash-tabel af størrelse m og et sæt af n elementer, der skal hash. Antag, at elementerne er ensartet fordelt mellem de m slidser. Hvad er sandsynligheden for en kollision, når n =m/2? Analyser det gennemsnitlige antal sammenligninger, der kræves for at indsætte alle elementerne i hash-tabellen ved hjælp af lineær sondering. (10 mark)

3. (a) Beskriv begrebet dynamisk programmering og forklar, hvordan det adskiller sig fra del-og-hersk tilgangen. (6 mark)

(b) Brug dynamisk programmering til at løse stangskæringsproblemet, hvor en stang med længden n kan skæres i mindre stænger, og hver stang med længden i har en pris p[i]. Målet er at finde den maksimale indtjening, der kan opnås ved at skære stangen i mindre stykker. Analyser tids- og rumkompleksiteten af ​​din algoritme. (10 mark)

4. (a) Forklar begrebet NP-fuldstændighed og dets betydning i analysen af ​​algoritmer. (6 mark)

(b) Bevis, at følgende problem er NP-komplet:Givet et sæt af n elementer med deres respektive vægte og værdier, afgør, om der eksisterer en delmængde af disse elementer, hvis samlede vægt er mindre end eller lig med en given grænse, og hvis total værdien er maksimeret. (10 mark)

5. (a) Forklar konceptet med en amortiseret analyse af algoritmer. Hvorfor bruges det, og hvad er dets fordele? (6 mark)

(b) Udfør en amortiseret analyse af stakdatastrukturen, hvor push- og pop-operationer er de eneste tilladte operationer. Bestem den gennemsnitlige tidskompleksitet for hver operation. (10 mark)

6. (a) Beskriv Kruskals algoritme til at finde minimumspændingstræet for en vægtet urettet graf. (6 mark)

(b) Anvend Kruskals algoritme på følgende graf og find minimumspændingstræet:

```

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

/ |

/ |

5/4

-----------

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

```

Beregn den samlede vægt af minimumspændingstræet. (10 mark)

7. (a) Forklar begrebet en topologisk form for en rettet acyklisk graf (DAG). (6 mark)

(b) Udfør en topologisk sortering på følgende DAG:

```

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

\/

-> (4)

```

Angiv rækkefølgen af ​​toppunkter i den topologiske sortering. (10 mark)

8. (a) Beskriv begrebet binære søgetræer (BST'er). Forklar, hvordan BST'er bruges til effektive søge- og indsættelsesoperationer. (6 mark)

(b) Indsæt følgende elementer i en oprindeligt tom BST:20, 10, 30, 5, 15, 25, 35. Tegn den resulterende BST og analyser tidskompleksiteten ved at søge efter et element i denne BST. (10 mark)

Husk at demonstrere en klar forståelse af begreberne, give korrekte forklaringer og analysere tids- og rumkompleksiteten af ​​algoritmer, når det kræves.