apply these algorithms or a given pseudo code algorithm in order to solve a given problem;

carry out simple asymptotic analyses of algorithms involving sequence, selection, and iteration, and identify and compare simple properties of these algorithms;

describe the algorithm design principles of divide-and-conquer, greedy method, and dynamic programming and distinguish the differences between these principles;

apply the studied algorithms that illustrate these design principles;

apply the studied design principles to produce algorithmic solutions to a given problem;

explain and illustrate the distinction between different classes of problems, in particular, polynomial time and exponential time solvable problems.

1 Introduction  (8 lectures)

Definition of an algorithm, counting elementary operations during execution, worst-case analysis of running time and storage requirements - on several examples of simple algorithms. Design of pseudo code algorithms.

2 Complexity Issues (6 lectures)

Asymptotics and ``order of'''' notation for complexity. Comparison of polynomial time and exponential time complexities and examples of algorithms with such complexities. Brief introduction of the notion of computable and non-computable functions.

3 Review of Graphs structures and their representation (4 lectures)

Directed and Undirected graphs; trees; representation by adjacency matrices and incid ence lists, graph and tree traversals.

4 Algorithm Design Techniques (18 lectures)

Review of the standard algorithm design paradigms commonly used in Computer Science together with typical example problems solved by these.

a)     Overview: why a range of design methods is needed.

b)     Divide-and-Conquer algorithms: general overview of approach; run-time analysis of simple Divide-and-Conquer methods via solution of recurrence relations.

c)     Dynamic Programming: differences from Divide-and-Conquer; general overview; necessity for iterative implementation.

d)     Greedy Method: concept of optimisation problem and the distinction between ''exact'' and ''approximate'' solution a lgorithms.

Lecture -

Tutorial -

Laboratory Work -