CS301 Complexity of Algorithms
Academic Aims
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.
Learning Outcomes
Students will learn to analyse the intrinsic difficulty of various computational challenges, and how to specify useful variations that may be more tractable.
Content
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.
