DD2352, Algorithms and Complexity 2013, algokomp13

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

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

Course evaluation

Here are some questions we would like you to answer:

Labs remaining?

If you havn't done all the labs, there will be an opportunity to do it in the "lab week". You can find information about this at http://www.csc.kth.se/utbildning/kth/labbvecka/

Solutions to the exam 130520

Solutions

Exam for higher grade

Here are three times for the extra exam:

Wednesday May 22 13-16

Thursday May 23 15-18

Friday May 24 13-16

It takes place in room 1527.

If you are interested in doing this, you should mail me and suggest a suitable day.If there are too many students preferring the same time slot I will contact you and try to arrange some other time. Mail me at latest 17.00 May 21. If none of the times suites you, we could possibly find some other occasion, but I prefer that you chose one of the suggested times.

In order to do the exam you have to have C on the ordinary exam or at least C on both Mas 1 and Mas 2. You can raise your grade on the exam, Mas 1 and Mas 2. You will get 1,2 or 3 problems to work on for one hour. After that you will be orally examined on your solutions.

Extra Mas

Mas 1

Mas 2

Current information

15/4: Some more information on the exam is added to the page.

5/4: Mas 2 is published.

14/3: Lab 2 is published.

1/3: Here is a clarification of some points in problem 4 in Mas 1:

The network contains c_i-nodes, K and other nodes. A message can take any path in the network. By connections I mean edges. The police has to select a set of edges such that any message, sent from any ci to K , sent along any path, has to pass through at least one of the edges the police has selected.

19/2: Mästarprov 1 is published.

20/2: A change is made in problem 1 of Mas 1. (A simplification).

The course starts on Jan 14 at 08.15 in D42.

There has been a change in schedule concerning week 6 and 10.

Course literature

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

"Kursbunt" with some extra texts. Is sold at Studentexpeditionen for 25 kr.

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,

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 c orrectly 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.

Last year's 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 count s 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 i f 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. On the complementary exam you can also raise the grade on Mas 1 and Mas 2. The form of the exam is like this: You get 1, 2 or 3 problems to solve depending on whether you want a higher grade on Mas 1, Mas 2 or the exam. You get one hour to think about the problems. Then you will present the solutions to the examiner.

Preliminary schedule for Mästarprov

Mästarprov 1 will be published 19/2 and shall be handed in 5/3

Mästarprov 2 will be published 5/4 and shall be handed in 19/4

Mästarprov

Mästarprov 1

Mästarprov 2

Extra Mästarprov

For those who have failed to complete Mas 1 or Mas 2 there will be an extra set of problems handed out on May 13th, to be returned on May 27th. But you can only get grade E by doing them.

Schedule

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

Week	Date	Time	Place	Activity	Topic	Reading instructions
3	14/1	8-10	D42	Föreläsning 1	Introduction. Graph Algorithms	Ch. 1-3
	16/1	13-15	D42	Föreläsning 2	Greedy Algorithms	Ch. 4 (Except 4.4)
	18/1	10-12	Q21	Övning 1	Algorithm Analysis
4	22/1	13-15	E32	Föreläsning 3	Flow Algorithms. More about graph algorithms.	Ch 7.1-7.3, 7.5, 4.4, 6.8-6.10
	23/1	13-15	E51	Föreläsning 4	Divide and Conquer Algorithms.	Ch 5
	25/1	10-12	Q21	Övning 2	Divide and Conquer Algorithms
5	29/1	10-12	D41	Föreläsning 5	Dynamic Programming	Ch 6
	30/1	13-15	D32	Föreläsning 6	Dynamic Programming cont.	Ch 6
	1/2	10-12	Q13	Övning 3	Dynamic Programming
6	4/2	15-17	Orange, Grå	Lab 1	Reporting of theory problems. Help session.
	8/2	13-15	Q31	Övning 4	Dynamic Programming cont.
7	11/2	8-10	D41	Föreläsning 7	Introduction to Linear Programming	The chapter on Linear Programming in "Kursbunten".
	11/2	115-17	Orange, Grå	Lab 1	Lab reporting
	13/2	13-15	D41	Föreläsning 8	Probabilistic Algorithms and other algorithms	Lecture notes
	15/2	15-17	D42	Övning 5	Flow Algorithms and Linear Programming.
8	18/2	10-12	D42	Föreläsning 9	Complexity. NP-problems.	Ch 8
	20/2	13-15	D32	Föreläsning 10	NP-problems cont.	Ch 8
	21/2	10-12	E33	Övning 6	NP-problems.
10	5/3	13-15	Q21	Föreläsning 11	Uncomputability.	Kursbunten, Lecture notes.
	8/3	10-12	Q21	Föreläsning 12	Turing Machines. Computability.	Kursbunten, Lecture notes.
12	18/3	10-12	D41	Föreläsning 13	Approximation Algorithms	Ch 11
	20/3	13-15	D32	Övning 7	NP-problems. Uncomputability.
13	25/3	13-15	D32	Föreläsning 14	Approximation Algorithms cont.	CH 13.1-13.5
	26/3	13-15	E32	Övning 8	Approximation Algorithms.
	28/3	15-17	Spel	Lab 2	Reporting of theory problems. Help session.
15	8/4	10-12	Q31	Föreläsning 15	Probabilistic Algorithms. PSPACE-problems.	Ch 9
	10/4	13-15	D42	Övning 9	Repetition.
	12/4	15-17	Spel	Lab 2	Lab reporting.