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