Course Catalog 2011-2012
Postgraduate

Basic Pori International Postgraduate Open University

|Degrees|     |Study blocks|     |Courses|    

Course Catalog 2011-2012

OHJ-2156 Analysis of Algorithms, 4 cr

Person responsible

Timo Kellomäki, Henri Hansen, Timo Aho, Antti Valmari

Requirements

Tentti

Principles and baselines related to teaching and learning

We learn by doing: We analyze many algorithms both during lectures and during exercises. Independent implementation (i.e. coding) of algorithms for simulating and testing the ideas presented in the course is encouraged.

Learning outcomes

The student is able to apply logic and other methods of analysis to assess the correctness and efficiency of simple algorithms. The student is able to read and comprehend proofs of correctness. The student has the ability to generalize from the principles of simple algorithms. The student is able to analyse resource consumption using the Theta-notation.

Content

Content Core content Complementary knowledge Specialist knowledge
1. Simple loop structures and their invariants with proofs.  Extensive use of state propositions. More complicated invariants  Difficult proofs of correctness, underlying mathematical structures. 
2. Analysis of time consumption of simple iterative programs. Elimination of tail recursion, simple recursive algorithms and recurrences, elements of amortized analysis.  Master Theorem, amortized analysis using potential functions, complicated iterative algoritms.  Complexity issues, exponential algorithms. 
3. Properties of basic algorithms: Sorting, Graph algorithms (BFS, DFS etc), the selection of a data structure from the point of view of efficiency, both memory and time.  More advanced algorithms: greedy algorithms, dynamic programming, high level implementation details, amortized costs of data structure operations as part of an algorithm.   Difficult algorithms and advanced proofs.  

Evaluation criteria for the course

Grading is based on exam. Questions are graded based how correct results are gained by using clearly presented reasoning.

Assessment scale:

Numerical evaluation scale (1-5) will be used on the course

Study material

Type Name Author ISBN URL Edition, availability, ... Examination material Language
Book   Introduction to Algorithms, 2nd edition   Cormen et. al            English  

Prerequisites

Course Mandatory/Advisable Description
MAT-20501 Todennäköisyyslaskenta Advisable    
OHJ-2010 Tietorakenteiden käyttö Mandatory    
OHJ-2100 Ohjelmistotieteen perustyökaluja Mandatory    

Prerequisite relations (Requires logging in to POP)



Correspondence of content

Course Corresponds course  Description 
OHJ-2156 Analysis of Algorithms, 4 cr OHJ-2150 Analysis of Algorithms, 4 cr  

Last modified11.08.2012