Lectures
Scripts of lectures and tutorials, fall 2018-2019
Lecture 1 + Tutorial 1: O()-notation. Comparison of complexity functions. Basic notions in graph theory.
Script
Lecture 2: Trees: equivalent conditions.
Script
Tutorial 2: Trees: additional equivalent conditions. Minimum spanning tree.
Script
Lecture 3: Prim's algorithm.
Script
Tutorial 3: Kruskal's algorithm.
Script
Lecture 4: Flow networks. Ford-Fulkerson algorithm.
Script
Tutorial 4: Black-green trees. Flow network properties.
Script
Lecture 5: Dinitz algorithm.
Script
Tutorial 5: Applications of flow.
Script
Lecture 6: Dinitz algorithm (cont.)
Script
Tutorial 6: Applications of flow (cont.)
Script
Lecture 7: 0-1 networks.
Script
Tutorial 7: Networks with upper and lower limits.
Script
Lecture 8: Divide-and-conquer algorithms.
Script
Tutorial 8: Karatsuba algorithm. Strassen algorithm.
Script
Lecture 9: Fast Fourier Transform.
Script
Tutorial 9: Fast Fourier Transform: examples.
Script
Lecture 10: Randomized algortihms. Rabin-Miller agorithm for primality testing.
Script
Tutorial 10: Randomized polynomial testing. Karger algorithm.
Script
Lecture 11: Introduction to linear programming.
Script
Tutorial 11: Linear programming.
Script
Lecture 12: Simplex algorithm.
Script
Tutorial 12: Simplex algorithm in augmented tableau format.
Script
Lecture 13: Approximation algorithms. Vertex cover. Set cover.
Script
Tutorial 13: Travelling salesman problem.
Script
Lecture 14: Knapsack problem.
Script
Tutorial 14: Bin packing problem.
Script
Lecture 15: LP in approximation algorithms. Dual fitting.
Script
Tutorial 15: LP in approximation algorithms: rounding. Half-integrality of vertex cover.
Script
Videos of lectures and tutorials, fall 2014-2015
Lecture 1: Introduction into graph theory. Trees.
http://uttv.ee/naita?id=20257
Lecture 2: Prim's algorithm.
Prim's algorithm
http://uttv.ee/naita?id=20279
Lecture 3: Kruskal algorithm.
http://uttv.ee/naita?id=20414
Lecture 4: Flow in networks.
http://uttv.ee/naita?id=20529
Lecture 5: Dinitz algorithm.
http://uttv.ee/naita?id=20574
Lecture 6: Dinitz algorithm in 0-1 networks.
http://uttv.ee/naita?id=20601
Lecture 7: Flow networks with lower and upper limits (cont.) Multiplication of polynomials.
http://uttv.ee/naita?id=20641
Lecture 8: Fast Fourier Transform.
http://uttv.ee/naita?id=20659
Lecture 9: Probabilistic algorithms. Rabin-Miller algorithm for primality testing.
http://uttv.ee/naita?id=20701
Lecture 10: Karger's algorithm (cont.) Linear programming problems.
http://uttv.ee/naita?id=20729
Lecture 11: Simplex algorithm.
http://uttv.ee/naita?id=20787
Lecture 12: Simplex algorithm: degeneracy example. Approximation algorithms. Vertex Cover problem.
http://uttv.ee/naita?id=20897
Lecture 13: Travelling Salesman Problem in directed graphs.
http://uttv.ee/naita?id=20950
Lecture 14: PTAS for the bin packing problem.
http://uttv.ee/naita?id=21036
Lecture 15: Primal-dual algorithms. Primal-dual approach to set cover.
http://uttv.ee/naita?id=21163
Tutorials
Tutorial 1: O()-notation. Comparison of complexity functions. Trees.
Tutorial 2: Properties of trees. Proof of correctness of Prim's algorithm.
http://uttv.ee/naita?id=20296
Tutorial 3: Minimum spanning trees.
http://uttv.ee/naita?id=20461
Tutorial 4: Min-cut max-flow theorem. Finding a maximum matching in a bipartite graph.
http://uttv.ee/naita?id=20530
Tutorial 5: Correctness of Dinitz algorithm. Finding vertex-disjoint path cover.
http://uttv.ee/naita?id=20575
Tutorial 6: Vertex cover in a bipartite graph. Flow networks with lower and upper limits.
http://uttv.ee/naita?id=20610
Tutorial 7: Divide an conquer: merge sort, Karatsuba algorithm, Strassen algorithm.
http://uttv.ee/naita?id=20656
Tutorial 8: Fast Fourier Transform: examples.
http://uttv.ee/naita?id=20671
Tutorial 9: Schwartz-Zippel lemma and polynomial identity testing. Karger's algorithm.
http://uttv.ee/naita?id=20708
Tutorial 10: Linear programming: primal and dual problems, weak and strong duality theorems.
http://uttv.ee/naita?id=20777
Tutorial 11: Simplex method using tableau format.
http://uttv.ee/naita?id=20859
Tutorial 12: Set Cover problem. Traveling Salesman problem.
http://uttv.ee/naita?id=20906
Tutorial 13: PTAS and FPTAS. Knapsack problem.
http://uttv.ee/naita?id=20957
Tutorial 14: Using LP in approximation algorithms. Dual fitting based proof for the set cover problem. Rounding algorithm for the set cover.
http://uttv.ee/naita?id=21088
Tutorial 15: Primal-dual approach to set cover (cont.)
http://uttv.ee/naita?id=21181