Schedule:

The dates are when discussion about each topic will take place. It is obligatory to watch the videos on the topic before that date.
Questions about the content can be sent beforehand by email.

3.9. Introduction lecture 3.9. Complexity + analysis techniques 10.9. Divide-and-Conquer 17.9. Dynamic programming 24.9. Greedy + fast MST Branch-and-bound 1.10. Randomized algorithms + Sherwood Approximation algorithms (Binpacking) + Approximation algorithms (TSP) 8.10. NP theory 15.10. Heap + Divide-and-Conquer k-NN 25.10. Q&A session 1.11. EXAM


Lecture Material:

Introduction
Analysis techniques
Divide and conquer
Closest pair problem
Dynamic programming
Dynamic programming: edit distance
Route reduction
Shortest paths problem
Greedy algorithms
Divide-and-Conquer MST
Divide-and-Conquer kNN
Branch-and-bound
Heap structure
Heap structure (by P.Kilpeläinen)
Union-find (by M.I.Malinen)
Union-Find structure (by T.H.Cormen)
Approximation algorithms
Randomized algorithms
Combinatoric optimization
NP-theory
NP reductions

Supplementary material:

TSP example | B-n-B for TSP
Lecture notes: Sariel Har-Peled (UIUC)
Lecture notes: Jeff Erickson (UIUC)
Maximum weighted matching
Lecture Notes: Introduction to Combinatoric Optimization
Genetic algorithms for clustering
Lecture Notes: Dynamic Programming
The Design of Approximation Algorithms
Millenium problems: P=NP ?
NP-complete problems
Minesweeper is NP-complete
Hanoi Towers
Sieve of Erastothenes
TRA I
TRA II
TRA I (in Finnish)
TRA II (In Finnish)