Course Catalog 2009-2010 Basic Basic Pori International Postgraduate Open University |Degrees|     |Study blocks|     |Courses|

Person responsible

Henri Hansen, Antti Valmari

Implementations

	Lecture times and places	Target group recommended to
Implementation 1	Per 4, 5 : Thursday 14 - 17, TB111	3.-n. vuosikurssi International Students

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

Understanding and analyzing correctness and efficiency of algorithms. Understanding proofs of correctness, understanding the principles of simple algorithms. Use of 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

Correspondence of content

More precise information per implementation

	Description	Methods of instruction	Implementation
Implementation 1

Last modified	06.05.2009
Modifier	Henri Hansen