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. (Slides)

Lecture 2 Video (Dynamic Programming, Matrix Chain Multiplication)

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

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 (Dynamic Programming, Longest Common Subsequence)  

This lecture is on Dynamic Programming, where we study the Longest Common Subsequence Problem. (Slides)

Lecture 4 Video (Greedy Algorithm, Activity Selection)

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

Lecture 5 Video (Greedy Algorithm, Huffman Codes)

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

Lecture 6 Video (Amortized Analysis, Aggregate Analysis, Accounting Method)

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

Lecture 7 Video (Amortized Analysis, Potential Method) 

This lecture introduces the "Potential Method" for amortized analysis. (Slides) 

Lecture 8 Video (Online Algorithms, Elevator or Stairs)

This lecture introduces online algorithms, where we study the "Elevator or Stairs" problem. (Slides)  

Lecture 9 Video (Online Algorithms, Maintaining a Search List)

This lecture introduces online algorithms, where we study the "Maintaining a Search List" problem. (Slides)  

Lecture 10 Video (Representation of Graphs, BFS)

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

Lecture 11 Video (DFS)

This lecture introduces DFS (Depth First Search). (Slides) 

Lecture 12 Video (Topological Sort)

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

Lecture 13 (Strongly Connected Components)

This lecture introduces the "Strongly Connected Components" problem. It is solved using DFS. (Slides)  

Lecture 14 Video (MST)

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

Lecture 15 Video (Single Source Shortest Paths) 

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

Lecture 16 Video (NP Completeness: Part 1)

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

Lecture 17 Video (NP Completeness: Part 2)

This lecture defines NP-completeness and introduces related concepts. (Slides)

Lecture 18 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. (Slides)  

Lecture 19 Video (NP Completeness: Part 4)

This lecture shows how to prove the Hamiltonian Cycle Problem is NP-complete. (Slides) 

Lecture 20 Video (NP Completeness: Part 5)

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

Lecture 21 Video (Approximation Algorithms: Part 1)

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

Lecture 22 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. (Slides)  

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 23 Video (Approximation Algorithms: Part 3)

This lecture studies an approxmation algorithm for the Set Covering Problem. (Slides)  

Lecture 24 Video (Approximation Algorithms: Part 4)

This lecture studies an approximation algorithm for the Subset Sum Problem, which is an FPTAS. (Slides)  

Lecture 25 Video (Maximum Flow: Part 1)

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

Lecture 26 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. (Slides)   

Lecture 27 Video (Maximum Bipartite Matching)

This lecture studies the Maximum Bipartite Matching Problem, which is solved using the Hopcroft-Karp Algorithm. (Slides)   

Lecture 28 Video (Hungarian Algorithm for Assignment Problem)

This lecture studies a bipartite matching problem called the "Assignment Problem", which is solved using the Hungarian Algorithm. (Slides)  

Lecture 29 Video (Linear Programming: Part 1)

This lecture introduces linear programming and its basic concepts. (Slides) 

Lecture 30 Video (Linear Programming: Part 2)

This lecture introduces the SIMPLEX algorithm. (Slides)

Lecture 31 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. (Slides)

Lecture 32 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. (Slides)

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.