Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Datastructuren voor CKI
Hoorcollege week 1: Intro van cursus en herhaling van Java. Lees hfdstk 1 en 2 zelf. Vraag wat u daarin niet snapt.
In te leveren opgave week 1: Project P-1.1 als uw studentnummer even is, Project P-1.3 als uw studentnummer oneven is.
Inleveren op adres datastructuren-1@phil.uu.nl voor dinsdag 14-2 13:00.
(Update: Inleveren kan nog tot 21-2 13:00. Je krijgt geen cijfer voor dit onderdeel,
maar zonder dit onderdeel krijg je geen cijfer voor opgave 2.)
Op college (10-2) gebruikte voorbeeld programma Nummer ter illustratie van de volgende
nieuwe features van Java 5: generics, enum types (inclusief gebruik van ordening), for-each construct, en auto-boxing.
eerste hoorcollege week 2: Arrays en (doubly) linked lists, informele complexiteits-analyse van singly/doubly
recursive methoden, hfdstk 3.
In te leveren opgaven week 2: Projecten P-3.3 en P-3.4.
Inleveren op adres datastructuren-2@phil.uu.nl voor dinsdag 21-2 13:00.
tweede hooorcollege week 2: Complexiteitsanalyse van algorithmen
gebaseerd op asymptotisch gedrag (almost all,O,Omega,Theta), hfdstk 4.
eerste hoorcollege week 3: Bespreking project P-3.3.
Het ADT (abstract data type) stack en enige typische toepassingen, hfdstk 5 eerste deel.
tweede hoorcollege week 3: Generificatie van project P-3.3.
Het ADT queue en enige typische toepassingen, hfdstk 5 tweede deel.
eerste hoorcollege week 4: afdrukken van high-scores mbv Iterator,
en daar de Generificatie van.
Iterators, geamortizeerde complexiteit en Array Lists/Vectors, hfdstk 6.1 en 6.3.
Praktikum opdracht R-6.3.
tweede hoorcollege week 4: Bomen, pre-/postorder walks, binaire bomen,
array representatie van binaire bomen, heaps, Heap sort,
hfdstk 7.1,7.2, begin 7.3, 8.3.
eerste hoorcollege week 5: Priority Queue ADT/Interface met drie implementaties: List, Sorted List, en Heap. Hierop gebaseerde Priority Queue Sort met instanties: Selection Sort, Insertion Sort, en Heap Sort met complexiteiten O(n^2), O(n^2), en O(n log n), respectievelijk. Bewijs dat comparison-based sorting Omega(n log n) is (dus dat Heap Sort optimaal is). hfdstk 8 en 11.3.
Praktikum opdracht: Maak een expression-tree uit de tokens in een Queue (zie inleveropgave week 3, dus ipv ze met een stack gelijk te verwerken, slaan we ze in een boom-structuur op).
tweede hoorcollege week 5: Adaptable Priority Queues (weer met drie implementaties), (niet-binaire) Trees, Sequences. Begin met Maps en Hashing. hfdstk 8.4, 7,1, 6.4, begin 9.
eerste hoorcollege week 6: Maps, hashing. hfdstk 9.1, 9.2.
tweede hoorcollege week 6: Vervallen wegens ziekte docent.
eerste hoorcollege week 7: Dictionaries, binary search, AVL trees, begin Skip Lists. hfdstk 9.3, 10.1, 10.2, deel 9.4.
tweede hoorcollege week 7: Dictionaries, (2,4)-trees, en red-black-trees gezien als (2,4)-trees waarbij de knopen als AVL-trees geimplementeerd zijn. hfdstk 10.4, 10.5. Praktikum-opdracht: maak een red-black-tree implementatie van een zoekbomen.
eerste hoorcollege week 8: divide-and-conquer sorting, met als speciale gevallen merge en quick sort. hfdstk 11.1,2,3.
tweede hoorcollege week 8: bucket-sort, radix-sort, verzamelingen, en union-find met toepassing in automatisch stelling bewijzen. hfstk 11 rest.
eerste hoorcollege week 9: left-to-right pattern matching met als speciale gevallen, brute force, BM, en KMP. hfdstk 12.1, 12.2.
tweede hoorcollege week 9: tries en huffman coding. hfdstk 12.3, 12.4.
In te leveren opgave week 9: maak het volgende (heel eenvoudige) natuurlijke taal interface bovenop red-black trees:
laat een zin bestaan uit een aantal door spaties gescheiden woorden.
als de zin eindigt op een ! (uitroepteken) voeg dan de woorden toe aan de red-black-tree.
als de zin eindigt op een ? (vraagteken) geef dan van ieder woord in de zin aan of het al bekend is.
als de zin eindigt op een # (hekje) verwijder dan ieder woord in de zin.
Inleveren op adres datastructuren-5@phil.uu.nl voor donderdag 27-4.