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

23.10.2014 16.00 B123
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2014 syksy 03.09-17.10. 1-1 Englanti Mikko Koivisto

Luennot

Aika Huone Luennoija Päivämäärä
Ke 14-16 D122 Mikko Koivisto 03.09.2014-17.10.2014
Pe 12-14 D122 Mikko Koivisto 03.09.2014-17.10.2014

Harjoitusryhmät

Group: 1
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Pe 14-16 D122 Ping Xiao 08.09.2014—17.10.2014

Information for international students

Language: The course will be given in English. The questions in the course exam, renewal exam, and separate exams will be in English.

Yleistä

NOTE: Prof. Wojciech Szpankowski gives a guest lecture "Emerging Frontiers of Science of Information" on Monday Sep 8 at 4pm, Exactum A111. Among many other things, prof. Szpankowski is an author of a fresh, great result on solving divide and conquer recurrences, published in JACM, the most presitigious journal of (theoretical) computer science.

Description: 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 or equivalent. Strongly recommended: basic courses in mathematics, especially in calculus, probability, and discrete math (basics of logic, graphs, combinatorics).

Course feedback: Remember to give (here)! A summary of the feedback with the lecturer's reflections is here. It is still possible to give feedback. The summary and reflections were revisited on December 12.

Note: The estimated work load of the course is 5 credit units. As 1 credit unit amounts to about 27 hours of work, the estimated total work load in the course is about 135 hours, meaning about 19 hours of work per week (for an average student that gets an average grade). For instance, 4 hours for the lectures, 2 for the exercise session, 8 for solving the exercise problems, and the remaining 5 hours for reading the book.

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 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 lecturer (M.K.) by email before the exercise session. The number of exercise points you get is (the ceil of) the number of problems you have solved (marked) times six divided by the total number of exercise problems. At any time, if you want to know the points you have earned so far, please send email to the instructor (P.X.).

Some remarks concerning the exam. Please check the precise time and place in advance. You need to be prepared to prove your ID. You may bring only the very basic equipment, like pen or pencil, but no calculator, lecture notes etc. Paper sheets are provided to you by the house. You will have a total of 2 and a half hours for answering all the questions given in a separate sheet. You may expect the exam questions to be mostly similar to the exercise problems. See an old exam, a set of sufficient model solutions, and a set more detailed solutions and grading guidelines.

The course exam was held on Thursday 23rd October at 16:00. The results are out! See here for the exam questions, here for model solutions (actually from the last year, but  for essentially the same exam) and rough grading rules. The exam turned out to be somewhat laborious, which is, naturally, taken into account in final grading. For detailed inspection of the grading of your solutions, please send email to M.K. to agree an appointment.

Statistics: Grades: (5**** 4* 3**** 2******* 1*). Top performer: 52/54 on the exam, 58/60 in total. On each problem, at least one answer got full points. The thresholds for the grades were 44, 39, 34, 29, and 24 out of the 60 points in total.

Comments on the questions (time usage plan for Average Joe in parentheses, in minutes; think+write-revisit; total 140 min):

  1. A description and an analysis are in CLRS, aren't they? Many answers missed 2 points by not showing the Omega(n log n) bound, i.e., that halving indeed yields the best case. (13+15+2)
  2. Very similar to the knapsack problem, covered in CLRS and Week II lectures. Many answers missed nearly all the points by giving a greedy algorithm instead of using dynamic programming. (15+14+1)
  3. The reduction function is very straightforward, but one needs to know what the vertex cover problem is. Many answers missed 2 points by not formulating the correct decision problem. (9+9+2)
  4. A variant of Exercise 35.2-5 of CLRS, also included in Week V exercises. Many answers missed several points by not finding the correct probability 1/3! of 3-inversion for fixed (i, j, k). (10+8+2)
  5. Mixes the NP-hardness proof of the vertex cover problem (in CLRS and Week III lectures) and the 2-approximation algorithm for the vertex cover problem (in CLRS). There is actually a more direct proof that does not follow the hint. Many answers missed all the points by giving no answer at all. (20+15+5)

Kirjallisuus ja materiaali

Note: On Friday 17th October there is no lecture (as the lecturer is away).

Note: To boost your learning, consider reading the material in the book already before attending the corresponding lecture.

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, 4 (except 4.6), 5 (except 5.4), 7, 15, 17, 23, 24, 25, 26.3, 34, 35, scheduled along seven lecture weeks as follows:

Week I (36): Divide and conquer; Recurrences; Sorting; Matrix multiplication - Chapters 1, 2, 3, 4, 7.1

Week II (37): Dynamic programming, Short paths and cycles - Chapters 15, 24, 25

Week III (38): NP-completeness; TSP, SAT, Subset Sum, and other examples - Chapter 34

Week IV (39): Amortized analysis - Chapter 17

Week V (40): Randomization; Average case analysis - Chapters 5, 7

Week VI (41): Approximation algorithms; Matchings; Misc. - Chapters 23, 26.3, 35

Week VII (42): Summary and solutions to an old exam

 

Additional material:

See an alternative probabilistic analysis of Quicksort by clicking photo1 and photo2 of the blackboard work in the lecture.

DAA@MIT.OCW, TCS cheatsheet, Compedium of NP-complete problems

Associated lecture slides  (by Valentin Polishchuk (c) 2011)

Home works and their solutions will appear here.

Exercises for week I and solutions.

Exercises for week II and solutions.

Exercises for week III and solutions.

Exercises for week IV and solutions.

Exercises for week V and solutions.

Exercises for week VI and solutions. An alternative proof of Problem-1, Hall's Theorem (only for the direction: if |A| <= |N(A)| then there exists a perfect matching, since it's the harder part) is provided by Nikolay Vasilev. His proof is quite different.