Switch to English
Cursus: INFOAL
Cursus informatie
Studiepunten (EC)7,5
After this course, students will be able to independently design, analyze, and implement algorithms.

The learning outcomes of this courses are:
1. Design efficient algorithms for computational problems using fundamental design techniques.
2. Analyze the running time and correctness of algorithms and data-structures using advanced proof and analysis methods.
3. Implement existing and newly-designed algorithms in an efficient manner in C#.
4. Apply algorithm design and analysis techniques to novel problems and contexts.
5. Understand and apply basic concepts in complexity and graph theory.

Entry requirements:
The course requires knowledge of the C# programming language, as taught in Imperatief Programmeren (INFOIMP), for the practicals. Moreover, we assume basic knowledge on data structures and the running time analysis of algorithms, as taught in Datastructuren (INFODS) or Datastructuren en Algoritmen voor KI (INFOB2DAKI). Students who have not followed those courses, but have a strong mathematical background and some programming experience, may also succeed with some extra work. If you are unsure whether your background fits with the entry requirements of this course, please contact us.

- two exams
- two hand-in exercises
- four practicals

Each of the two exams counts for 35 percent of your final grade. Each of the two hand-in exercises counts for 5 percent of your final grade. By correctly solving a practical, you earn 0.5 points for your final grade (so a maximum of 2 points). To pass the course and get a grade, you need to have at least two correctly solved practicals and a grade for both exams.

If you do not satisfy the conditions to get a grade or your unrounded final grade is at least a 4 and less than a 5.50, then you might qualify for re-examination. In order to do so you need either: a grade for both exams with an average of at least 4 and at least one correctly solved practicals; or, a grade of at least 4 for one exam and at least two correctly solved practicals.

For the re-examination, you have four choices, of which you may choose only one: do one extra practical, do two extra practicals, do the re-exam, or do the re-exam and one extra practical.

The re-exam covers the material of the whole course. Your grade for the re-exam replaces the grade for your lowest or missing exam.
In many practical applications, the speed of software is very important. Often this means that, besides fast computers and smart compilers, we need efficient algorithms. To design and develop such efficient algorithms, you will study several techniques and topics in Algoritmiek.

The course emphasizes both fundamental aspects (running time analysis and correctness proofs) and practical aspects (implementation challenges) of algorithmics. The lectures provide a solid foundation to this. You will study time analysis and proofs in the tutorial sessions, while you can work on implementation challenges in the practicals.

The main topics of the course are:
- Divide-and-conquer algorithm design technique
- Dynamic programming algorithm design technique and optimal substructure property
- Greedy algorithm design technique and greedy choice property
- Analysis of recursive algorithms and solving recurrences
- Amortized analysis
- Randomized algorithms and analysis
- Average-case analysis
- Graphs and graph representations
- Graph exploration
- Shortest path algorithms
- Minimum Spanning Tree algorithms
- Maximum Matching, Maximum Flow and Minimum Cut algorithms
- String matching algorithms
- Dynamic search trees
- NP-completeness and complexity theory

Material (recommended):
Book: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, third edition, MIT Press / McGraw Hill, 2009. The second and fourth edition are mostly equivalent and can also be used.

Instructional formats:
Tutorial sessions

The exams, practicals, and tutorial exercises of this course are in English. The lectures are in Dutch or English, depending on the lecturer.
Switch to English