Course code | COL756 |

Instructor | Ashish Chiplunkar |

Teaching Assistant | Ajay Soni |

Classes | Tuesday, Wednesday, Friday 10:00 - 11:00 (Slot E) |

Office hour | TBD |

- Linear algebra: Vector spaces, linear independence, span, basis and dimension, linear transformations, matrices and their inversion
- Discrete mathematics: specifically, graph theory
- Algorithms: Shortest path, min-weight spanning tree, maxflow-mincut

- Linear Programming Problems, the Geometry of Feasible Spaces and the set of Optima
- The Simplex Algorithm
- LP Duality and Complementary Slackness
- Application to Combinatorial Problems: Shortest Path, Min-weight Spanning Tree, Maxflow-mincut, Matchings, Min-Cost Flow
- The Ellipsoid Algorithm
- Semidefinite Programming and Goemans-Williamson Algorithm
- Convex Optimization, Lagrangian Dual, algorithms
- Extension Complexity

- "Combinatorial Optimization" by Christos H. Papadimitriou, Kenneth Steiglitz
- "Convex Optimization" by Stephen Boyd, Lieven Vandenberghe; available online

- Microsoft Teams for live lectures, tutorials, announcements, and exam proctoring
- Impartus for recorded lectures (see the 'Flipped Lectures' tab) and notes / slides (see the 'Backpack' tab)
- Gradescope for submitting homeworks and exams
- Piazza for discussions

Homeworks | 20% | To be done in groups of size ≤ 3 |

Minor exams | 40% | 2 minor exams. No compensation for missed exams except for medical reasons, in which case a doctor's certificate must be submited. |

Major exam | 40% |

30% marks are necessary and sufficient for a passing grade, both in the credit as well as audit mode.