16 poängsfrågor om design och analys av algoritmer (CS1201):
1. (a) Vad är en dela-och-härska-algoritm? Förklara det allmänna tillvägagångssättet för dela-och-härska-algoritmer. (6 poäng)
(b) Använd dela-och-härska-metoden för att designa en algoritm för att hitta minimielementet i en array av n element. Analysera tidskomplexiteten för din algoritm. (10 poäng)
2. (a) Förklara begreppet hash- och kollisionsupplösningstekniker. (6 poäng)
(b) Överväg en hashtabell med storlek m och en uppsättning av n element som ska hashas. Antag att elementen är jämnt fördelade mellan de m slitsarna. Vad är sannolikheten för en kollision när n =m/2? Analysera det genomsnittliga antalet jämförelser som krävs för att framgångsrikt infoga alla element i hashtabellen med linjär sondering. (10 poäng)
3. (a) Beskriv konceptet med dynamisk programmering och förklara hur det skiljer sig från dela-och-härska-metoden. (6 poäng)
(b) Använd dynamisk programmering för att lösa stångskärningsproblemet, där en stång med längden n kan skäras till mindre stavar, och varje stång med längden i har ett pris p[i]. Målet är att hitta den maximala intäkter som kan erhållas genom att skära spöet i mindre bitar. Analysera komplexiteten i tid och rum i din algoritm. (10 poäng)
4. (a) Förklara begreppet NP-fullständighet och dess betydelse vid analys av algoritmer. (6 poäng)
(b) Bevisa att följande problem är NP-komplett:Givet en uppsättning av n objekt med deras respektive vikter och värden, bestäm om det finns en delmängd av dessa objekt vars totala vikt är mindre än eller lika med en given gräns och vars totala värdet är maximerat. (10 poäng)
5. (a) Förklara konceptet med en amortiserad analys av algoritmer. Varför används det och vilka är fördelarna med det? (6 poäng)
(b) Utför en amortiserad analys av stackdatastrukturen, där push- och pop-operationer är de enda tillåtna operationerna. Bestäm den genomsnittliga tidskomplexiteten för varje operation. (10 poäng)
6. (a) Beskriv Kruskals algoritm för att hitta det minsta spännträdet för en vägd oriktad graf. (6 poäng)
(b) Tillämpa Kruskals algoritm på följande graf och hitta det minsta spännträdet:
```
(1)---2---(3)
/ |
/ |
5/4
-----------
(4)---6---(5)
```
Beräkna den totala vikten av det minsta spännträdet. (10 poäng)
7. (a) Förklara konceptet med en topologisk typ av en riktad acyklisk graf (DAG). (6 poäng)
(b) Utför en topologisk sortering på följande DAG:
```
(1) -> (2) -> (3)
\ /
-> (4)
```
Ange ordningen på hörn i den topologiska sorteringen. (10 poäng)
8. (a) Beskriv konceptet med binära sökträd (BST). Förklara hur BST används för effektiv sökning och infogning. (6 poäng)
(b) Infoga följande element i en initialt tom BST:20, 10, 30, 5, 15, 25, 35. Rita den resulterande BST och analysera tidskomplexiteten för att söka efter ett element i denna BST. (10 poäng)
Kom ihåg att visa en tydlig förståelse av begreppen, ge korrekta förklaringar och analysera tids- och rumskomplexiteten hos algoritmer när det behövs.
