Design and Analysis of Algorithms

582630
5
Algoritmit ja koneoppiminen
Syventävät opinnot
General design principles of algorithms. Examples of central problems and typical solutions. Average case analysis. Amortised complexity. Recurrences. NP-completeness. Prerequisites: the course Data Structures and Algorithms or equivalent.

Koe

26.10.2016 16.00 A111
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

Group: 1
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Ke 10-12 B119 Topi Talvitie 12.09.2016—21.10.2016
Group: 2
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Ke 12-14 B119 Topi Talvitie 12.09.2016—21.10.2016
Group: 3
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Ke 16-18 B119 Daniel Valenzuela 12.09.2016—21.10.2016
Group: 4
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Pe 10-12 B222 Veli Mäkinen 05.09.2016—14.10.2016 Study group!
Group: 5
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Pe 12-14 B222 Daniel Valenzuela 05.09.2016—14.10.2016 Study group!
Group: 6
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Pe 14-16 B222 Veli Mäkinen 05.09.2016—14.10.2016 Study group!
Group: 7
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