Under övningstillfällena kommer ni att få möjlighet att lösa och diskutera övningar. Notera att några övningar kommer att hållas på engelska.

Nedan listas några förslag på övningar. Ni förväntas inte hinna med allihop. I första hand rekommenderas ni att lösa övningarna listade under "Gamla tentauppgifter m m". Notera att lösningsförslag för de här övningarna är tillgängliga via kurshemsidan (till skillnad från övningarna i kursboken).

Ett antal övningar är lämpliga att lösa både med ett funktionellt och ett objektorienterat programmeringsspråk. Ge i så fall gärna två lösningar, och reflektera över eventuella skillnader mellan dem.

Vi har tänkt gå igenom övningar markerade med * på övningstillfällena (i den ena övningsgruppen), men planeringen är preliminär. Fördelningen av uppgifter mellan olika läsveckor är också preliminär, och kan komma att ändras.

Vecka Ämne Gamla tentauppgifter m m Övningar i kursboken (andra upplagan) Övningar i kursboken (tredje upplagan)
1 Induktion 1.11a*b1, 1.12 1.11a*b, 1.12
Grundläggande tidsanalys P1 2.1*, 2.2*, 2.4-5, 2.7a, 2.10*, 2.11-12, 2.15*, 2.26, 2.31 2.2*, 2.7a, 2.10*, 2.11-12, 2.15*, 2.26, 2.31
Listor, stackar, köer 12/08:1*, 12/08:5, 12/04:3*, 13/04:6 3.2, 3.6, 3.11, 3.15, 3.21-22, 3.24, 3.25a*, 3.27-28, 3.29*, 3.31-32 3.2, 3.6, 3.11, 3.15, 3.21-22, 3.25a, 3.27, 3.28, 3.29*, 3.31-32
2 Listor, stackar, köer 12/12:5, 13/04:5*, 12/08:62, 12/04:53 3.7, 3.33*, 3.34-35, 3.37 3.33*, 3.34
Sortering 7.1-2, 7.15, 7.17 7.14, 7.2, 7.15, 7.17
Träd 12/11:2* 4.1-5, 4.8, 4.41 4.1-3, 4.5, 4.8, 4.41
Prioritetsköer 12/04:4 (för trea), 13/04:3, 13/08:4, 12/11:1*, 13/08:2 6.2*, 6.3*, 6.10ab, 6.37b*, 6.38-39 6.2*, 6.3*, 6.10ab, 6.37b*, 6.38
3 Hashtabeller, "sets", "maps" P3*, 12/08:2*, 11/12:1*, 12/11:3, 13/08:3, 13/08:6, 13/04:4 5.1a-c, 5.4, 5.13b, 5.14, 5.18 5.1a-c, 5.15b, 5.17
Grafer P4, 12/12:2, P5*, P6*, 12/08:4*, 13/08:5 9.1-3, 9.5, 9.38b, 9.41 9.1-2, 9.5, 9.38b, 9.41
4 Grafer P7*, 12/04:6*, P8, 11/12:4, 12/12:6*, 11/12:6 9.7a, 9.10b, 9.15-16, 9.18, 9.20*, 9.26-27, 9.31, 9.42*, 9.44-45, 9.51*, 9.52-53 9.7a, 9.10b, 9.15-16, 9.18, 9.20*, 9.26, 9.31, 9.42*, 9.44-45, 9.51*, 9.52-53
5 Sökträd 12/12:1*, 13/04:1*, P9*, P10*, P11, 12/08:3*, 11/12:2, 12/04:1,2, 11/12:3 (för trea), 12/12:4* 4.9, 4.11-12, 4.16, 4.37, 4.49, 6.37c*, 4.19, 4.24-25, 4.35 4.9, 4.11-12, 4.16, 4.37, 4.49, 6.37c*, 4.19, 4.35, 4.25b
Prefixträd 13/12:6, 11/12:1*, 12/11:35
Skipplistor 11/12:3 med skipplistor* 10.36, 10.38 10.37, 10.39
6 Sortering P12, P13*, P14*, 12/04:4* (för fyra), 12/12:3* 7.11-12, 7.19-20, 7.21a-c, 7.22a, 7.27b, 7.31, 7.33, 7.39-41, 7.48ab* 7.11, 7.19-20, 7.21a-c, 7.22a, 7.27b, 7.31, 7.33, 7.44-46, 7.53ab*
7 Repetition
8 Gamla tentor?

  1. Notera att övningarna inte är korrekt formulerade. En del av uppgiften är att rätta till formuleringarna.

  2. Använd bokföringsmetoden.

  3. Använd bokföringsmetoden.

  4. Använd insättningssortering, inte radixsortering.

  5. Med listor innehållandes strängar. Algoritmen ska vara linjär i listornas längd plus strängarnas längd.