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
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
so that they will be able to
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