DD2352, Algorithms and Complexity 2014, algokomp14

Times for oral exam

These are the requirements for being admissable for the oral exam. You should

Have grade C on the exam

Have grade E or D on the exam and have at least grade C on both Mas 1 and Mas 2.

Course evaluation

Here are some questions we would like you to answer:

Questions

Solutions to the exam

Solutions

Course Information

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

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

Current information

Booking for extra mas:

19/5: For those of you who haven't completed all labs there will be an extra opportunity during the lab week:

http://www.csc.kth.se/utbildning/kth/labbvecka/

22/4: Mas 2 is published.

If you want to practise your skills and see what a mästarprov could look like, you can try to solve this one: Mas 2 2010

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,

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

This extra exam will be given June 9-11. There will be individual booking.

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 22/4 and shall be handed in 6/5.

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.

For those who have failed either Mas1 or Mas2 there are extra versions here. Correctly solved they give grade E:

Extra mas1

Extra mas2

Here are some sketches for solutions to the old Mas 2 previously published. Solutions

Schedule

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

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