Design and Analysis of Algorithms

Lectures:
36 h

Recommended for
Graduate students in computer science.

The course was last given:
Fall 1998

Goals
The primary aim of this course is to increase the student's skills in algorithmic problem solving. To this end, the course presents several techniques for design and analysis of algorithms. In addition, the course gives knowledge about important subareas within algorithm and complexity theory.

Prerequisites
An introductory course on data structures and algorithms, e.g., TDDB 57 Datastrukturer och Algoritmer. That is, students are expected to be familiar with asymptotic notation, basic data structures such as lists, stacks, queues, trees, etc., and algorithms for fundamental problems such as searching, sorting, etc.

Organization
The theoretical content of the course is presented during the lectures. Since algorithmic problem solving is an art as much as a science, the seminars and homework exercises are intended to practice design and analysis of algorithms.

Contents
Techniques for design and analysis of algorithms, and for determining lower bounds on time complexity, fast Fourier transforms, randomized algorithms, string matching algorithms, geometric algorithms, NP completeness, approximation algorithms, parallel algorithms, etc.

Literature
Introduction to Algorithms by Cormen, T.H., Leiserson, C.E., and Rivest, R.L., MIT Press.

Teachers
Peter Jonsson.

Examiner
Peter Jonsson.

Schedule
August - October 1999.

Examination
One final written exam.

Credit
3.5 credits.

Comments:
The course will be given in Swedish. The exam may be written in English.

Page responsible: Director of Graduate Studies