bild
Skolan för
datavetenskap
och kommunikation
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:

Solution

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

Mästarprov 2 (Extra version)

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:

Mästarprov 1

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:

Mästarprov 2

Last years exam looked like this:

Exam

An English version:

Exam in English

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.

F1

F2

F3

F4+F5

F6

F7

F7

F8

F9+F10

F11+F12

F13+F14

Övningar

Övning 1, Problems

Övning 1, Problems and solutions

Övning 2, Problems

Övning 2, Problems and solutions

Övning 3+4, Problems

Övning 3+4, Problems and solutions

Övning 5, Problems

Övning 5, Problems and solutions

Övning 6, Problems

Övning 6, Problems and solutions

Övning 7, Problems

Övning 7, Problems and solutions

Övning 8, Problems

Övning 8, Problems and solutions

Övning 9, Problems

Övning 9, Problems and solutions

Copyright © Sidansvarig: Johan Karlander <johank@nada.kth.se>
Uppdaterad 2011-05-16