# Design and Analysis of Algorithms

## Koe

Vuosi | Lukukausi | Päivämäärä | Periodi | Kieli | Vastuuhenkilö |
---|---|---|---|---|---|

2013 | syksy | 03.09-11.10. | 1-1 | Englanti | Mikko Koivisto |

## Luennot

Aika | Huone | Luennoija | Päivämäärä |
---|---|---|---|

Ti 12-14 | D122 | Mikko Koivisto | 03.09.2013-11.10.2013 |

Pe 12-14 | D122 | Mikko Koivisto | 03.09.2013-11.10.2013 |

## Harjoitusryhmät

Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|

Ti 14-16 | D122 | Juho-Kustaa Kangas | 09.09.2013—11.10.2013 |

Aika | Huone | Ohjaaja | Päivämäärä | Huomioitavaa |
---|---|---|---|---|

Pe 14-16 | D123 | Juho-Kustaa Kangas | 09.09.2013—04.10.2013 | |

Pe 14-16 | C220 | Juho-Kustaa Kangas | 11.10.2013—11.10.2013 |

## Information for international students

**Language:** The course will be given in English.

## Yleistä

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

**Course feedback:** Remember to give (**here**)! A summary of the feedback with the instructor's reflections is **here**.

**NEW The renewal exam will be held on November 26, 2013**.

For the regular course exam (held on October 15), see below.

## 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 instructor (M.K.) by email before the Tuesday 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 teaching assistant (J-K.K.).

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

**The course exam was held on Tuesday 15 October at 9:00 - 11:30. The results are out!** See **here** for the exam questions, **here** for model solutions 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: 53/54 on the exam, 59/60 in total. Top points per question: 11/12 on question 1, 6/6 on question 3, and 12/12 on the remaining questions.

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

- 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)
- 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) - 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)
- 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) - 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). Many answers missed all the points by giving no answer at all. (20+15+5)

## 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, 4 (except 4.6), 5 (except 5.4), 7, 15, 17, 23, 24, 25, 26.3, 34, 35, scheduled along six 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

**Additional material:** 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.