# Linear programming and its applications to computer science

- Institution: IIT Kanpur
- Department: Computer Science and Engineering
- Teacher: Prof. Rajat Mittal
- Level: Undergraduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106104356)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106104356)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

Linear programming is a special class of mathematical optimization problems where the constraints as well as the cost function is linear. This class of problems have known efficient algorithms, deep structural properties and wide applications in various fields.

In this course we not only introduce and learn about linear programming, but also see its uses in different areas of computer science (algorithms, algorithmic game theory, theoretical computer science, machine learning).

Intended audience: Senior undergraduate (3rd or 4th year) and masters/phd students in CSE

Prerequisites: Linear algebraBasic Linear Algebra - https://nptel.ac.in/courses/111101115Linear Algebra - https://nptel.ac.in/courses/111104137https://nptel.ac.in/courses/111106135

## Lectures

1. [Lecture 1 : Linear programming, an example](https://invisiblenetwork.ai/learn/nptel/106104356/80df1fbf4c8f) (YouTube)
2. [Lecture 2 : Introduction to linear programming](https://invisiblenetwork.ai/learn/nptel/106104356/57b4f02e6492) (YouTube)
3. [Lecture 3 : Gaussian elimination with examples](https://invisiblenetwork.ai/learn/nptel/106104356/489cb71909bf) (YouTube)
4. [Lecture 4 : Summary of Gaussian elimination](https://invisiblenetwork.ai/learn/nptel/106104356/34836a95c8e0) (YouTube)
5. [Lecture 5: Vector space over real numbers](https://invisiblenetwork.ai/learn/nptel/106104356/3d949b042000) (YouTube)
6. [Lecture 6: Linear operators](https://invisiblenetwork.ai/learn/nptel/106104356/f6e1afb9fe86) (YouTube)
7. [Lecture 7: Solutions of linear equations](https://invisiblenetwork.ai/learn/nptel/106104356/e24523e2138d) (YouTube)
8. [Lecture 8: Resource allocation as LP](https://invisiblenetwork.ai/learn/nptel/106104356/e2801b254feb) (YouTube)
9. [Lecture 9: Approximate degree as LP](https://invisiblenetwork.ai/learn/nptel/106104356/333e585afd88) (YouTube)
10. [Lecture 10: Equivalent LP's](https://invisiblenetwork.ai/learn/nptel/106104356/53b2c38a2fd9) (YouTube)
11. [Lecture 11: Introduction to convexity](https://invisiblenetwork.ai/learn/nptel/106104356/8a0968fc2d17) (YouTube)
12. [Lecture 12: Different kind of convex sets](https://invisiblenetwork.ai/learn/nptel/106104356/14a4843b5f7b) (YouTube)
13. [Lecture 13: Feasible region of LP](https://invisiblenetwork.ai/learn/nptel/106104356/7bdb6e7c4ad4) (YouTube)
14. [Lecture 14: Proof of Weyl's theorem](https://invisiblenetwork.ai/learn/nptel/106104356/0595673ec304) (YouTube)
15. [Lecture 15: Definition of convex functions](https://invisiblenetwork.ai/learn/nptel/106104356/d2a42541f303) (YouTube)
16. [Lecture 16: Properties of convex functions and examples](https://invisiblenetwork.ai/learn/nptel/106104356/fe906f76cb68) (YouTube)
17. [Lecture 17: Basic feasible solution](https://invisiblenetwork.ai/learn/nptel/106104356/855bae7e3bd9) (YouTube)
18. [Lecture 18: BFS and vertices](https://invisiblenetwork.ai/learn/nptel/106104356/667a2f2957ad) (YouTube)
19. [Lecture 19: Simplex algorithm](https://invisiblenetwork.ai/learn/nptel/106104356/78e92429a981) (YouTube)
20. [Lecture 20: Details of simplex algorithm](https://invisiblenetwork.ai/learn/nptel/106104356/3e25e224a8d4) (YouTube)
21. [Lecture 21: Starting BFS](https://invisiblenetwork.ai/learn/nptel/106104356/9eae4d63b097) (YouTube)
22. [Lecture 22: Degeneracy](https://invisiblenetwork.ai/learn/nptel/106104356/2c1a15e65cf7) (YouTube)
23. [Lecture 23: Introduction to duality](https://invisiblenetwork.ai/learn/nptel/106104356/15d7b6a3a838) (YouTube)
24. [Lecture 24: Hyperplane separation theorems](https://invisiblenetwork.ai/learn/nptel/106104356/58bc52bd325e) (YouTube)
25. [Lecture 25: Farkas Lemma](https://invisiblenetwork.ai/learn/nptel/106104356/3e967eea22bf) (YouTube)
26. [Lecture 26: How to take dual](https://invisiblenetwork.ai/learn/nptel/106104356/3a1be52ddf19) (YouTube)
27. [Lecture 27: Examples of taking dual](https://invisiblenetwork.ai/learn/nptel/106104356/c657c6ed1367) (YouTube)
28. [Lecture 28: Strong Duality](https://invisiblenetwork.ai/learn/nptel/106104356/8d5a0976b353) (YouTube)
29. [Lecture 29: Proof of strong duality](https://invisiblenetwork.ai/learn/nptel/106104356/237dd5134fe1) (YouTube)
30. [Lecture 30: Complementary slackness](https://invisiblenetwork.ai/learn/nptel/106104356/17a583d37ce3) (YouTube)
31. [Lecture 31: Introduction to algorithmic game theory](https://invisiblenetwork.ai/learn/nptel/106104356/6cc4d7f1b48e) (YouTube)
32. [Lecture 32: Nash equilibrium](https://invisiblenetwork.ai/learn/nptel/106104356/836ba1ff77d1) (YouTube)
33. [Lecture 33: Minimax and Nash equilibrium](https://invisiblenetwork.ai/learn/nptel/106104356/cc2eaba2ca1b) (YouTube)
34. [Lecture 34: Deterministic communication complexity](https://invisiblenetwork.ai/learn/nptel/106104356/25520061d1a4) (YouTube)
35. [Lecture 35: Randomized communication complexity](https://invisiblenetwork.ai/learn/nptel/106104356/6fd5398276a6) (YouTube)
36. [Lecture 36: Yao's minimax theorem](https://invisiblenetwork.ai/learn/nptel/106104356/ace7e2d1c88b) (YouTube)
37. [Lecture 37: Lower bounds using Yao's minimax](https://invisiblenetwork.ai/learn/nptel/106104356/25ad43f23aa9) (YouTube)
38. [Lecture 38: Set disjointness problem](https://invisiblenetwork.ai/learn/nptel/106104356/8cd1d0fe5a47) (YouTube)
39. [Lecture 39: LP for max flow problem](https://invisiblenetwork.ai/learn/nptel/106104356/354254a0029d) (YouTube)
40. [Lecture 40: LP for min cut problem](https://invisiblenetwork.ai/learn/nptel/106104356/581d91f42cfc) (YouTube)
41. [Lecture 41: max flow = min cut](https://invisiblenetwork.ai/learn/nptel/106104356/6cce37f76fe8) (YouTube)
42. [Lecture 42: Primal dual approach](https://invisiblenetwork.ai/learn/nptel/106104356/6104d2c4e9ae) (YouTube)
43. [Lecture 43: Primal dual for max flow](https://invisiblenetwork.ai/learn/nptel/106104356/5f5b3f738730) (YouTube)
44. [Lecture 44: Set cover problem](https://invisiblenetwork.ai/learn/nptel/106104356/c893e097791d) (YouTube)
45. [Lecture 45: Rounding for set cover](https://invisiblenetwork.ai/learn/nptel/106104356/c1719f4ea466) (YouTube)
46. [Lecture 46: Analysis of rounding](https://invisiblenetwork.ai/learn/nptel/106104356/35603ceae6c1) (YouTube)
47. [Lecture 47: Algorithm for set cover](https://invisiblenetwork.ai/learn/nptel/106104356/74acc3fa4dac) (YouTube)
48. [Lecture 48: Linear regression through LP](https://invisiblenetwork.ai/learn/nptel/106104356/09334d187853) (YouTube)
49. [Lecture 49: Linear classifiers through LP](https://invisiblenetwork.ai/learn/nptel/106104356/27129acb27be) (YouTube)