KTH / CSC / Kurser / DD2352 / algokomp12

DD2352, Algorithms and Complexity 2012, algokomp12

Course Information

Course leader and lecturer: Johan Karlander johank@nada.kth.se.

Course assistant: Musard Balliu: musard@kth.se.

Extra exam

Some of you have told me that you will not be able to attend the ordinary exam on May 31th. For you, there will be an extra exam on May 10th. If you are interested in doing the exam on the 10th, please contact me.

Extra Mastarprov

For those of you that haven't done Mas 1 or Mas 2 there will be an extra opportunity to do them. However, it will only be possible to get at most grade E on these extra assignments. They will be published on May 2nd and should be handed in latest May 16th.

Extra Mastarprov 1

Extra Mastarprov 2

Extra lab session

In the same way, For those of you that haven't done Lab 1 or Lab 2 there will be an extra opportunity to do them. We have planned a lab session for May 7th, 13-15.

Current information

Presentation of Mas 2:+ 20/3: Mas 2 is published

Mastarprov 2

5/3: Lab 2 is published.

17/2: Error on webpage! Todays Ovning is 10-12 and nothing else!

9/2: Mastarprov 1

7/2: There is a change in schedule for Mastarprov 1. Will be published Feb 9 and returned Feb 24 (latest).

30/1: The date for the exam is set. It will be on May 31th 14-17 in Q34

Course literature

Kleinberg, Tardos; Algorithm Design, Pearson Addison-Wesley.

Learning outcomes

The goals of the course are to give the students

the fundamental skills needed to develop algorithms using data structures and analyze their correctness and efficiency,
an introduction to complexity theory,

so that they will be able to

design programs that use computer resources efficiently,
realize that there are problems that are impractical or even impossible to solve by a computer.

Course content

Principles for construction of algorithms: Decomposition, greedy algorithms, dynamic programming. Algorithm analysis. Probalistic algorithms. Approximation. Selected applications to sets, graphs, arithmetic, and geometry.

Computability and complexity: Reduction. Complexity classes P (polynomial time), NP (non-deterministic polynomial time), and NC (efficiently parallelizable problems). NP-complete problems. Undecidable problems.

Examination

The examination has four parts.

There are two home assignements (Mästarprov). They consist of 4 problems. They will be graded F-A. Basically, two problems correctly solved give you an E. They will be handed out during the course. You should hand in a written report and then do a short oral exam (15 min).
There are two laboratory works.
The course ends with a written exam.

Three of the parts are graded: Mas 1, Mas 2 and Exam. The final course grade will be the mean value of these grades where E counts as 1 and A counts as 5. In the first written phase the grade on the exam will be E, D or C. If you get grade C on the exam or if you pass the exam and has got at least C on both Mas 1 and Mas 2 you can do a complementary exam and raise the grade on the exam to B or A.

Schedule for Mästarprov

Mästarprov 1 will be published 9/2 and shall be handed in 24/2

Mästarprov 2 will be published 20/3 and shall be handed in 3/4

Schedule

This is a preliminary form. There could be small changes during the course.

Week Date Time Place Activity Topic Reading instructions
3 17/1 13-15 B24 Föreläsning 1 Introduction. Graph Algorithms Ch. 1-3
18/1 13-15 B23 Föreläsning 2 Greedy Algorithms Ch. 4 (Except 4.4)
20/1 10-12 B24 Övning 1 Algorithm Analysis
4 24/1 13-15 B22 Föreläsning 3 Flow Algorithms. More about graph algorithms. Ch 7.1-7.3, 7.5, 4.4, 6.8-6.10
25/1 13-15 E51 Föreläsning 4 Divide and Conquer Algorithms. Ch 5
27/1 10-12 E35 Övning 2 Divide and Conquer Algorithms
5 30/1 8-10 D3 Föreläsning 5 Dynamic Programming Ch 6
31/1 13-15 D34 Föreläsning 6 Dynamic Programming cont. Ch 6
3/2 10-12 D33 Övning 3 Dynamic Programming
6 7/2 13-15 Q24 Föreläsning 7 Introduction to Linear Programming The chapter on Linear Programming in "Kursbunt".
8/2 13-15 Gul Lab 1 Reporting of theory problems. Help session.
9/2 13-15 D32 Föreläsning 8 Probabilistic Algorithms and other algorithms Lecture notes
10/2 10-12 Q26 Övning 4 Dynamic Programming cont.
7 14/2 13-15 K53 Föreläsning 9 Complexity. NP-problems. Ch 8
15-17 Gul Lab 1 Lab reporting
15/2 13-15 D34 Föreläsning 10 NP-problems cont. Ch 8
17/2 10-12 D42 Övning 5 Flow Algorithms and Linear Programming.
8 21/2 13-15 E53 Föreläsning 11 Turing Machines. Computability. Kursbunten, Lecture notes.
22/2 13-15 K53 Föreläsning 12 Uncomputability. Kursbunten, Lecture notes.
24/2 10-12 E35 Övning 6 NP-problems.
12 20/3 10-12 E51 Föreläsning 13 Approximation Algorithms Ch 11
22/3 10-12 E51 Övning 7 NP-problems. Uncomputability.
13 27/3 10-12 E36 Föreläsning 14 Approximation Algorithms cont. CH 13.1-13.5
29/3 10-12 Q17 Övning 8 Approximation Algorithms.
15-17 Gul Lab 2 Reporting of theory problems. Help session.
15 10/4 10-12 E32 Föreläsning 15 Probabilistic Algorithms. PSPACE-problems. Ch 9
11/4 15-17 E35 Övning 9 Repetition.
12/4 15-17 Gul Lab 2 Lab reporting.