Entry requirements

Mathematics 30 ECTS credits and Computer Science 22.5 ECTS credits including Computer Programming, second course or the equivalent.

Learning outcomes

In order to pass, the student must be able to

• analyse the runtime performance of a (simple) algorithm/program in terms of the size of its inputs, and this in the average, best, and worst cases.
• answer evaluation questions such as the following: If the inputs double in size, will the runtime be the same, doubled, quadrupled, squared, or what? Which algorithm/program should one choose among several alternatives for the same specification? Which data structure should one choose when implementing an algorithm, considering its basic operations (add, modify, delete, find, order) on its data? Does it make a difference in runtime (for large inputs) if one replaces a part of an algorithm/program by a faster alternative?
• state in a precise way the assumptions underlying such a runtime performance analysis.
• know (and analyse) the runtime performance of the basic operations (add, modify, delete, find, order) for some of the most common (simple) data structures (lists, arrays, first-in first-out queues, priority queues, stacks, trees, heaps).
• explain the trade-off of using a so-called greedy algorithm (that makes opportunistic choices without any sense of regret) for an optimisation problem where the expected runtime performance is very bad for the typically occurring size of the inputs.

Content

Mathematical foundations: asymptotic notation, summations, recurrence relations.

Data structures: stacks, first-in first-out queues, trees, heaps, priority queues.

Searching: binary search trees, balanced search trees, hash tables.

Sorting.

Graph algorithms (simple ones).

Greedy algorithms.

Implementation in an imperative (possibly object-oriented) programming language.

Instruction

Lectures, lessons and compulsory assignments.

Assessment

Written exam (4.5 credits) and compulsory assignments (3 credits).