Datastrukturer (DAT036), lp2 2012

Under övningstillfällena kommer ni att få möjlighet att lösa och diskutera övningar.

Nedan listas några förslag på övningar. Ni förväntas inte hinna med allihop. Vi planerar att gå igenom övningar markerade med * på övningstillfällena, men planeringen för senare veckor är preliminär.

Vecka Ämne Övningar i kursboken (andra upplagan) Övningar i kursboken (tredje upplagan) Andra övningar och gamla tentauppgifter
1 Induktion 1.11a*b1, 1.12 1.11a*b, 1.12
Grundläggande tidsanalys 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 P1
Sortering 7.1-2, 7.15, 7.17 7.12, 7.2, 7.15, 7.17
2 Listor, stackar, köer 3.2, 3.6-7, 3.11, 3.15, 3.21-22, 3.24, 3.25a*, 3.27-28, 3.29*, 3.31-32, 3.33*, 3.34-35, 3.37 3.2, 3.6, 3.11, 3.15, 3.21-22, 3.25a, 3.27, 3.28, 3.29*, 3.31-32, 3.33*, 3.34 2012/08:1,5, 2012/04:3
Amorterad tidskomplexitet P2*
Träd 4.1-5, 4.8, 4.41 4.1-3, 4.5, 4.8, 4.41
Prioritetsköer 6.2*, 6.3*, 6.10ab, 6.32, 6.37b*, 6.38-39 6.2*, 6.3*, 6.10ab, 6.32, 6.37b*, 6.38 2012/04:4 (för trea)
3 Prioritetsköer 6.33a 6.33a
Hashtabeller, "sets", "maps" 5.1a-c, 5.4, 5.13b, 5.14, 5.18 5.1a-c, 5.15b, 5.17 P3*, 2012/08:2*, 2011/12:1*
Grafer 9.1-3, 9.5, 9.38b, 9.41 9.1-2, 9.5, 9.38b, 9.41 P4, P5*, P6*, 2012/08:4*
4 Grafer 9.7a, 9.10b, 9.15-16, 9.18, 9.20* 9.7a, 9.10b, 9.15-16, 9.18, 9.20* P7*, 2012/04:6*
5 Grafer 9.26-27, 9.31, 9.42*, 9.44-45, 9.51*, 9.52-53 9.26, 9.31, 9.42*, 9.44-45, 9.51*, 9.52-53 P8, 2011/12:4, 2011/12:6*
Sökträd 4.9, 4.11-12, 4.16, 4.37, 4.49, 6.37c* 4.9, 4.11-12, 4.16, 4.37, 4.49, 6.37c* P9*, P10*
6 Sökträd 4.19, 4.24-25, 4.27-28, 4.35 4.19, 4.35, 4.25b, 4.27 P11*, P12, 2012/08:3*, 2012/04:1,2, 2011/12:1, 2011/12:3*
Skipplistor 10.36, 10.38 10.37, 10.39 2011/12:3 med skipplistor*
Amorterad tidskomplexitet 11.2, 11.11, 11.14 11.2, 11.11, 11.14 2012/08:6*, 2012/04:5, 2011/12:5*
7 Sortering 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* P13, P14*, P15*, 2012/04:4 (för fyra)

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

  2. Använd insättningssortering, inte radixsortering.↩