Göm menyn

TDDC70 Datastrukturer och algoritmer

Föreläsningar

Preliminär föreläsningsplan med läshänvisning till kursboken av Goodrich/Tamassia (GT). Läshänvisning för de som använder andra upplagan av Introduction to Algorithms finns här. Oh-bilder från föreläsningarna kommer att göras tillgängliga nedan i anslutning till respektive föreläsning.

Visualiseringsverktyget som används för att demonstrera vissa datastrukturer finns här.

Föreläsning 1

Kursadministration. RAM-modellen. Programspråksnotation. Abstrakta datatyper. Ordo-notation.
GT 4.1-4.2, Appendix A.
OH-bilder
Föreläsning 2

Algoritmanalys.
GT 4.1-4.2 (forts.)
OH-bilder
Föreläsning 3

Tävlingsprogrammering och DALG-mästerskapet 2012.
Rekursion, ADTn Stack, ADTn Kö, ADTn ArrayLista, ADTn NodLista.
GT 3.5, 5.1-5.2, 6.1-6.2.
Stack applet
Queue applet
Cyclic Queue applet
Linked List applet
Doubly-Linked List applet (längst ned på sidan)
OH-bilder
Föreläsning 4

ADTn Map, Hashtabeller, ADTn Dictionary. Skip-lista.
GT 9.1-9.2, 9.4-9.5
Lafore's Separate-Chaining Hash Table
Lafore's Linear-Probe Hash Table
Lafore's Quad/Double Hash Table
Hashing Animation Tool
Skip List Applet
OH-bilder
Föreläsning 5

Träd: grundläggande begrepp, ADTn Träd, Datastrukturer för att representera träd. Binära Sökträd.
GT 7.1-7.3, 10.1
Binary Search Tree applet (väj simple i menyn där none är valt från början för att se nyckelvärdena)
OH-bilder

Föreläsning 6

Sökträd: AVL-träd, "Multi-Way"-sökträd.
GT 10.2, 10.4, 14.3
AVL-tree applet, (2.4)-tree applet, B-tree applet
OH-bilder

Föreläsning 7

Splay-träd, Prioritetsköer och deras implementation, Heapar, Union/Find.
GT 10.3, 8.1-8.2, 8.3.1-8.3.4, 11.4
Splay Tree applet (väj simple i menyn där none är valt från början för att se nyckelvärdena)
Priority Queue applet (baserad på MinHeap)
OH-bilder
Föreläsning 8

Sortering I. Insertion sort, Selection Sort, Quick-sort.
Selection / Median finding, QuickSelect.
GT 3.1.2, 11.2, 11.5
Sorting algorithms applet
OH-bilder
Föreläsning 9

Sortering II. Heapsort, Mergesort, Undre gränser för sortering, Counting Sort, Bucket sort, Radix Sort.
GT 8.3.5-8.3.6, 11.1, 11.3
Heap Sort Applet
Merge Sort Applet
Radix Sort Algorithm Visualization Applet (baserad på Counting Sort)
Radix Sort Applet (baserad på Bucket Sort, startas med knapp längst ned på sidan)
OH-bilder
Föreläsning 10

Grafer. ADTn Graf, Representation, Grafsökning
GT 13.1-13.3
Graph Traversal Applet
BFS/DFS animation
Ett spel som använder grannmatriser
OH-bilder
Föreläsning 11

Riktade grafer: Transitivt hölje, Topologisk sortering. Viktade grafer: Kortaste vägar.
GT 13.4-13.5
Topological Sort Applet
Dijkstra's Algorithm Applets (klicka på länkarna "Java applet demos" i vänstermarginalen)
Connected components animation
Transitive closure animation
Shortest path animation
OH-bilder
Föreläsning 12

Metoder för algoritmdesign: Divide & conquer, Dynamisk programmering, Giriga algoritmer.
GT (11.1), 12.2, 12.4
OH-bilder
Föreläsning 13

Reservtillfälle
Gamla tentor finns här.


 


Sidansvarig: Tommy Färnqvist
Senast uppdaterad: 2012-10-09