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? |
Notera att övningarna inte är korrekt formulerade. En del av uppgiften är att rätta till formuleringarna.↩
Använd bokföringsmetoden.↩
Använd bokföringsmetoden.↩
Använd insättningssortering, inte radixsortering.↩
Med listor innehållandes strängar. Algoritmen ska vara linjär i listornas längd plus strängarnas längd.↩