(Created 2010-07-25.)

ALGORITHM THEORY | EDAN05 |

**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. Fibonacci heaps. Amortized analysis. van Emde Boas-trees. Dynamic programming. Computational geometry. Sorting networks. String matching. A compulsory project.

**Literature**

Cormen T, Leiserson C, Rivest R & Stein C: Introduction to Algorithms. Third Ed. MIT Press 2009. ISBN: 978-0-262-53305-8

**Code: **0109.
**Name: **Algorithm Theory.

**Higher education credits: ** 6.
**Grading scale: **TH.
**Assessment:** Written examination. The final grade is based on the result of the written examination and on 5 assignments.

**Code: **0209.
**Name: **Project.

**Higher education credits: ** 1,5.
**Grading scale: **UG.
**Assessment:** For a final grade on the course the compulsory project work must have been completed.