Göm menyn

TDDE22 Datastrukturer och algoritmer

Föreläsningar

Föreläsningarna i år går på distans via Zoom med följande mötesinfo:

  • länk
  • Meeting ID: 647 1440 7975
  • Passcode: DALG
  • Observera att SSO-inloggning via LiU's portal krävs. I Zoom klickar du på SSO-inloggning och ge adressen liu-se.zoom.us.
Dessvärre tillåter vi inte inspelning av varken ljud eller video (se denna länk för mer info).

Här laddas slides upp strax före att föreläsningen börjar, tillsammans med läsanvisningar för OpenDSA.

Föreläsning 1

Kursadministration. RAM-modellen. Programspråksnotation. Abstrakta datatyper. Ordo-notation, Algoritmanalys. (Slides)
OpenDSA: kapitel: 0.1, 1.1, 3.1-3.14, 2.6.

Föreläsning 2

ADTn Stack, ADTn Kö, ADTn ArrayLista, ADTn NodLista. (Slides)
OpenDSA: kapitel: 4.1-4.13

Rekommenderade länkar:
Visualisering av stack.
Visualisering av kö implementerad med länkad lista.

Föreläsning 3

ADTn Map, Hashtabeller, ADTn Dictionary. (Slides)
OpenDSA: kapitel: 10.1-10.9

Labb 1

Rekommenderade länkar:
Visualisering av hashtabell med separat länkning.
Visualisering av hashtabell med öppen adressering.

Föreläsning 4

Träd: grundläggande begrepp, ADTn Träd, Datastrukturer för att representera träd. Binära Sökträd. (Slides)
OpenDSA: kapitel 5.2, 5.3
OpenDSA: kapitel 6.1-6.12
OpenDSA: kapitel 8.1, 8.3

Rekommenderad länk:
Visualisering av BST.

Föreläsning 5

Sökträd: AVL-träd, "Multi-Way"-sökträd. (Slides)
OpenDSA: kapitel 7.1, 7.2
OpenDSA: kapitel 9.1, 9.4, 9.5, 9.6

Labb 2

Rekommenderad länk:
Visualisering av AVL-träd. Det går att sakta ned animationshastigheten för att bättre se vad som händer.

Föreläsning 6

Splay-träd, Prioritetsköer och deras implementation, Heapar. (Slides)
OpenDSA: kapitel 6.13
OpenDSA: kapitel 7.3

Labb X

Rekommenderade länkar:
Visualisering av Splay-träd.
Visualisering av Heap.
Föreläsning 7

Sortering I. Insertion sort, Selection Sort, Quick-sort. Selection / Median finding. (Slides) ida.liu.se/opendsa/Books/TDDE22F21/html/InSort.html">12.1, 12.2, 12.3, 12.4, 12.5, 12.6, 12.7, 12.11

Labb 3

Rekommenderade länkar:
Visualisering av diverse sorteringsalgoritmer.
Quick sort: Ungersk folkdansversion.
Insertion sort: Rumänsk folkdansversion.
Föreläsning 8

Sortering II. Heapsort, Mergesort, Undre gränser för sortering, Counting Sort, Bucket sort, Radix Sort.(Slides)
OpenDSA: kapitel 12.9, 12.10, 12.12, 12.13, 12.14, 12.16

Rekommenderade länkar:
Visualisering av Heap-sort.
Visualisering av diverse algoritmer. Kan användas för att titta på Merge-sort.
Visualisering av Bucket-sort.
Visualisering av Counting-sort.
Visualisering av Radix-sort.
Föreläsning 9

Grafer. ADTn Graf, Representation, Grafsökning. (Slides)
OpenDSA: kapitel 11.1, 11.2, 11.3
Labb 4

Visualisering Bredden-först sökning.
Visualisering Djupet-först sökning.
Visualisering sammanhängande komponenter.
Föreläsning 10

Riktade grafer: Transitivt hölje, Topologisk sortering. Viktade grafer: Kortaste vägar. (Slides)
OpenDSA: kapitel 11.4, 11.5
OpenDSA: kapitel 14.1
Tentaföreläsning

Exempel på tentauppgifter och hur de löses. (Slides)
Tentan: (Lydelse)


Sidansvarig: Magnus Nielsen
Senast uppdaterad: 2021-10-12