Course syllabus

# Algoritmer, datastrukturer och komplexitet

Algorithms, Data Structures and Complexity

## EDAF05, 5 credits, G2 (First Cycle)

## General Information

## Aim

## Learning outcomes

## Contents

## Examination details

## Admission

Admission requirements:## Reading list

## Contact and other information

Algorithms, Data Structures and Complexity

Valid for: 2017/18

Decided by: PLED C/D

Date of Decision: 2017-04-03

Main field: Technology.

Compulsory for: D2, Pi4-pv

Elective for: C4-pv, E4, F4, F4-pv

Language of instruction: The course will be given in English on demand

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, particularly graph algorithms. The course will also give the students knowledge of techniques for analysing algorithms with respect to performance.

Knowledge and understanding

For a passing grade the student must

- be able to describe data structures which can be used to represent graphs
- be able to describe a number of different problem solving strategies, such as divide and conquer and greedy algorithms
- master a number of techniques for analysing algorithm performance
- be familiar with concepts such as lower bounds, complexity classes and undecidable problems

Competences and skills

For a passing grade the student must

- from a given problem, be able to identify algorithms and data structures which can be used to implement a solution
- be able to implement the data structures included in the course in an object-oriented language
- be able to apply different problem solving strategies on new problems
- be able to apply techniques for analysing the time complexity of algorithms and be able to use the notations for asymptotic time complexity

Judgement and approach

For a passing grade the student must

- be able to evaluate proposed solutions and data representations for given problems with respect to suitability and efficiency
- understand that there are problems for which it is unknown whether or not efficient algorithms exist

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.

Grading scale: TH - (U,3,4,5) - (Fail, Three, Four, Five)

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.

The examiner, in consultation with Disability Support Services, may deviate from the regular form of examination in order to provide a permanently disabled student with a form of examination equivalent to that of a student without a disability.

Parts

Code: 0109. Name: Written Examination.

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.

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.

- A first course in object-oriented programming. Completed the compulsory course items from EDAA01 or passed the written exam in this course

The number of participants is limited to: No

The course overlaps following course/s: EDA027, EDA690

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

Course coordinator: Professor Thore Husfeldt, Thore.Husfeldt@cs.lth.se

Course homepage: http://cs.lth.se/edaf05