Under övningstillfällena kommer ni att få möjlighet att lösa och diskutera övningar. Under läsvecka ett kommer dessutom en av övningsledarna att gå igenom lite funktionell programmering på övningspassen: 29/10 i ML12 och 1/11 i ML2.
Två salar har bokats för varje övningspass. I den ena salen (den som står listad först i schemat) kommer lösningar att presenteras, och i den andra salen ges mer tid åt egen problemlösning (bortsett från under läsvecka ett; se ovan). Uppdatering: Eftersom de flesta övningsdeltagarna har valt att gå till salen där lösningar presenteras så tas det andra alternativet bort fr o m 2013-11-12.
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 | 3.7, 3.33*, 3.34-35, 3.37 | 3.33*, 3.34 |
Sortering | 7.1-2, 7.15, 7.17 | 7.13, 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, 12/04:54 | 6.2*, 6.3*, 6.10ab, 6.32, 6.33a, 6.37b*, 6.38-39 | 6.2*, 6.3*, 6.10ab, 6.32, 6.33a, 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 |
Splayträd | 13/08:1, 11/12:3 med splayträd*, P12 | 4.27-28 | 4.27 | |
Skipplistor | 11/12:3 med skipplistor* | 10.36, 10.38 | 10.37, 10.39 | |
6 | Sortering | P13, P14*, P15*, 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 |