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 (17.12)

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

    Vali tegevus
    Klipi teostus: Mirjam Paales 17.12.2014 3193 vaatamist Arvutiteadus


    Advanced methods in algorithms.

     

    Seotud videod

    Advanced Methods in Algorithms (03.09)
    03.09.14
    Advanced Methods in Algorithms (10.09)
    10.09.14
    Advanced Methods in Algorithms (12.09)

    Tutorial 2: Properties of trees. Proof of correctness of Prim's algorithm.
    12.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 (19.12)

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


    19.12.14