Data on the course

Show instruction and examinations
814602S Design and Analysis of Computer Algorithms, 5 ECTS cr 
Code 814602S  Validity 01.08.2011 - 31.10.2012
Name Design and Analysis of Computer Algorithms  Abbreviation Design and Anal 
Scope5 ECTS cr   
TypeAdvanced Studies Discipline3259 Information Processing Science 
TypeCourse   
  Grading1 - 5, pass, fail 
 
   
Unit  

Teachers
Name
Juha Kortelainen 

Description
ECTS Credits 

5 ECTS credits/134 hours of work

 
Language of instruction 

English

 
Timing 

1 st – 2 nd year of Master’s studies, autumn semester, period 1

 

 
Learning outcomes 

After completing the course, the student understands and internalises the phases that are needed when designing and analysing a computer algorithm. They are able to choose an appropriate design technique for a given simple problem, apply the chosen technique and specify the respective algorithm. Moreover, the student is capable of analysing the time and space complexity of the algorithm as well as its simplicity and generality. Finally they can implement the algorithm with a programming language.

 
Contents 

1.                Mathematical background

2.                Asymptotic analysis

3.                Divide and conquer algorithms

4.                Greedy algorithms

5.                Dynamic programming

6.                Graph algorithms

7.                NP-hard problems

8.                Linear programming

9.                Approximation algorithms

10.              Randomised algorithms

 
Mode of delivery 

Face-to-face teaching

 

 
Learning activities and teaching methods 

Lectures 35h, exercises 35h, autonomous work 64h.

 
Target group 

 

 
Prerequisites and co-requisites 

Basic knowledge in discrete mathematics, data structures and algorithms, rudimentary skills in programming.

 
Recommended optional programme components 

 

 
Recommended or required reading 

1.  Lecture notes

2.  Lecture slides

3.  Exercise materials

4.  Text book: Steven S. Skiena: The Algorithm Design Manual, 2nd ed., Springer-Verlag, London, 2008.

 

 
Assessment methods and criteria 

Either two partial exams or a single final exam.

 

 
Grading 

 1–5

 
Person responsible 

  Juha Kortelainen

 
Working life cooperation 

No

 


Current and future instruction
No instruction in WebOodi

Future examinations
No examinations in WebOodi