Current Time 0:00
Duration -:-
Loaded: 0%
Stream Type LIVE
Remaining Time -:-
 
1x
  • Chapters
  • descriptions off, selected
  • subtitles off, selected
    • Quality

    Advanced Methods in Algorithms (12.09)

    Tutorial 2: Properties of trees. Proof of correctness of Prim's algorithm.

    Vali tegevus
    Klipi teostus: Mirjam Paales 12.09.2014 4098 vaatamist Arvutiteadus


    Advanced methods in algorithms.

    Tutorial 2: Properties of trees. Proof of correctness of Prim's algorithm.

    Seotud videod

    Advanced Methods in Algorithms (03.09)
    03.09.14
    Advanced Methods in Algorithms (10.09)
    10.09.14
    Advanced Methods in Algorithms (24.09)
    24.09.14
    Advanced Methods in Algorithms (26.09)

    Tutorial 3: minimum spanning trees.
    26.09.14

    Advanced Methods in Algorithms (01.10)
    Lecture 4: Flow in networks. 

     
    01.10.14

    Advanced Methods in Algorithms (03.10)
    Tutorial 4: Min-cut max-flow theorem. Finding a maximum matching in a bipartite graph. 

     
    03.10.14

    Advanced Methods in Algorithms (08.10)

    Lecture 5: Dinitz algorithm.
    08.10.14

    Advanced Methods in Algorithms (10.10)

    Tutorial 5: Correctness of Dinitz algorithm. Finding vertex-disjoint path cover.
    10.10.14

    Advanced Methods in Algorithms (15.10)

    Lecture 6: Dinitz algorithm in 0-1 networks. 
    15.10.14

    Advanced Methods in Algorithms (17.10)

    Tutorial 6: Vertex cover in a bipartite graph. Flow networks with lower and upper limits. 
    17.10.14

    Advanced Methods in Algorithms (22.10)

    Lecture 7: Flow networks with lower and upper limits (cont.) Multiplication of polynomials.


    22.10.14
    Advanced Methods in Algorithms (24.10)

    Tutorial 7: Divide an conquer: merge sort, Karatsuba algorithm, Strassen algorithm. 


    24.10.14
    Advanced Methods in Algorithms (29.10)

    Lecture 8: Fast Fourier Transform.


    29.10.14
    Advanced Methods in Algorithms (31.10)

    Tutorial 8: Fast Fourier Transform: examples.


    31.10.14
    Advanced Methods in Algorithms (05.11)

     Lecture 9: Probabilistic algorithms. Rabin-Miller algorithm for primality testing. 


    05.11.14
    Advanced Methods in Algorithms (07.11)

    Tutorial 9: Schwartz-Zippel lemma and polynomial identity testing. Karger's algorithm. 


    07.11.14
    Advanced Methods in Algorithms (12.11)

    Lecture 10: Karger's algorithm (cont.) Linear programming problems. 


    12.11.14
    Advanced Methods in Algorithms (14.11)
    Tutorial 10: Linear programming: primal and dual problems, weak and strong duality theorems. 
     

    14.11.14
    Advanced Methods in Algorithms (19.11)

    Lecture 11: Simplex algorithm.


    19.11.14
    Advanced Methods in Algorithms (21.11)

    Tutorial 11: Simplex method using tableau format. 


    21.11.14
    Advanced Methods in Algorithms (26.11)

    Lecture 12: Simplex algorithm: degeneracy example. Approximation algorithms. Vertex Cover problem. 


    26.11.14
    Advanced Methods in Algorithms (28.11)

    Tutorial 12: Set Cover problem. Traveling Salesman problem. 


    28.11.14
    Advanced Methods in Algorithms (03.12)

    Lecture 13: Travelling Salesman Problem in directed graphs. 


    03.12.14
    Advanced Methods in Algorithms (05.12)

    Tutorial 13: PTAS and FPTAS. Knapsack problem. 
    05.12.14

    Advanced Methods in Algorithms (10.12)

    Lecture 14: PTAS for the bin packing problem. 


    10.12.14
    Advanced Methods in Algorithms (12.12)

    Tutorial 14: Using LP in approximation algorithms. Dual fitting based proof for the set cover problem. Rounding algorithm for the set cover.


    12.12.14
    Advanced Methods in Algorithms (17.12)

    Lecture 15: Primal-dual algorithms. Primal-dual approach to set cover. 


    17.12.14
    Advanced Methods in Algorithms (19.12)

    Tutorial 15: Primal-dual approach to set cover (cont.) 


    19.12.14