To develop knowledge and skills in constructing and analyzing algorithms and data structures, to study advanced algorithmic solutions for the problems on sets, graphs, arithmetic, network and geometry, and to investigate the computational complexity of different problems.

After the course the student should be able to

• demonstrate knowledge of the disciplinary foundation and of proven experience in the design and analysis ofalgorithms and data structures

• demonstrate the ability to construct, analyze and critically evaluate various algorithmic solutionswith respect to correctness, efficiency, and reliability

• demonstrate the ability to identify, formulate, and mangeproblems of high complexity by develop computer program that use computer resources efficiently

• show knowledge of mathematical tools for analyzing algorithms

• demonstrate the ability to plan and use appropriate methods to undertake advanced tasks within predetermined parameters

• demonstrate theability to model, predict and evaluate the events even with limited information

Algorithm analysis: Correctness and efficiency, amortized and competitive analysis
Construction principles: Dynamic programming, approximation, augmenting data structures, randomized, dynamic, parallel,and on-line algorithms.
Computational complexity: Efficiency measures, upper and lower bounds, problem reduction technique, complexity classes including P, NP, and NP-complete problems.

Lectures. During the course there could be homework assignments that render bonus points on the written exam that follows directly after the course has been given.

The credits for this course cannot be combined with the credits forSMD 073, SMD087, SMD141, och SMD160.