NOC:Linear Programming and its Applications to Computer Science

Lecture 1 - Linear Programming, an Example

Lecture 2 - Introduction to Linear Programming

Lecture 3 - Gaussian Elimination with Examples

Lecture 4 - Summary of Gaussian Elimination

Lecture 5 - Vector Space over real numbers

Lecture 6 - Linear Operators

Lecture 7 - Solutions of Linear Equations

Lecture 8 - Resource Allocation as LP

Lecture 9 - Approximate Degree as LP

Lecture 10 - Equivalent LP's

Lecture 11 - Introduction to Convexity

Lecture 12 - Different Kind of Convex Sets

Lecture 13 - Feasible Region of LP

Lecture 14 - Proof of Weyl's Theorem

Lecture 15 - Definition of Convex Functions

Lecture 16 - Properties of Convex Functions and Examples

Lecture 17 - Basic Feasible Solution

Lecture 18 - BFS and Vertices

Lecture 19 - Simplex Algorithm

Lecture 20 - Details of Simplex Algorithm

Lecture 21 - Starting BFS

Lecture 22 - Degeneracy

Lecture 23 - Introduction to Duality

Lecture 24 - Hyperplane Separation Theorems

Lecture 25 - Farkas Lemma

Lecture 26 - How to take dual

Lecture 27 - Examples of taking dual

Lecture 28 - Strong Duality

Lecture 29 - Proof of Strong Duality

Lecture 30 - Complementary Slackness

Lecture 31 - Introduction to Algorithmic Game Theory

Lecture 32 - Nash Equilibrium

Lecture 33 - Minimax and Nash Equilibrium

Lecture 34 - Deterministic Communication Complexity

Lecture 35 - Randomized Communication Complexity

Lecture 36 - Yao's Minimax Theorem

Lecture 37 - Lower bounds using Yao's Minimax

Lecture 38 - Set Disjointness Problem

Lecture 39 - LP for mass flow problem

Lecture 40 - LP for min cut problem

Lecture 41 - Max flow = Min cut

Lecture 42 - Primal dual approach

Lecture 43 - Primal dual for max flow

Lecture 44 - Set cover problem

Lecture 45 - Rounding for set cover

Lecture 46 - Analysis of Rounding

Lecture 47 - Algorithm for Set Cover

Lecture 48 - Linear Regression through LP

Lecture 49 - Linear Classifiers through LP