Syllabus 2010/2011 EDAN05

Syllabus academic year 2010/2011
(Created 2010-07-25.)

ALGORITHM THEORY

EDAN05

Credits: 7,5. Grading scale: TH. Cycle: A (Second Cycle). Main field: Technology. Language of instruction: The course will be given in English. EDAN05 overlaps following cours/es: EDA110. Optional for: D4, D4pv, E4, E4pv, F4, F4bs, F4pv, Pi4, Pi4pv. Course coordinator: Rolf Karlsson, Rolf.Karlsson@cs.lth.se, Dept of Computer Science. 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://cs.lth.se/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

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