  Cursuscode   INFOAL 
   
     
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 datastructures using advanced proof and analysis methods.
3. Implement existing and newlydesigned algorithms in an efficient manner in C#.
4. Apply algorithm design and analysis techniques to novel problems and contexts.
5. Define and understand basic concepts in complexity and graph theory.


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:
 Divideandconquer 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
 Averagecase 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
 NPcompleteness and complexity 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.
Tests:
 two exams
 six practicals
Each of the two exams counts for 50 percent of your final grade. By correctly solving 5 or 6 practicals, you can obtain 0.5 or 1 bonus point towards your final grade. You need at least 4 correctly solved practicals to pass this course.
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 reexamination. In order to do so you need either: a grade for both exams with an average of at least 5.50 and at least two correctly solved practicals; or, a grade for at least one exam and at least three correctly solved practicals.
For the reexamination, you have four choices, of which you may choose only one: do one extra practical, do two extra practicals, do the reexam, or do the reexam and one extra practical.
The reexam covers the material of the whole course. Your grade for the reexam replaces the grade for your lowest or missing exam.
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:
Lectures
Tutorial sessions
Practicals





   

 
 