Syllabus 2007/2008 EDA110

Syllabus academic year 2007/2008

ALGORITHM THEORY

EDA110

Higher education credits: 6. Grading scale: TH. Level: A (Second level). Language of instruction: The course will be given in English. Optional for: D4, D4ps, E4ps, F4, F4tvb, L4, Pi3sbs. Course coordinator: Rolf Karlsson, Rolf.Karlsson@cs.lth.se, Inst f datavetenskap. Prerequisites: EDA027 Algorithms and Data Structures, FMA410 Calculus in One Variable and FMA420/425 Linear Algebra. Assessment: The final grade is based on a written examination and on 5 assignments. Home page: http://www.cs.lth.se/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