Volledige Samenvatting Classic Computer Science Algortihms

1



Samenvatting CCSA
1: Zoeken en sorteren............................................................................................................................2
2: Gelinkte lijsten....................................................................................................................................8
2.1: Stapels...........................................................................................................................................16
2.2: Wachtrijen.....................................................................................................................................22
3: Hashtabellen.....................................................................................................................................26
4: Bomen..............................................................................................................................................32
5: Grafen...............................................................................................................................................44
6: Zoekalgoritmes.................................................................................................................................61
8: Machinaal leren................................................................................................................................75
9: Complexiteitstheorie........................................................................................................................82
Extra:....................................................................................................................................................85


Notities examen:

 Pseudocodes: pas x toe op deze oefening  zelf pseudocode schrijven
o Of: wijzig x in pseudocode y zodat …
 Bewijzen skip
 Python: zoals dodona: nen tekst

, 2



1: Zoeken en sorteren
Waarom sorteren?
 Effect van sorteren  sneller zoeken
 Vb woordenboek: probeer maar is een woord te zoeken als ze niet gesorteerd zijn.

Lineair / sequentieel zoeken: algoritme
 = elk element afgaan om te zoeken
 Tijdscomplexiteit is lineair, dus tijdscomplexiteit van orde n
o T(n) = O(n)

Pseudocode – python




Binair zoeken
 Eerst de array sorteren
 Dan een element beschouwen (het middelste bv)
o Indien dit element kleiner is dan de gezochte waarde, zoek dan rechts verder
o Indien dit element groter is dan de gezochte waarde, zoek dan links verder
 Kan iteratief / recursief
 Tijdscomplexiteit is logaritmisch: telkens halveer je de lijst
o T(n) = O(²log(n))
 Tijdscomplexiteit manueel: hoeveel wordt dit uitgevoerd ‘rij[m] < zoekItem’
o Bij n = 1  0 keer
o Bij n = 2  1 keer
o Bij n = 4  2 keer
o …

, 3


Pseudocode iteratief – python




Pseudocode recursief – python

, 4


Tijdscomplexiteit (=analyse v/d uitvoeringstijd)
Karakteriseert het gedrag v/d uitvoeringstijd voor grote waarden, typisch gedrag is:

 Lineaire functie: T(n) = n
o Invoer verdubbelt  uitvoeringstijd verdubbelt
 Kwadratische functie: T(n) = n²
o Invoer verdubbelt  uitvoeringstijd x 4
 Exponentiële functie: T(n) = 2n
o Invoer + 1  uitvoeringstijd x 2
 Logaritmische functie: T(n) = log(n)
o Invoer verdubbelt  uitvoeringstijd + constante

Hoe bepalen?

 Bij zoekalgoritmen wordt dit bepaalt door het aantal vergelijkingen dat worden uitgevoerd. Zie
bv bij binair zoeken hierboven

Sorteren door selectie
 Basisidee:
o zoek het grootste element en plaats het achteraan
o Doe zo voort
 Complexiteitsanalyse: hoeveel keer wordt a[j] > max uitgevoerd?
o For i  n keer
o For j  n – 1 keer
o  (n(n-1)) / 2
o  T(n) = O(n²)
 Algemeen:
o 0 + 1 + 2 + … + n-1 = ! n (n-1) / 2 !

pseudocode – python (kan ook omgekeerd: buitenste for van klein nr groot en dan telkens de min
bijhouden etc) + examen: van groot nr klein, met mengen / tussenvoegen / selection

 Groot nr klein is gwn < of > switchen