Syllabus academic year 2011/2012
(Created 2011-09-01.)
ALGORITHMS, DATA STRUCTURES AND COMPLEXITYEDAF05
Credits: 5. Grading scale: TH. Cycle: G2 (First Cycle). Main field: Technology. Language of instruction: The course will be given in Swedish. EDAF05 overlaps following cours/es: EDA027 and EDA690. Compulsory for: D2, Pi4pv. Optional for: F4, F4pv, F4tf, Pi4. Course coordinator: Associate prof. Thore Husfeldt, Thore.Husfeldt@cs.lth.se, Computer Science. Prerequisites: A first course in object-oriented programming. Completed the compulsory course items from EDAA01 or passed the written exam in this course. Assessment: Written exam. The final grade of the course is based on the result of the written exam. For a passing grade of the course the compulsory course items must be completed. Parts: 2. Home page: http://cs.lth.se/edaf05.

Aim
Algorithms and data structures are fundamental in computer science. Data structures are used to model reality and the choice of data structures affects the efficiency of algorithms. One aim with this course is to give the students knowledge of advanced data structures for some of the abstract models included in previous courses and also of a number of data structures used to represent further models, such as graphs. Another aim is to give improved knowledge of algorithms, particularily graph algorithms. The course will also give the students knowledge of techniques for analysing algorithms with resspect to performance.

Knowledge and understanding
For a passing grade the student must

Skills and abilities
For a passing grade the student must

Judgement and approach
For a passing grade the student must

Contents
Graphs and graph algorithms. Data structures for graphs. Problem solving strategies such as divide and conquer, greedy algorithms and brute force. Techniques for analysing the time complexity of algorithms. Introduction to the complexity classes P and NP, computability and the Church-Turing thesis.

Literature
Kleinberg J, Tardos E: Algorithm Design. Addison-Wesley 2005.
ISBN: 0321295358

Parts

Code: 0109. Name: Written Examination.
Higher education credits: 3. Grading scale: TH. Assessment: The final grade of the course is based on the result of the written exam.

Code: 0209. Name: Compulsory Course Items.
Higher education credits: 2. Grading scale: UG. Assessment: For a passing grade, the compulsory course items must be completed. Contents: Laboratory work and a hand-in assignment.