DD2352, Algorithms and Complexity 2012, algokomp12
Course Information
Course leader and lecturer: Johan Karlander
johank@nada.kth.se
.
Course assistant: Musard Balliu: musard@kth.se
.
Solutions to the exam
Solutions
Course evaluation
Here are some questions we would like you to answer:
Questions
Current information
Exam for grades A,B.
My plan is to give this exam on June 5th either at 13-15 or 16-18. If you are interested, please contact my by email.
Extra lab session.
We have the so called lab week June 8-15. If you haven't done the labs it will be possible for you to do them then. Sign in at www.csc.kth.se/labbvecka.
20/3: Mas 2 is published
Mastarprov 2
5/3: Lab 2 is published.
17/2: Error on webpage! Todays Ovning is 10-12 and nothing else!
9/2: Mastarprov 1
7/2: There is a change in schedule for Mastarprov 1. Will be published Feb 9 and returned Feb 24 (latest).
30/1: The date for the exam is set. It will be on May 31th 14-17 in Q34
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 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 counts 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.
Schedule for Mästarprov
Mästarprov 1 will be published 9/2 and shall be handed in 24/2
Mästarprov 2 will be published 20/3 and shall be handed in 3/4
Schedule
This is a preliminary form. There could be small changes during the course.
Week
| Date
| Time
| Place
| Activity
| Topic
| Reading instructions
|
3 | 17/1 | 13-15 | B24 | Föreläsning 1 | Introduction. Graph Algorithms
| Ch. 1-3
|
| 18/1 | 13-15 | B23 | Föreläsning 2 | Greedy Algorithms
| Ch. 4 (Except 4.4)
|
| 20/1 | 10-12 | B24 | Övning 1 | Algorithm Analysis
|
4 | 24/1 | 13-15 | B22 | Föreläsning 3 | Flow Algorithms. More about graph algorithms.
| Ch 7.1-7.3, 7.5, 4.4, 6.8-6.10
|
| 25/1 | 13-15 | E51 | Föreläsning 4 | Divide and Conquer Algorithms.
| Ch 5
|
| 27/1 | 10-12 | E35 | Övning 2 | Divide and Conquer Algorithms
|
5 | 30/1 | 8-10 | D3 | Föreläsning 5 | Dynamic Programming
| Ch 6
|
| 31/1 | 13-15 | D34 | Föreläsning 6 | Dynamic Programming cont.
| Ch 6
|
| 3/2 | 10-12 | D33 | Övning 3 | Dynamic Programming
|
6 | 7/2 | 13-15 | Q24 | Föreläsning 7 | Introduction to Linear Programming
| The chapter on Linear Programming in "Kursbunt".
|
| 8/2 | 13-15 | Gul | Lab 1 | Reporting of theory problems. Help session.
|
| 9/2 | 13-15 | D32 | Föreläsning 8 | Probabilistic Algorithms and other algorithms
| Lecture notes
|
| 10/2 | 10-12 | Q26 | Övning 4 | Dynamic Programming cont.
|
7 | 14/2 | 13-15 | K53 | Föreläsning 9 | Complexity. NP-problems.
| Ch 8
|
| | 15-17 | Gul | Lab 1 | Lab reporting
|
| 15/2 | 13-15 | D34 | Föreläsning 10 | NP-problems cont.
| Ch 8
|
| 17/2 | 10-12 | D42 | Övning 5 | Flow Algorithms and Linear Programming.
|
8 | 21/2 | 13-15 | E53 | Föreläsning 11 | Turing Machines. Computability.
| Kursbunten, Lecture notes.
|
| 22/2 | 13-15 | K53 | Föreläsning 12 | Uncomputability.
| Kursbunten, Lecture notes.
|
| 24/2 | 10-12 | E35 | Övning 6 | NP-problems.
|
12 | 20/3 | 10-12 | E51 | Föreläsning 13 | Approximation Algorithms
| Ch 11
|
| 22/3 | 10-12 | E51 | Övning 7 | NP-problems. Uncomputability.
|
13 | 27/3 | 10-12 | E36 | Föreläsning 14 | Approximation Algorithms cont.
| CH 13.1-13.5
|
| 29/3 | 10-12 | Q17 | Övning 8 | Approximation Algorithms.
|
| | 15-17 | Gul | Lab 2 | Reporting of theory problems. Help session.
|
15 | 10/4 | 10-12 | E32 | Föreläsning 15 | Probabilistic Algorithms. PSPACE-problems.
| Ch 9
|
| 11/4 | 15-17 | E35 | Övning 9 | Repetition.
|
| 12/4 | 15-17 | Gul | Lab 2 | Lab reporting.
|
Lecture notes
F1
F2
F3
F4
F5 (updated)
F6 (updated)
F7 (draft)
F8 (updated)
F9
F10
F11
F12
F13
F14
F15
Exercises
Exercise 1
Solutions 1
Exercise 2
Solutions
Exercise 3+4
Solutions
Exercise 5
Solutions
Exercise 6
Solutions
Exercise 7
Solutions
Exercise 8
Solutions
Exercise 9
Solutions
Old lecture notes
There is a set of lecture notes from previous year. They are in Swedish.
F1
F2
F3
F4+F5
F6
F7
F8
F9+F10
F11+F12
F13+F14