## DD2354, Algorithms and Complexity 2010, algokomp10## ExamsThere 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 InformationCourse leader and lecturer: Johan Karlander`johank@nada.kth.se` .
Course assistant: Musard Balliu: ## Current informationThose 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:
There is an extra version of Mästerprov 2. It is for students who failed Mästerprov 2. ## Course literatureKleinberg, Tardos; Algorithm Design, Pearson Addison-Wesley.
## Learning outcomesThe 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 contentPrinciples 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. ## ExaminationThe 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.## ScheduleThis is a preliminary form. There could be small changes during the course.
## MästarprovMästarprov 1 is now published: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 examThe 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:
Last years exam looked like this: An English version: ## Laboratory WorkSome 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 notesThere is a set of lecture notes from previous year. They are in Swedish.## ÖvningarÖvning 1, ProblemsÖvning 1, Problems and solutions Övning 2, Problems and solutions Övning 3+4, Problems and solutions Övning 5, Problems and solutions Övning 6, Problems and solutions Övning 7, Problems and solutions |