Hier volgt een lijst met onderwerpen die men IN IEDER GEVAL voor het
tentamen Datastructuren (jaargang 2001-2002) moet kennen.
Het is puur bedoeld als service aan de studenten. Er kunnen geen
rechten aan worden ontleend.


Belangrijkste wijzigingen ten opzichte van vorig jaar:

  Wel tot de tentamenstof behoort:
      ZLW-compressie als toepassing van trie
      topologisch sorteren met als toepassing een activiteiten-netwerk
  Niet tot de tentamenstof behoort:
      external quicksort als toepassing van de SMM heap


DE LIJST:
=========

Legenda:
  #   : genoemd maar niet uitgewerkt -> globaal kennen
  rest: goed kennen


C++
    wat betreft declaraties & implementaties
    algoritmen mogen in preudo-code worden opgeschreven

Abstracte DataTypen (ADT)
    specificatie, representatie & implementatie

Lijsten, Stapels, Rijen  [Progmeth, Algoritmiek]

Bomen
    terminologie
    representaties
        binaire bomen, eerste kind-rechter broer, array representatie
    boomwandeling
        WLR (preorde) LWR (symmetrisch) LRW (postorde) (al dan niet recursief)
        niveau-orde   
    bedrade binaire bomen
    boomwandeling mbv linkomkering
    methode Morris (als toepassing van draden)       
    binaire zoekbomen
        toevoegen, verwijderen
    interne / externe padlengtes
    Union-Find  [Werkcollege, opgave 3.23]
        toepassing bij Kruskal
    compressie
        Huffman
	Ziv-Lempel-Welch (toepassing trie)
           [u weet wel, van de programmeeropdracht]
    zie ook onder 'Priority-queue' en 'Dictionary'
    
Priority-queue
    abstract, en de implementaties:
    triviaal: lijst (array, gelinkt)
    heap [Algoritmiek]
       top down en bottom up opbouwen heapstructuur
    symmetrische min-max heap
    links-hellende bomen (Ritsen)
    binomiaal bomen
    
Dictionary
    abstract, en de implementaties:
    # skip-lists
    # zelf-organiserend lijsten & bomen
    binaire zoekbomen
        # complexiteit
    AVL-bomen
        rotaties, toevoegen, verwijderen
        link met Fibonacci getallen
    B-bomen
        toevoegen, verwijderen
        complexiteit
        Rood-zwart bomen (als implementatie van B-bomen orde m=4)
    hash-methoden (zie onder)
    
Hashen
    perfect hashen
    met lijsten, buckets
    open adressering,
        lineair, dubbel, enz. hashen, 
	clustering (primair en secundair)
    ter plekke uitbreiden van hash-tabellen
    hash-functies
        
Grafen
    representaties
    wandelingen (DFS, BFS)
    algoritmen
        minimale opspannende boom: 
	   Prim
	        correctheid
	   Kruskal
        kortste paden: 
	   Dijkstra
	        complexiteit (met/zonder priority queue)
           Floyd (alle paren)
     topologisch sorteren
        correctheid
        activiteiten netwerk
           als toepassing van top.sort of DFS

Patroonherkenning
    Knuth-Morris-Pratt
    reguliere expressies en eindige automaten [uitgedeeld dictaat]
        omzetten expressie in (semantische) boom
        evaluatie (boom naar automaat)
	tekst zoeken