(Created 2009-08-11.)
 ALGORITHM THEORY EDAN05

Higher education credits: 7,5. Grading scale: TH. Level: A (Second level). Language of instruction: The course will be given in English. EDAN05 overlap following cours/es: EDA110 och EDA110. Optional for: D4, D4ps, E4, E4ps, F4, F4tvb, Pi4, Pi4sbs. Course coordinator: Rolf Karlsson, Rolf.Karlsson@cs.lth.se, Inst f datavetenskap. Prerequisites: EDAA01 Programming-Second course or EDA027 Algorithms and Data Structures. Also FMA420 Linear Algebra. Recommended prerequisits: FMA 410 Calculus in One Variable. Assessment: The final grade is based on a written examination and on 5 assignments. For a passing grade the project also has to be completed. Parts: 2. Home page: http://www.cs.lth.se/Education/LTH/.

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. A compulsory project.

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

Parts

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: TH. Assessment: For a final grade on the course the compulsory project work must have been completed.