CS301 15 CATS (7.5 ECTS) Term 1
Core - DM. Option - CS and Mathematics
CS259 and CS260 are recommended.
To learn the notions of the complexity of algorithms and the complexity of computational problems. To learn various models of computation. To understand what makes some computational problems harder than others. To understand how to deal with hard/intractable problems.
Students will learn to analyse the intrinsic difficulty of various computational challenges, and how to specify useful variations that may be more tractable.
In this module, the notions of complexity of algorithms and of computational problems will be studied. Students will learn how to design efficient algorithms, what makes an algorithm efficient, and what makes a problem hard (so that it has no fast algorithm).
Various models of computation will be discussed, in particular, the models of classical deterministic computations, non-deterministic computations, and also of randomized computations, approximation algorithms, parallel computations, and on-line computations will be presented.
Some part of the module will be devoted to the discussion of what makes some computational problems harder than others, how to classify well-defined computational problems into levels of hardness, and how to deal with problems that are hard and intractable.
There is no single textbook used in this module. Handouts will be made available online on the module web page.
Three-hour examination (100%)
30 one-hour lectures, 9 Seminars