In dit college wordt de complexiteit van algoritmen bekeken: dit is het aantal elementaire stappen dat een algoritme nodig heeft om het onderhavige probleem op te lossen. We onderscheiden worst case, average case en best case complexiteit. Enkele te behandelen onderwerpen zijn: O-notatie, algoritmen voor selectie/sorteren, beslissingsbomen, adversary argument, optimaliteit, recurrente betrekkingen, polynoomevaluatie, graafproblemen. We zullen zien dat er voor veel problemen een polynominaal algoritme bestaat. Er zijn evenwel ook problemen (waaronder bijvoorbeeld het handelsreizigersprobleem) die echt moeilijk zijn: de NP-volledige problemen. Ook NP, NP-volledigheid en reducties zullen aan de orde komen.
Method: hoorcollege en werkgroep
Examination: schriftelijk
Prior knowledge: eerstejaarscolleges informatica
Literature: dictaat (reader) waarin ook opgaven zijn opgenomen
*Website: * http://www.liacs.nl/~graaf/COMP