Design and Analysis of Algorithms
Koe
Vuosi | Lukukausi | Päivämäärä | Periodi | Kieli | Vastuuhenkilö |
---|---|---|---|---|---|
2016 | syksy | 07.09-19.10. | 1-1 | Englanti | Veli Mäkinen |
Luennot
Aika | Huone | Luennoija | Päivämäärä |
---|---|---|---|
Ke 14-16 | CK112 | Veli Mäkinen | 07.09.2016-19.10.2016 |
Harjoitusryhmät
Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|
Ke 10-12 | B119 | Topi Talvitie | 12.09.2016—21.10.2016 |
Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|
Ke 12-14 | B119 | Topi Talvitie | 12.09.2016—21.10.2016 |
Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|
Ke 16-18 | B119 | Daniel Valenzuela | 12.09.2016—21.10.2016 |
Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|
Pe 10-12 | B222 | Veli Mäkinen | 05.09.2016—14.10.2016 | Study group! |
Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|
Pe 12-14 | B222 | Daniel Valenzuela | 05.09.2016—14.10.2016 | Study group! |
Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|
Pe 14-16 | B222 | Veli Mäkinen | 05.09.2016—14.10.2016 | Study group! |
Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|
To 12-14 | B222 | Veli Mäkinen | 08.09.2016—20.10.2016 |
Information for international students
The course will be given in English. The questions in the course exam, renewal exam, and separate exams will be in English.
Yleistä
News.
Reading for separate exam? Here is a package containing most relevant material.
The separate exam on 24.1.17 is now graded.
The separate exam on 29.11.16 is now graded.
The exam is now graded. There will be a feedback session on Tue 15.11 9.30-10.30 room D234.
Pseudocode of linear time Select fixed (base case to return j-th smallest element on small array).
You can check your exercise points here: https://ilmo.cs.helsinki.fi/tulokset/
Description: General design principles of algorithms. Examples of central problems, typical solutions, reductions between problems. Recurrences, analysis techniques, worst / best / amortised / average case / expected case analysis. Dynamic programming, network flows, NP-completeness.
Prerequisites: the course Data Structures and Algorithms or equivalent knowledge. Strongly recommended: basic courses in mathematics, especially in calculus, probability, and discrete math (basics of logic, graphs, combinatorics).
Learning goals: see this draft matrix.
Weekly agenda:
- Wednesday lecture by V. M.: Introduction to the week's topic and setting up goals what to study before attending your selected Friday study group.
- Friday study groups by V. M. and D. V.: Online problem solving to get hands on experience on the topic.
- Wednesday exercise sessions by T. T. and D. V.: Exercise questions are announced at latest on Friday after the study groups, and the goal of this independent homework is to reflect how well the learning goals are met. Seeing solutions by others and presenting your own solution at the exercise session gives the final opportunity to learn the previous week's topic before the next lecture.
Kurssin suorittaminen
To pass the course you need to earn more than 30 points (tentative, may be lowered depending on the difficulty of the exam). From the exam you may get up to 54 points and from weekly exercises you may earn up to 6 points. To attend the course exam, you should earn at least one point from exercises. Otherwise, you can alway attend a separate exam.
To get exercise points you need to either (a) show up in an exercise session and describe your solution if asked, or (b) send your solutions to the instructur (topi.talvitie[at]helsinki.fi) by email before the first exercise session of the week. The points from the exercises come through a linear scale. We expect to have 6*6=36 assignments; in that case the scale is 6 -> 1 p, 11 -> 2p, 16 -> 3p, 21 -> 4p, 26 -> 5p, 31 -> 6p.
Kirjallisuus ja materiaali
Course book: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009.
Chapters 1, 2, 3, 22, 23, 24, 25 are recommended as background material before (during) attending the course; these concepts are briefly revisited when needed, but not thoroughly covered as these chapters are part of prerequisite Data Structures and Algorithms course.
Lecture notes will be linked here some time after each lecture.
Additional material:
DAA@MIT.OCW, TCS cheatsheet, Compedium of NP-complete problems, a graph of NP-complete problems