Course syllabus

## EDAN55, 7,5 credits, A (Second Cycle)

Valid for: 2017/18
Decided by: PLED C/D
Date of Decision: 2017-04-03

## General Information

Elective for: C5-pv, D4-pv, E4-pv, F4, F4-pv, F4-bs, Pi4-bs, Pi4-pv
Language of instruction: The course will be given in English

## Aim

Algorithms play an important role in computer science and many other science and engineering disciplines. Part of this knowledge has found its way into many science and engineering undergraduate curricula. This advanced algorithms course covers a number of modern topics outside of this basic curriculum.

First, randomization plays an important role in all aspects of algorithms and data structures. This includes basic solutions, such as hash tables and quick sort, that are part of standard data structure libraries used by every programmer. A large part of the internet, from routing tables to massive-scale companies such as Google, are completely reliant on randomization. But even though these ideas are often both simple, very efficient, and highly practical, they are typically not included in a basic course because of lacking prerequisites from discrete probability theory.

Second, a large number of problems are known to be computationally intractable, in the strict sense of being hard for complexity classes like NP or #P. However, this problems still need to be solved. The course presents design and analysis techniques outside of the basic algorithmic undergraduate curriculum for attacking these problems, such as approximation algorithms, exponential time algorithms, parameterized complexity, heuristics and randomized solutions.

Third, many algorithmic solutions must be viewed in the face of massive data encountered today in many application areas, such as google-size databases and information-age science. As instance size grow to mega- and gigabytes, basic data structures and even storage models need to be reconsidered, and new questions arise. Often, randomization plays a central role in the solutions.

Many of these topics are active research questions and the course is at the cutting edge of algorithmic research with rich opportunities for thesis or beginning research work.

## Learning outcomes

Knowledge and understanding
For a passing grade the student must

• be informed about basic randomized algorithms and data structures
• recognize various computational paradigms for the solution or hard problems
• be informed about modern data structures for massive data sets
• be able to reason in various models of computation for massive data

Competences and skills
For a passing grade the student must

• be able to analyze a randomized algorithm using tools from discrete probability theory, with respect to both performance and correctness guarantees
• be able to analyze the approximation hardness of a computationally hard problem
• be able to implement and test a solution to computationally hard problem
• be able to implement and test an efficient data structure for a massive scale problem

Judgement and approach
For a passing grade the student must

• be able to suggest informed and well-reasoned solutions to computationally hard problems
• be able to select between probabilistic models for randomized computation
• be able to assess the viability of algorithmic solutions based on both experimental and formal analyses of their efficiency and soundness
• be able to evaluate the relevance of an algorithmic solution presented in the research literature

## Contents

Parameterized algorithms and complexity. Design, applications, and analysis of randomized algorithms; hash functions, randomized data structures, Markov chains and random walks, Chernoff bounds, method of conditional probability, the probabilistic method, balls and bins. Approximation algorithms. Models and data structures for massive data.

## Examination details

Grading scale: TH - (U,3,4,5) - (Fail, Three, Four, Five)
Assessment: The final grade of the course is based on the result of the written examination. For a passing grade the compulsory course items must also 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: 0112. Name: Written Examination.
Credits: 4,5. Grading scale: TH. Assessment: The final grade of the course is based on the result of the written examination. Contents: Written examination.
Code: 0212. Name: Compulsory Course Items.
Credits: 3. Grading scale: UG. Assessment: For a passing grade the laboratory work and the assignment must be completed. Contents: Laboratory work and an assignment.

• A passing grade in the course EDAA01 (Programming - Second Course) and completed compulsory course items or a passing grade in the written exam in EDAF05 (Algorithms, Data structures and Complexity) and FMS012/FMSF45 (Mathematical Statistics, Basic Course)

The number of participants is limited to: No

• Kleinberg J, Tardos E: Algorithm Design. Addison-Wesley, 2005, ISBN: 0321295358. Parts of this book has been used in the course EDAF05.
• Mitzenmacher M, Upfal E: Probability and Computing: Randomized Algorithms and Probabilistic Ananlysis. Cambridge University Press, 2005, ISBN: 0-521-83540-2.
• Hromkovic J: Algorithmics for Hard Problems. Springer, 2002, ISBN: 3-540-44134-4.
• Selected research papers.

## Contact and other information

Course coordinator: Professor Thore Husfeldt, Thore.Husfeldt@cs.lth.se
Course homepage: http://cs.lth.se/edan55