Lectures
Lecture 1: Introduction. Multiplication of polynomials.
Lecture-1
Lecture 2: Fast Fourier Transform algorithm.
Lecture-2
Lecture 3: Primality testing. Rabin-Miller algorithm.
Lecture 4: Minimum spanning tree. Prim's algorithm.
http://uttv.ee/naita?id=18018
Lecture 5: Flow networks. Ford-Fulkerson algorithm.
Lecture 6: Dinitz algorithm.
http://uttv.ee/naita?id=18167
Lecture 7: Networks with upper and lower bounds on the flow.
http://uttv.ee/naita?id=18241
Lecture 8: Introduction into linear programming problems.
http://uttv.ee/naita?id=18322
Lecture 9: Simplex algorithm.
http://uttv.ee/naita?id=18359
Lecture 10: Approximation algorithms. Minimum vertex cover problem. Minimum cost set cover problem.
http://www.uttv.ee/naita?id=18499
Lecture 11: cancelled.
Lecture 12: Travelling salesman problem.
http://www.uttv.ee/naita?id=18563
Lecture 13: Knapsack problem.
http://uttv.ee/naita?id=18598
Lecture 14: Using linear programming in approximation algorithms. Dual-fitting-based analysis. Rounding algorithms.
Lecture 15: Primal-dual method. Algorithm for set cover problem using primal-dual method.
http://uttv.ee/naita?id=18670
Lecture 16: Primal-dual for minimum Steiner Forest problem (cont.).
Practice sessions
Tutorial 1: O()-notation. Comparison of complexity functions. Divide and conquer method. O(n log n) lower bound on comparison-based sorting. Fast matrix multiplication.
Tutorial 2: Fast Fourier Transform algorithm. Polynomial interpolation. Algorithm of Gauss for fast multiplication of two n-bit integers.
Tutorial 3: Graphs and trees. Properties of the trees.
http://uttv.ee/naita?id=17895
Tutorial 4: Kruskal's algorithm. Minimum spanning trees.
http://uttv.ee/naita?id=18029
Tutorial 5: Applications of flow in networks: maximum matching in bipartite graphs, vertex-disjoint path cover.
Tutorial 6: Applications of flow in networks (cont.): minimum vertex cover in bipartite graphs.
http://uttv.ee/naita?id=18196
Tutorial 7: Finding maximum flow in 0-1 networks.
http://uttv.ee/naita?id=18247
Tutorial 8: Hall's Theorem. Examples of linear-programming problems. Equivalent problems. Integer linear-programming problems and relaxations: maximum matching, vertex cover.
http://uttv.ee/naita?id=18323
Tutorial 9: Examples: simplex algorithm.
http://www.uttv.ee/naita?id=18497
Tutorial 10: Examples of approximation algorithms. Finding a maximum matching in a general graph.
http://www.uttv.ee/naita?id=18500
Tutorial 11: Finding a maximum matching in a general graph (cont.)
http://www.uttv.ee/naita?id=18544
Tutorial 12: Travelling salesman problem in a directed graph. PTAS and FPTAS. Knapsack problem.
http://www.uttv.ee/naita?id=18577
Tutorial 13: Bin packing problem.
http://uttv.ee/naita?id=18645
Tutorial 14: Integrality and half-integrality.
http://uttv.ee/naita?id=18669
Tutorial 15: Primal-dual for minimum Steiner Forest problem.
http://uttv.ee/naita?id=18748
Tutorial 16: Coping with NP-hardness. Heuristics.