|
|
|||||||||||||||||
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 |
|
|
|