Warning! This is the 2012 course's website! You probably want the current course website.

Exempeltentamen

Eftersom årets tentamen skiljer sig en del i form och innehåll mot föregående års, så ger jag en exempeltenta här. Såhär ser försättsbladet ut.

Tentan är uppdelad i 6 "lätta" frågor och 3 "svåra" frågor.

• Frågorna har inga poäng, endast rätt eller fel gäller!
• För godkänt krävs att du har svarat rätt på 5 av de lätta frågorna.
• För väl godkänt krävs dessutom att du har svarat rätt på 2 av de svåra frågorna.

Ni får inte ha kursboken med till tentan. Däremot får ni ha en fusklapp — en (1) A4-sida med valfria anteckningar, hand- eller maskinskrivna. OBS! Endast ena sidan får vara använd!

Nedan följer ett antal frågor från övningarna och kursboken, som skulle kunna vara passande tentafrågor. Några av frågorna är lite för stora för en tenta (t.ex. att bygga ett träd från sekvensen a b c … x y z), så motsvarande tentafråga blir isåfall en deluppgift (t.ex. att stoppa in x y z i ett redan givet träd).

"Lätta" frågor

En tentamen skulle kunna bestå av sex av dessa frågor.

Frågor från övningssidan

1. Övning 6 (komplexiteten för KWArrayList-metoder) i avsnittet om komplexitet från vecka 11.
2. Övning 7 (algoritm som tar bort kommentartext) i avsnittet om listor från vecka 11.
3. Övning 6 (sätt in element i en heap) i avsnittet om prioritetsköer från vecka 13.
4. Övning 5 (sätt in element i ett träd) i avsnittet om självbalanserande träd från vecka 16. (För att uppgiften inte ska ta för lång tid eller för många svarspapper, så blir en motsvarande tentafråga att stoppa in ett eller två värden i ett redan färdigbyggt träd, inte att bygga ett träd från början).
5. Övning 9, 10 eller 11 (implementera en sorteringsfunktion) i avsnittet om Haskell från vecka 17.
6. Övning 7 (sortera för hand) i avsnittet om sortering från vecka 18.
7. Övning 8 (vilken komplexitet har sorteringsalgoritmen) i avsnittet om sortering från vecka 18.

Frågor från inlämningsuppgifterna

1. Beräkna komplexiteten för någon av funktionerna Ex1–Ex7 i inlämningsuppgift 1.

Frågor från kursboken

1. Kapitel 2:
   1. Programming exercise 1 på sid 69.
   2. Programming exercise 2 på sid 69.
   3. Programming exercise 1 på sid 98.
   4. Programming exercise 3 på sid 98.
2. Kapitel 3:
   1. Programming exercise 1 på sid 161.
   2. Self-check exercise 1+2 (tillsammans) på sid 169.
3. Kapitel 4:
   1. Review question 1 på sid 238–9.
   2. Någon av review questions 2–7 på sid 239.
4. Kapitel 5:
   1. Programming exercise 4 på sid 259.
5. Kapitel 6:
   1. Self-check exercise 4 på sid 303.
   2. Self-check exercise 2 på sid 306.
   3. Programming exercise 3 på sid 315.
   4. Self-check exercise 2 på sid 332.
   5. Self-check exercise 3 på sid 332.
   6. Self-check exercise 1+2 (tillsammans) på sid 344.
   7. Self-check exercise 3 på sid 344.
   8. Quick-check exercise 5 på sid 355.
   9. Quick-check exercise 8 på sid 355.
6. Kapitel 7:
   1. Self-check exercise 2 på sid 382.
   2. Self-check exercise 3 på sid 383.
   3. Programming exercise 1 på sid 383.
   4. Self-check exercise 1 på sid 395.
   5. Programming exercise 5 på sid 395.
   6. Quick-check exercise 5–7 (tillsammans) på sid 415.
   7. Review question 1 på sid 416.
   8. Review question 2 på sid 416.
7. Kapitel 8:
   1. Self-check exercise 1 på sid 427.
   2. Self-check exercise 1 på sid 435.
   3. Self-check exercise 1 på sid 446.
   4. Self-check exercise 1+2 (tillsammans) på sid 451.
   5. Self-check exercise 1 på sid 460.
   6. Self-check exercise 2 på sid 460.
   7. Quick-check exercise 6, 7 eller 8 på sid 460.
   8. Programming exercise 5 på sid 468.
8. Kapitel 9:
   1. Self-check exercise 3 på sid 490.
   2. Self-check exercise 2 på sid 502.
   3. Quick-check exercise 2 på sid 533.
   4. Review question 2 på sid 534.
   5. Review question 3 på sid 534.
9. Kapitel 10:
   1. Self-check exercise 1+2+3 (tillsammans) på sid 559–60.
   2. Self-check exercise 1+2 (tillsammans) på sid 572.
   3. Self-check exercise 1 eller 2 på sid 588.
   4. Self-check exercise 3 eller 4 på sid 588.
   5. Någon av quick-check exercises 4–8 på sid 590.

"Svåra" frågor

Dessutom skulle man kunna tänka sig att tentan består av tre av följande lite svårare frågor.

Frågor från övningssidan

1. Övning 2 (en algoritm som översätter infixuttryck) i avsnittet om stackar från vecka 12.
2. Övning 5 (modifiera ett binärt sökträd) i avsnittet om träd och sökträd från vecka 13.
3. Övning 10 (en linjär algoritm som ordnar om ett fält med enbart 2 värden) i avsnittet om sortering från vecka 18.
4. Övning 6 (bipartita grafer) i avsnittet om grafer från vecka 19.

Frågor från kursboken

1. Kapitel 2:
   1. Programming project 2 på sid 145.
   2. Samma uppgift, fast i Haskell.
2. Kapitel 5:
   1. Programming project 3 på sid 291.
   2. Programming project 7 på sid 291.
   3. Samma uppgifter, fast i Haskell.
3. Kapitel 6:
   1. Programming project 7 på sid 357.
   2. Programming project 11 på sid 358.
4. Kapitel 7:
   1. Programming project 2 på sid 416.
5. Kapitel 10:
   1. Programming project 7 på sid 592–3.
   2. Programming project 8 på sid 593.