DD2352, Algorithms and Complexity 2014, algokomp15

Course Information

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

Course assistant: Mladen Miksa: miksa@kth.se.

Course literature

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

Learning outcomes

The goals of the course are to learn the students

the fundamental skills needed to develop algorithms using data structures and to 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), 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 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 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. 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 14/2 and shall be handed in 28/2.

Mästarprov 2 will be published 7/4 and shall be handed in 28/4.

If you have failed either Mas 1 or Mas 2 there will be extra versions of them to solve. They will be published May 12 and should be submitted latest May 26.

Schedule

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

Week Date Activity Topic Reading instructions
4 20/1 Lecture 1 Introduction. Graph Algorithms Ch. 1-3
21/1 Lecture 2 Greedy Algorithms Ch. 4 (Except 4.4)
22/1 Exercise 1 Algorithm Analysis
5 26/1 Lecture 3 Flow Algorithms. More about graph algorithms. Ch 7.1-7.3, 7.5, 4.4, 6.8-6.10
27/1 Lecture 4 Divide and Conquer Algorithms. Ch 5
29/1 Exercise 2 Divide and Conquer Algorithms
6 2/2 Lecture 5 Dynamic Programming Ch 6
5/2 Lecture 6 Dynamic Programming cont. Ch 6
6/2 Exercise 3 Dynamic Programming
7 9/2 Lecture 7 Introduction to Linear Programming Lecture notes. Extra material on Linear Programming. Can be found on Kurswebben.
11/2 Lecture 8 Probabilistic Algorithms and other algorithms Lecture notes
12/2 Exercise 4 Dynamic Programming cont.
13/2 Lab 1 Reporting of theory problems. Help session.
8 16/2 Lecture 9 Complexity. NP-problems. Ch 8
18/2 Lecture 10 NP-problems cont. Ch 8
19/2 Exercise 5 Flow Algorithms and Linear Programming.
20/2 Lab 1 Lab reporting
9 23/2 Lecture 11 Uncomputability. Lecture notes. Extra material on Uncomputability. Can be found on Kurswebben.
24/2 Lecture 12 Turing Machines. Computability. Lecture notes. Extra material on Turing Machines. Can be found on Kurswebben. (You must login.)
26/2 Exercise 6 NP-problems.
14 30/3 Lecture 13 Approximation Algorithms Ch 11
31/3 Exercise 7 NP-problems. Uncomputability.
16 13/4 Lecture 14 Approximation Algorithms cont. CH 13.1-13.5
14/4 Exercise 8 Approximation Algorithms.
16/4 Lab 2 Reporting of theory problems. Help session.
17 20/4 Lecture 15 Probabilistic Algorithms. PSPACE-problems. Ch 9
21/4 Exercise 9 Repetition.
23/4 Spel Lab 2 Lab reporting.
23 1/6 V33,V35 Exam

Week	Date	Activity	Topic	Reading instructions
4	20/1	Lecture 1	Introduction. Graph Algorithms	Ch. 1-3
	21/1	Lecture 2	Greedy Algorithms	Ch. 4 (Except 4.4)
	22/1	Exercise 1	Algorithm Analysis
5	26/1	Lecture 3	Flow Algorithms. More about graph algorithms.	Ch 7.1-7.3, 7.5, 4.4, 6.8-6.10
	27/1	Lecture 4	Divide and Conquer Algorithms.	Ch 5
	29/1	Exercise 2	Divide and Conquer Algorithms
6	2/2	Lecture 5	Dynamic Programming	Ch 6
	5/2	Lecture 6	Dynamic Programming cont.	Ch 6
	6/2	Exercise 3	Dynamic Programming
7	9/2	Lecture 7	Introduction to Linear Programming	Lecture notes. Extra material on Linear Programming. Can be found on Kurswebben.
	11/2	Lecture 8	Probabilistic Algorithms and other algorithms	Lecture notes
	12/2	Exercise 4	Dynamic Programming cont.
	13/2	Lab 1	Reporting of theory problems. Help session.
8	16/2	Lecture 9	Complexity. NP-problems.	Ch 8
	18/2	Lecture 10	NP-problems cont.	Ch 8
	19/2	Exercise 5	Flow Algorithms and Linear Programming.
	20/2	Lab 1	Lab reporting
9	23/2	Lecture 11	Uncomputability.	Lecture notes. Extra material on Uncomputability. Can be found on Kurswebben.
	24/2	Lecture 12	Turing Machines. Computability.	Lecture notes. Extra material on Turing Machines. Can be found on Kurswebben. (You must login.)
	26/2	Exercise 6	NP-problems.
14	30/3	Lecture 13	Approximation Algorithms	Ch 11
	31/3	Exercise 7	NP-problems. Uncomputability.
16	13/4	Lecture 14	Approximation Algorithms cont.	CH 13.1-13.5
	14/4	Exercise 8	Approximation Algorithms.
	16/4	Lab 2	Reporting of theory problems. Help session.
17	20/4	Lecture 15	Probabilistic Algorithms. PSPACE-problems.	Ch 9
	21/4	Exercise 9	Repetition.
	23/4	Spel	Lab 2	Lab reporting.
23	1/6	V33,V35	Exam