Datastrukturer och databaser för STS

och

Programmeringsteknik II för F

Arne Andersson


Läs- och studieanvisningar


Kapitel 1

  1. Kapitel 1.1 - 1.3: De grundläggande matematiska begreppen exponenter, logaritmer och serier skall du kunna sedan tidigare. Se till att du minns vad det hela handlar om. Speciellt kommer logaritmbegreppet att vara flitigt använt i kursen. 1.2.4, 1.2.5 och 1.3 skall du förstå ordentligt.

  2. Kapitel 1.6 - 1.7: Dessa avsnitt bör du titta igenom för din egen skull för att fräscha upp dina Java-kunskaper.


Kapitel 2

Avsnitt 2.1 är mycket viktigt, du skall förstå begreppen Ordo, Omega och Theta ordentligt. Resten av kapitlet bör du läsa igenom en gång.


Kapitel 3

Listor, stackar och köer. Hela kapitlet är viktigt, utom första halvan av 3.2.6 (Polynomial ADT) och 3.2.7. Andra halvan av 3.2.6, radix sort behandlas i samband med sorteringsalgoritmer.


Om trädsturkturer och sökträd i kapitel 4, 10 och 12


Kapitel 5: hashkodning

Hela kapitel 5, utom 5.4.2, är viktigt.


Databaser.

Du skall kunna grundläggande begrepp från föreläsningsbilderna, som finns på referensmaterial-sidan. Du skal också kunna databaslaborationen noga, En fråga om den kan mycket väl komma på tentamen.


Kapitel 6: Prioritetsköer

Kapitel 6.1 - 6.3 är mycket viktiga, kapitel 6.4 läser du igenom.

Du skall vara väl förtrogen med hur man representerar en heap som ett binärt träd i en vektor. Du skall också känna till hur man gör, insert, deleteMin, decreaseKey och buildHeap. Du skall kunna förklara varför insert, deleteMin och decreaseKey tar O(log n) tid, och varför buildHeap tar O(n) tid.


Kapitel 7: Sorteringsalgoritmer


Kapitel 9, Grafer, grafalgoritmer

Avsnitt i läroboken:


Kapitel 10.1.2, Huffman-kodning

Viktigt, du skall kunna visa hur Huffman-koder beräknas för en given uppsättnnig tecken. Du skall också förstå hur man använder Huffman-koder för datakompression.