Algorithms

Course goals

Na deze cursus is de student in staat om zelfstandig algoritmes te ontwerpen, analyseren en implementeren. De leerdoelen van deze cursus zijn:
1. Het ontwerpen van efficiënte algoritmen voor computationele problemen middels fundamentele ontwerptechnieken.
2. Het analyseren van de looptijd en correctheid van algoritmes en datastructuren middels geavanceerde bewijs- en analysemethoden.
3. Het implementeren van bestaande en nieuw-ontworpen algoritmes op efficiente wijze.
4. Het toepassen van algoritmische ontwerp- en analysetechnieken op nieuwe problemen en contexten.
5. Het begrijpen en toepassen van concepten uit computationele complexiteitstheorie en graaftheorie.


Toetsing

- twee tentamens
- vier practica
- meerdere mini-toetsen

Ieder van de twee tentamens telt voor 40 procent van je eindcijfer. Voor ieder correct practicum (zoals beoordeeld door PrairieLearn), verdien je 0.25 punten voor je eindcijfer, dus in totaal 10 procent. De mini-toetsen tellen voor totaal 10 procent van je eindcijfer. Om voor het vak een eindcijfer te krijgen, moet je wel tenminste twee correcte practica hebben en een cijfer voor beide tentamens.

Je kunt meedoen aan de aanvullende toetsing als: (1) je voldoet aan de vereisten om een cijfer te krijgen en je onafgeronde eindcijfer is tenminste een 4 en minder dan 5.50; of (2) je niet voldoet aan de vereisten om een cijfer te krijgen, maar (2a) je voor beide tentamens een cijfer hebt, met gemiddeld tenminste een 4, en tenminste een correct practicum, of (2b) je een cijfer hebt voor precies een van beide tentamens, dat tenminste een 4 is, en je hebt tenminste twee correcte practica.

De aanvullende toets bestaat uit een van vier opties, die je zelf mag kiezen: een extra practicum doen; twee extra practica doen; het hertentamen doen; het hertentamen en een extra practicum doen.

Het hertentamen gaat over de inhoud van de hele cursus. Het cijfer voor het hertentamen vervangt het laagste of missende cijfer van de deeltentamens.

Content

De snelheid van software is belangrijk in veel applicaties. Daar heb je niet alleen snelle computers en slimme compilers voor nodig, maar ook efficiënte algoritmes. In Algoritmiek leer je technieken om zulke efficiënte algoritmes te ontwerpen, analyseren en implementeren. Ook zie je verschillende problemen waar deze technieken hun toepassing vinden.

De cursus omvat zowel meer theoretische aspecten van het vak (analyse van looptijd en correctheid) als meer praktische aspecten (implementatie). De hoorcolleges geven je hiervoor een stevige basis. Je bestudeert en gebruikt de geleerde technieken voor bewijzen en analyse in de werkcolleges en werkt aan hun implementatie tijdens de practica.

De onderwerpen van deze cursus zijn:
- technieken om algoritmen te ontwerpen: divide-and-conquer, dynamisch programmeren (en het optimaliteitsprincipe), en greedy algoritmen (en de greedy choice property)
- analyse van verschillende soorten algoritmen: recursieve en gerandomiseerde algoritmen
- verschillende soorten van looptijdanalyse van algoritmen: worst-case, geamortizeerde en gemiddelde looptijd
- algoritmen voor problemen op netwerken en grafen: kortste paden, opspannende bomen, koppelingen, stromingen, snedes
- de representatie in een computer van netwerken en grafen
- algoritmen voor zoeken in teksten
- dynamische zoekbomen
- computationele complexiteit en NP-volledigheid

Additional information

De hoorcolleges zijn in het Nederlands of het Engels, naar gelang de docent. De opgaven van de tentamens, practica, mini-toetsen en werkcolleges zijn in het Engels.