1. (a) Hva er en del-og-hersk-algoritme? Forklar den generelle tilnærmingen til del-og-hersk-algoritmer. (6 merker)

(b) Bruk del-og-hersk-tilnærmingen til å designe en algoritme for å finne minimumselementet i en rekke av n elementer. Analyser tidskompleksiteten til algoritmen din. (10 merker)

2. (a) Forklar begrepet hashing og kollisjonsoppløsningsteknikker. (6 merker)

(b) Vurder en hashtabell med størrelse m og et sett med n elementer som skal hashes. Anta at elementene er jevnt fordelt mellom de m sporene. Hva er sannsynligheten for en kollisjon når n =m/2? Analyser det gjennomsnittlige antallet sammenligninger som kreves for å sette inn alle elementene i hashtabellen ved hjelp av lineær sondering. (10 merker)

3. (a) Beskriv konseptet med dynamisk programmering og forklar hvordan det skiller seg fra del-og-hersk-tilnærmingen. (6 merker)

(b) Bruk dynamisk programmering for å løse stavskjæringsproblemet, der en stang med lengde n kan kuttes i mindre stenger, og hver stang med lengde i har en pris p[i]. Målet er å finne den maksimale inntekten som kan oppnås ved å kutte stangen i mindre biter. Analyser tids- og romkompleksiteten til algoritmen din. (10 merker)

4. (a) Forklar begrepet NP-fullstendighet og dets betydning i analysen av algoritmer. (6 merker)

(b) Bevis at følgende problem er NP-fullstendig:Gitt et sett med n elementer med deres respektive vekter og verdier, finn ut om det eksisterer en delmengde av disse elementene hvis totale vekt er mindre enn eller lik en gitt grense og hvis total verdien er maksimert. (10 merker)

5. (a) Forklar konseptet med en amortisert analyse av algoritmer. Hvorfor brukes det, og hvilke fordeler har det? (6 merker)

(b) Utfør en amortisert analyse av stabeldatastrukturen, der push- og pop-operasjoner er de eneste tillatte operasjonene. Bestem den gjennomsnittlige tidskompleksiteten for hver operasjon. (10 merker)

6. (a) Beskriv Kruskals algoritme for å finne minimumspenningstreet til en vektet urettet graf. (6 merker)

(b) Bruk Kruskals algoritme på følgende graf og finn minimumspenningstreet:

```

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

/ |

/ |

5/4

----------

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

```

Beregn totalvekten til minimumspenningstreet. (10 merker)

7. (a) Forklar konseptet med en topologisk form for en rettet asyklisk graf (DAG). (6 merker)

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

```

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

\ /

-> (4)

```

Oppgi rekkefølgen på toppunktene i den topologiske sorteringen. (10 merker)

8. (a) Beskriv konseptet med binære søketrær (BST). Forklar hvordan BST-er brukes for effektive søke- og innsettingsoperasjoner. (6 merker)

(b) Sett inn følgende elementer i en opprinnelig tom BST:20, 10, 30, 5, 15, 25, 35. Tegn den resulterende BST og analyser tidskompleksiteten ved å søke etter et element i denne BST. (10 merker)

Husk å demonstrere en klar forståelse av begrepene, gi korrekte forklaringer og analyser tids- og romkompleksiteten til algoritmer når det er nødvendig.