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
38	23/9	10-12	V3	Föreläsning 1	Introduction. Graph Algorithms	Ch. 1-3
		13-15	D42	Övning 1	Algorithm Analysis
39	29/9	10-12	Q36	Föreläsning 2	Greedy Algorithms	Ch. 4 (Except 4.4)
40	6/10	10-12	Q36	Föreläsning 3	Divide and Conquer Algorithms	Ch. 5
		13-15	Q36	Övning 2	Divide and Conquer Algorithms
43	26/10	10-12	V35	Föreläsning 4	Dynamic Programming	Ch. 6.1-6.3
		13-15	Q34	Övning 3	Dynamic Programming
	29/10	10-12	Q34	Föreläsning 5	Dynamic Programming cont.	CH. 6.4-6.7
44	2/11	10-12	Q33	Föreläsning 6	Graph Algorithms cont.	Ch. 4.4, ch. 6.8-6.10
		13-15	L52	Övning 4	Dynamic Programming cont.
	5/11	10-12	Q34	Föreläsning 7	Flow Algorithms. Introduction to Linear Programmming.
45	9/11	8-10	Grå+Karmosin	Lab 1	Reporting of theory problems. Help session.
	9/11	10-12	Q31	Föreläsning 8	Linear Programming cont.
		13-15	Q34	Övning 5	Flow Algorithms and Linear Programming.
	12/11	10-12	L51	Föreläsning 9	Complexity. NP-problems.
46	16/11	10-12	Q33	Föreläsning 10	NP-problems cont.
		13-15	V23	Övning 6	NP-problems.
		15-17	Brun+Grön	Lab 1	Lab reporting
	19/11	10-12	M3	Föreläsning 11	Turing Machines. Computability.
47	23/11	8-10	Spel+Sport	Lab 2	Reporting of theory problems. Help session.
	23/11	10-12	L52	Föreläsning 12	Uncomputability.
		13-15	Q31	Övning 7	NP-problems. Uncomputability.
	26/11	10-12	M3	Föreläsning 13	Approximation Algorithms
48	30/11	8-10	Spel+Sport	Lab 2	Lab reporting.
	30/11	10-12	M33	Föreläsning 14	Approximation Algorithms cont.
		13-15	M33	Övning 8	Approximation Algorithms.
49	7/12	10-12	K1	Föreläsning 15	Probabilistic Algorithms. PSPACE-problems.
		13-15	Q33	Övning 9	Repetition.

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.