Design and Analysis of Algorithms
|Ti 12-14||D122||Mikko Koivisto||04.09.2012-12.10.2012|
|Pe 12-14||D122||Mikko Koivisto||04.09.2012-12.10.2012|
Information for international students
Language: The course will be given in English.
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.
For the regular course exam (held on October 18), see below.
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.
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. Old exam questions not available.
The regular course exam was held on October 18, 2012: The results are out! See here for the exam questions, here for model solutions, and here for more rigorous explanations and grading rules. The exam turned out to be rather difficult and 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 fix an appointment.
Statistics: Grades: (5*** 4*** 3**** 2** 1***). Top performer: 42/54 on the exam, 48/60 in total. Top points per question: 9/9 on questions 1-4, 8/9 on question 5, and 7/9 on question 6. Average number of points per question: 5.5, 1.8, 2.6, 2.8, 3.8, 1.7 (over all participants of the exam) and 6.2, 2.6, 4.1, 4.0, 5.4, 2.9 (over those that got at least one point from the question).
Comments on the questions (time usage plan for Average Joe in parentheses, in minutes; think+write-revisit; total 140 min):
- Basics. The two simpler cases of the master method directly apply. (5+4+1)
- Essentially the same as the rod-cutting problem, covered in CLRS and Week II lectures. (10+9+1)
- Exercise 34.5-5 of CLRS with added hint. Finding the retrospectively obvious reduction turned out to be difficult. (14+10+6)
- A cute algorithm, of which analysis requires some actual, amortized-style thinking, elementary though. (14+10+1)
- An example taken from CLRS (proof of Thm 35.6, page 1124). (10+9+1)
- A variant of Exercise 34.4-6 of CLRS, also included in Week III exercises. Calls for mixing multiple techniques learned during the course. (15+14+6)
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
Home works and their solutions will appear here.
|Ti 14-16||C222||Teppo Niinimäki||10.09.2012-12.10.2012|
|Pe 14-16||C222||Teppo Niinimäki||10.09.2012-12.10.2012|