Under övningstillfällena kommer ni att få möjlighet att lösa och diskutera övningar. Det finns två typer av övningar som går parallellt i varsin sal. I den ena salen går en övningsledare genom uppgifter på tavlan. Detta sker på engelska. I den andra går övningsledaren runt och svarar på frågor medan studenterna jobbar med övningarna själva. Det är två övningstillfällen i veckan. Från och med lv 5 kommer de uppgifter som inte hinns med vid de första tillfället gå igenom vid andra tillfället. När detta är klart används eventuellt resterande tid andra tillfället till att lösa samma uppgifter igen från början (så många som hinns med).
Genomgång på tavlan sker i den salan som står först nämnd i schemat vid aktuellt tillfälle och självständigt arbete sker i den sist nämnda salen.
De slides som Marco använt vid övningstillfällena finns här: v1, v2, v3, v4, v5, v6, v7
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).
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 |
| 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*, 11/12:1* | 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, 12/11:34 | |||
| 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.1-2, 7.15, 7.17 7.11-12, 7.19-20, 7.21a-c, 7.22a, 7.27b, 7.31, 7.33, 7.39-41, 7.48ab* | 7.15, 7.2, 7.15, 7.17 7.11, 7.19-20, 7.21a-c, 7.22a, 7.27b, 7.31, 7.33, 7.44-46, 7.53ab* |
| 7 | Repetition |
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.↩
Med listor innehållandes strängar. Algoritmen ska vara linjär i listornas längd plus strängarnas längd.↩
Använd insättningssortering, inte radixsortering.↩