• Course code:63546F
  • Credits:6
  • Semester: summer
  • Contents

In the first part of this two-part course, we will introduce a mathematical model to solve many problems in computer science, such as scheduling, network analysis, pathfinding problems in graphs, hierarchical clustering, parsing,... We will define an algebraic structure called a semiring and show its capability to solve such problems in diverse situations. As semirings allow for more general and joint solutions to various problems, while reducing the time complexity of existing algorithms, they are a very active research area in computer science and mathematics.

In the second part of the course we will learn the field of algorithm engineering which guiding principle is to bridge the gap between theory and practice. There are many well-known cases where classical theory of algorithms inadequately describes behavior of algorithm in practice such as simplex algorithm, quicksort, graph planarity, graph minor etc. Consequently it is of great importance to obtain good implementation and to experimentally examine the algorithm. During the course we will look at the algorithm engineering process and its phases: realistic models of computation, algorithm design, algorithm implementation, beyond worst-case analysis, experiments, generating realistic inputs, and creating algorithmic libraries.

  • Study programmes
  • Distribution of hours per semester
laboratory work
  • Professor
Teaching Assistant
Course Organiser