Objectives and outcomes
Students analyse and apply the concepts of algorithm theory. Algorithms appear in almost every branch of computer science, in engineering, biology, etc. Every problem that appears in the scientific process and needs to be solved requires an algorithm that is able to find a solution based on the given data. Ability to critically analyse existing solutions and synthesise original solutions in the field of algorithms.
Lectures
Methods for designing algorithms: greedy algorithm (Huffman coding), dynamic programming (the longest common subsequence), matrix multiplication, transitive closure. Analysis of algorithms: recurrent methods, worst-case analysis, average case analysis (e.g. quicksort), amortised complexity. Algorithms in number theory: integer (the greatest common divisor, modular arithmetic), FFT, polynomial and integer arithmetic. Algorithms on graphs (graph traversal, the shortest distance, the spanning tree). Network flow algorithms. Word matching algorithms. Other algorithmic paradigms: parallel algorithms (Pointer Jumping, prefix sum, list ranking, sorting), distributed algorithms (Byzantine Agreement).
Practical work
A part of the course is dedicated to independent research work that includes writing a paper on the theory of algorithms.