(Created 2008-07-17.)

ALGORITHM THEORY | EDA110 |

**Aim**

To give a deeper knowledge of the design and analysis of efficient algorithms and give training in algorithmic problem solving

*Knowledge and understanding*

For a passing grade the student must

- have thorough knowledge of properties and usefulness of presented data structures and problem solving techniques
- understand what is a practically efficient algorithm for large problems

*Skills and abilities*

For a passing grade the student must

- be able to analyse algorithms with respect to time and space complexity
- be able to formulate and solve recurrences
- be able to apply the given techniques for solving problems
- have increased ability to develop efficient algorithms for practically relevant problems

**Contents**

Methods for solving recurrences. Order statistics. Red-black trees. Augmenting data structures. Dynamic programming. Greedy algorithms. Shortest paths. Computational geometry. Maximum flow. Sorting networks. String matching.

**Literature**

Cormen T, Leiserson C, Rivest R & Stein C: Introduction to Algorithms. Second Ed. McGraw-Hill & MIT Press 2001. ISBN: 0-262-53196-8