CS301 15 CATS (7.5 ECTS) Term 1

Availability

Core - DM. Option - CS and Mathematics

Prerequisites

CS259 and CS260 are recommended.

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.

Books

There is no single textbook used in this module. Handouts will be made available online on the module web page.

Assessment

Three-hour examination (100%)

Teaching

30 one-hour lectures, 9 Seminars