Lecture 15: Primal-dual algorithms. Primal-dual approach to set cover.
<iframe width="560" height="315" src="https://www.uttv.ee/embed?id=21163" frameborder="0" allowfullscreen></iframe>
Advanced methods in algorithms.
Tutorial 2: Properties of trees. Proof of correctness of Prim's algorithm. 12.09.14
Tutorial 3: minimum spanning trees. 26.09.14
01.10.14
03.10.14
Lecture 5: Dinitz algorithm. 08.10.14
Tutorial 5: Correctness of Dinitz algorithm. Finding vertex-disjoint path cover. 10.10.14
Lecture 6: Dinitz algorithm in 0-1 networks. 15.10.14
Tutorial 6: Vertex cover in a bipartite graph. Flow networks with lower and upper limits. 17.10.14
Lecture 7: Flow networks with lower and upper limits (cont.) Multiplication of polynomials.
Tutorial 7: Divide an conquer: merge sort, Karatsuba algorithm, Strassen algorithm.
Lecture 8: Fast Fourier Transform.
Tutorial 8: Fast Fourier Transform: examples.
Lecture 9: Probabilistic algorithms. Rabin-Miller algorithm for primality testing.
Tutorial 9: Schwartz-Zippel lemma and polynomial identity testing. Karger's algorithm.
Lecture 10: Karger's algorithm (cont.) Linear programming problems.
Lecture 11: Simplex algorithm.
Tutorial 11: Simplex method using tableau format.
Lecture 12: Simplex algorithm: degeneracy example. Approximation algorithms. Vertex Cover problem.
Tutorial 12: Set Cover problem. Traveling Salesman problem.
Lecture 13: Travelling Salesman Problem in directed graphs.
Tutorial 13: PTAS and FPTAS. Knapsack problem. 05.12.14
Lecture 14: PTAS for the bin packing problem.
Tutorial 14: Using LP in approximation algorithms. Dual fitting based proof for the set cover problem. Rounding algorithm for the set cover.
Tutorial 15: Primal-dual approach to set cover (cont.)
Parema kasutuskogemuse tagamiseks kasutame küpsiseid. UTTV veeb ei töötle ega kogu isikuandmeid. UTTV kasutab Google Analyticsi teenust. Loe lähemalt andmekaitsetingimustest.
