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
college Algoritmen en Datastructuren 2005-2006
[go: Go Back, main page]

Algoritmen en Datastructuren 2005-2006

Deze pagina wordt regelmatig bijgewerkt: raadpleeg altijd de meest recente versie.

Dit is de primaire bron van informatie over het vak Algoritmen en Datastructuren. Daarnaast is een Nestorpagina voor dit vak: daar staan oa. de prakticumopdrachten en bijkomend materiaal voor het prakticum.

Versie 20-12-2005 (aanpassing rooster week 5, 6 en 8).

Inhoud

Analyse en ontwerp van algoritmen en datastructuren; graafalgoritmen.
Dit vak overdekt een breed gebied binnen ontwerp en analyse van algoritmen en datastructuren, zoals asymptotische notatie voor complexiteit, worst-case analyse, randomisering, algoritmische paradigma's, waaronder greedy methoden, divide- en conquer, dynamisch programmeren, backtracking en branch-and-bound. Ook geavanceerde datastructuren komen aan de orde, zoals priority queues, AVL-bomen, 2-4-bomen, red-black trees, splay trees, B-trees, skip-lists, en union-find bomen.
Tenslotte behandelen we graafalgoritmen, waaronder depth-first en breadth-first traversals, topologisch sorteren, kortste-pad-algoritmen (all-pairs and single-source), en algoritmen voor minimale opspannende bomen.

Cursusmateriaal

We gebruiken het boek Algorithm Design. Foundations, Analysis, and Internet Examples van Michael T. Goodrich & Roberto Tamassia (John Wiley & Sons, Inc. 2002, ISBN 0-471-38365-1). Zie de webpagina bij het boek en de lijst van Jan Jongejan voor tekstcorrecties.

Elk van de 14 hoofdstukken wordt afgesloten met een groot aantal opgaven. Er zijn drie soorten opgaven: reinforcement exercises, creativity exercises en implementation projects. In de cursus Algoritmen en Datastructuren wordt ongeveer 2/3 van de inhoud van het boek behandeld.

Cursusopzet

Per week is er 2 x 2 uur hoorcollege en 2 uur werkcollege. Vanaf december is er tevens 2 uur verroosterd prakticum. Zie verder het rooster.
In het prakticum wordt gewerkt met JDSL, de Data Structures Library in Java. Zie de webpagina bij het boek.
Het hoorcollege wordt gegeven aan de hand van presentaties die door de auteurs van het cursusboek ontwikkeld zijn. Afdrukken van de presentaties zijn beschikbaar op de webpagina bij het boek.
Tijdens het werkcollege wordt gewerkt aan de opgaven. Hieronder is per week aangegeven welke opgaven aan de orde zijn.
Het prakticum bestaat uit twee opgaven: zie het weekrooster hieronder.

Toetsing

Het eindcijfer is het gewogen gemiddelde van het prakticum (25 %, zijnde 10 % voor de eerste opgave en 15 % voor de tweede) en het tentamen (75 %). Het prakticumresultaat moet wel voldoende (dwz. minimaal 5,5) zijn! Prakticumresultaten van eerdere jaren (2002, 2003 of 2004) zijn geldig. Raadpleeg in voorkomende gevallen de docent om zeker te weten dat een eerder prakticumresultaat geregistreerd is.

Weekrooster

Week 1 (maandag 14 november 2005 - vrijdag 18 november 2005)

Chapter 1: Algorithm Analysis (pseudocode, RAM model, O-notation, amortization). Niet behandeld van Chapter 1: 1.6.
Chapter 2: Basic Data Structures (stacks, queues, vectors, lists, sequences, trees, priority queues, heaps, dictionaries, hash tables). Niet behandeld van Chapter 2: 2.4 p. 109-111 (bottom-up heap construction), 2.5.6 (universal hashing), 2.6.
Opgaven:

Week 2 (maandag 21 november 2005 - vrijdag 25 november 2005)

Chapter 3: Search Trees and Skip Lists (binary search trees, AVL trees, (2,4) trees, splay trees, skip lists, locators). Niet behandeld van Chapter 3: 3.3.3 (red-black trees), 3.4.2 (amortized analysis of splaying), 3.6
Opgaven:

Week 3 (maandag 28 november 2005 - vrijdag 2 december 2005)

Chapter 4: Sorting, Sets, and Selection (mergesort, quicksort, bucket sort, radix sort, lower bound for sorting by comparison, the Set ADT, selection). Niet behandeld van Chapter 4: 4.2.2 (partititions with union-find operations), 4.2.3 (a tree-based partition implementation), 4.8.
Chapter 5: Fundamental Techniques (5.1: greedy method; 5.2: divide-and-conquer).

Opmerking: de `master method' voor het oplossen van recurrente vergelijkingen ivm. divide-and-conquer-algoritmen (5.2, p. 268) is in eenvoudiger vorm al behandeld bij de cursus Discrete Structuren. Zie het boek Discrete Mathematics van Ross en Wright, p. 241. Niet behandeld van Chapter 5: 5.2.3.
Opgaven:

De eerste prakticumopdracht is beschikbaar: zie de Nestorpagina van dit vak. Deadline vrijdag 16 december 2005, 17 uur.

Week 4 (maandag 5 december 2005 - vrijdag 9 decvember 2005)

Chapter 5: Fundamental Techniques (5.3: dynamic programming).
Chapter 6: Graphs (Graph ADT, edge list structure, adjacency list structure, adjacency matrix structure, depth-first search, breadth-first search, biconnectivity, gerichte grafen, DAGs, sterke connectiviteit, transitieve afsluiting, topologische ordening)
Opgaven:

Week 5 (maandag 12 december 2005 - vrijdag 16 december 2005)

Chapter 7: Weighted Graphs (kortste-pad algoritmen, minimale opspannende boom). Niet behandeld van Chapter 7: 7.2.2, 7.4.

Chapter 8: Network Flow and Matching (algoritme van Ford-Fulkerson, bipartite matching). Niet behandeld van Chapter 8: 8.2.4, 8.4, 8.5.
Opgaven:

Vrijdag 16 december 2005, 17 uur: deadline prakticumopdracht 1.

De tweede prakticumopdracht is beschikbaar: zie de Nestorpagina van dit vak. Deadline vrijdag 20 januari 2006, 17 uur.

Week 6 (maandag 19 december 2005 - vrijdag 23 december 2005)

NB: het hoorcollege van vrijdag 23 december vervalt.

Chapter 9: Text Processing (Tries, suffix tries, text compression, Huffman coding). Niet behandeld van Chapter 9: 9.1, 9.4, 9.5.
Opgaven:

Week 7 (maandag 9 januari 2006 - vrijdag 13 januari 2006)

Chapter 10: Number Theory and Cryptography (Algoritme van Euclides, machtsverheffen modulo n, testen op priemgetal-zijn, public-key cryptosystemen, fast Fourier transform, vermenigvuldigen van grote getallen). Niet behandeld van Chapter 10: 10.3, 10.5.
Aanvulling op sectie 10.1.6: in 2002 is door Manindra Agrawal, Neeraj Kayal en Nitin Saxena (Kanpur, India) een polynomiaal algoritme ontwikkeld dat nagaat of een gegeven getal priem is of niet. Referentie: Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160(2): 781-793 (2004). Zie ook een recentere versie van dit artikel.
Opgaven:

Week 8 (maandag 16 januari 2006 - vrijdag 20 januari 2006)

Deze week het laatste college op dinsdag 17 januari, dus vrijdag 20 januari geen college; er is deze week ook geen werkcollege.

Chapter 13: NP-completeness (complexity classes P and NP, NP-hardness, NP-completeness, examples). Niet behandeld: 13.4, 13.5, 13.6.

Vrijdag 20 januari 2006, 17 uur: deadline prakticumopdracht 2.

Week 9 (maandag 23 januari 2006 - vrijdag 27 januari 2006)

Week 10 (maandag 30 januari 2006 - vrijdag 3 februari 2006)

Week 11 (maandag 6 februari 2006 - vrijdag 10 februari 2006)

Tentamen: vrijdag 10 februari 2006, 14-17 uur, Examenhal
Bekijk als voorbeelden de tentamens van januari 2003 en februari 2005.