Design and Analysis of Algorithms 2024/25 fall

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
Algorithm for finding an augmenting path

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.pdf
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