Skolan för
elektroteknik
och datavetenskap
KTH / CSC / Kurser / DD2354 / algokomp10

DD2354, Algorithms and Complexity 2010, algokomp10

Exams

There will be an exam on June 8th at 14-16 in D2.

There will probably be an exam on August 24th at 18-20.

Course Information

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

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

Current information

Those of you got a C on the exam can take the oral exam for higher grade. The are two possibilities: If you want to do the exam before Christmas, please email me so we can fix a time. It can be done on Monday, Tuesday or Wednesday. If you do not want/need to do it before Christmas it can be done January 10th - January 14th. Please contact me so we can fix a time.

Here are solutions (at least sketches) to the exam:

There is an extra version of Mästerprov 2. It is for students who failed Mästerprov 2.

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 form is similar to DD1352 Algoritmer, datastrukturer och komplexitet. A description in Swedish can be found here: Examination The examination has three parts. There are two home assignements (Mästarprov). They consists 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). The course ends with a written exam.

Schedule

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

Week Date Time Place Activity Topic Reading instructions
3823/910-12V3Föreläsning 1Introduction. Graph Algorithms Ch. 1-3
13-15D42Övning 1Algorithm Analysis
3929/910-12Q36Föreläsning 2Greedy Algorithms Ch. 4 (Except 4.4)
406/1010-12Q36Föreläsning 3Divide and Conquer Algorithms Ch. 5
13-15Q36Övning 2Divide and Conquer Algorithms
4326/1010-12V35Föreläsning 4Dynamic Programming Ch. 6.1-6.3
13-15Q34Övning 3Dynamic Programming
29/1010-12Q34Föreläsning 5Dynamic Programming cont. CH. 6.4-6.7
442/1110-12Q33Föreläsning 6Graph Algorithms cont. Ch. 4.4, ch. 6.8-6.10
13-15L52Övning 4Dynamic Programming cont.
5/1110-12Q34Föreläsning 7Flow Algorithms. Introduction to Linear Programmming.
459/118-10Grå+KarmosinLab 1Reporting of theory problems. Help session.
9/1110-12Q31Föreläsning 8Linear Programming cont.
13-15Q34Övning 5Flow Algorithms and Linear Programming.
12/1110-12L51Föreläsning 9Complexity. NP-problems.
4616/1110-12Q33Föreläsning 10NP-problems cont.
13-15V23Övning 6NP-problems.
15-17Brun+GrönLab 1Lab reporting
19/1110-12M3Föreläsning 11Turing Machines. Computability.
4723/118-10Spel+SportLab 2Reporting of theory problems. Help session.
23/1110-12L52Föreläsning 12Uncomputability.
13-15Q31Övning 7NP-problems. Uncomputability.
26/1110-12M3Föreläsning 13Approximation Algorithms
4830/118-10Spel+SportLab 2Lab reporting.
30/1110-12M33Föreläsning 14Approximation Algorithms cont.
13-15M33Övning 8Approximation Algorithms.
497/1210-12K1Föreläsning 15Probabilistic Algorithms. PSPACE-problems.
13-15Q33Övning 9Repetition.

Mästarprov

Mästarprov 1 is now published:

Comments: Observe that when we say integers they can be both positive, negative and zero. Without that convention problem 1 would be very trivial indeed!

The exam

The exam consists of 5 theory questions. I you solve about half of them correctly you will get E. If you get a C you have the option to do an oral exam in order to get a higher grade.

Mästarprov 2 is now published:

Last years exam looked like this:

An English version:

Laboratory Work

Some of you are SU-students and are required to do two laboratory works. The rest of you do not have to do them but I have decided to reward those of you doing them with up to 4 bonus credits to the written exam. More information about the labs can be found here.

Old lecture notes

There is a set of lecture notes from previous year. They are in Swedish.

Övningar

Övning 1, Problems