Lecture 1 Video (Dynamic Programming, Rod Cutting Problem, Time Complexity)

This is the video of Lecture 1. It covers the basics of Dynamic Programming, studies the Rod Cutting Problem in detail as an example of dynamic programming, and gives a brief overview of Time Complexity. 

Lecture 2 Video (Dynamic Programming, Matrix Chain Multiplication)

This lecture is on Dynamic Programming, where we study the Matrix Chain Multiplication Problem. 

Please note: at about 48 minutes 32 seconds of the video, on the whiteboard, "k* - 1" should have been written as "k* + 1." (It was a typo.)

Lecture 3 Video (Greedy Algorithm, Activity Selection)

This lecture introduces Greedy Algorithms, and uses the Activity Selection Problem as an example. 

Lecture 4 Video (Greedy Algorithm, Huffman Codes)

This lecture studies Greedy Algorithms, with the design of Huffman Codes as an example. 

Lecture 5 Video (Amortized Analysis)

This lecture introduces techniques of amortized analysis, including aggregate analysis and the accounting method, for analyzing time complexity. 

Lecture 6 Video (Representation of Graphs, BFS)

This lecture studies how to represent a graph, and the BFS (Breadth First Search) Algorithm. 

Lecture 7 Video (DFS)

This lecture introduces DFS (Depth First Search).

Lecture 8 Video (Topological Sort)

This lecture introduces the "Topological Sort Problem" for directed acyclic graphs. The problem is solved using DFS. 

Lecture 9 Video (MST)

This lecture studies the Minimum Spanning Tree (MST) problem. 

Lecture 10 Video (Single Source Shortest Paths) 

This lecture introduces the single source shortest path problem for directed graphs. 

Lecture 11 Video (Linear Programming: Part 1)

This lecture introduces linear programming and its basic concepts. 

Lecture 12 Video (Linear Programming: Part 2)

This lecture introduces the SIMPLEX algorithm. 

Lecture 13 Video (Linear Programming: Part 3)

This lecture reviews the SIMPLEX algorithm, proves its correctness using the duality between primal LP and dual LP, and discusses the possibility that the initial basic solution to a slack-form LP is not feasible. 

Lecture 14 Video (Linear Programming: Part 4)

This lecture studies how to determine if an LP is feasible, and how to find an initial feasible basic solution. 

Please note: at around 58 minutes 28 seconds of the lecture, on the board, in the question "what if x0 is a basic solution in the final slack form?", "basic solution" should be "basic variable." It was a typo.

Lecture 15 Video (NP Completeness: Part 1)

This lecture introduces basic concepts for the study of NP-completeness. 

Lecture 16 Video (NP Completeness: Part 2)

This lecture defines NP-completeness and introduces related concepts. 

Lecture 17 Video (NP Completeness: Part 3)

This lecture shows hows to prove a problem is NP-complete, using the Clique Problem and the Vertex Cover Problem as examples. 

Lecture 18 Video (NP Completeness: Part 4)

This lecture studies how to prove the NP-completeness of two problems: the traveling salesman problem and the subset sum problem. 

Lecture 19 Video (Approximation Algorithms: Part 1)

This lecture introduces approximation algorithms for the Vertex Cover Problem and the Traveling Salesman Problem (TSP). 

Lecture 20 Video (Approximation Algorithms: Part 2)

This lecture studies the hardness of approximating the general traveling salesman problem (general TSP), the technique of using linear programming for approximation, and randomized algorithms. 

Note: at around 19 minutes 57 seconds of the video, what was written on the board should be "G has a Hamiltonian cycle of weight |V|", not G'. It was a small typo.

Lecture 21 Video (Maximum Flow: Part 1)

This lecture studies the maximum flow problem, and presents the Ford-Fulkerson method. 

Lecture 22 Video (Maximum Flow: Part 2)

This lecture proves the max-flow min-cut theorem and the correctness of the Ford-Fulkerson method, introduces the Edmonds-Karp algorithm, solves the maximum bipartite matching problem as an application of the maximum flow problem, and introduces how to formulate the maximum flow problem as a linear program. 

TBA

8/22/2023 (Tuesday):   

8/24/2023 (Thursday): 

8/29/2023 (Tuesday):  

8/31/2023 (Thursday):   

9/5/2023 (Tuesday): 

9/7/2023 (Thursday):  

9/12/2023 (Tuesday):  

9/14/2023 (Thursday): 

9/19/2023 (Tuesday):       

9/21/2023 (Thursday):    

9/26/2023 (Tuesday):    

9/28/2023 (Thursday):    

10/3/2023 (Tuesday):   

10/5/2023 (Thursday):     

10/10/2023 (Tuesday): Fall break. No class.

10/12/2023 (Thursday):     

10/17/2023 (Tuesday):  

10/19/2023 (Thursday):   

10/24/2023 (Tuesday):  

10/26/2023 (Thursday):   

10/31/2023 (Tuesday): 

11/2/2023 (Thursday): 

11/7/2023 (Tuesday):  

11/9/2023 (Thursday):   

11/14/2023 (Tuesday):    

11/16/2023 (Thursday):  

11/21/2023 (Tuesday):   

11/23/2023 (Thursday): Thanksgiving holiday. No class.

11/28/2023 (Tuesday):  

11/30/2023 (Thursday): 

Related Lectures: