Background: The following lecture series will be conducted online. The lectures will be on Saturday evenings and Sunday mornings. These series are designed to give an introduction to advanced topics in algorithms and theoretical computer science. The lectures will not be recorded. Moreover, the teaching will be done using a digital board, therefore, no or minimal slides will be used.
Eligibility: Any UG / PG student, who has preferably completed a basic course in Data Structures and/or Algorithms and is willing to dedicate time and learn advanced topics! A faculty person or industry person is welcome too!
Who will conduct?: Ms. Girija Limaye (email: reach<dot><surname><at><gmail>)
Registration: There is no registration fee but registration is mandatory.
Registration is closed on April 25. If you are genuinely interested, please drop me an email.
Theme 1
Topics: Beyond NP-completeness: Approximation algorithms
Tentative date and time: May 13, 2023, 6pm--8.30pm and May 14, 2023, 10am--12.30pm
Details: A tentative list of topics is as follows.
A discussion / warm-up about the computational problems, the classes P and NP and the famous P vs. NP question, ways to deal with NP-completeness
Introduction to approximation algorithms
Designing simple approximation algorithms
Introduction to advanced techniques
Introduction to hardness of approximation
Theme 2
Topics: Network flow and Matchings
Tentative date and time: May 20, 2023, 6pm--8.30pm and May 21, 2023, 10am--12.30pm
Details: A tentative list of topics is as follows.
Network flow, max flow-min cut theorem and Ford-Fulkerson algorithm
Introduction to other algorithmic techniques for computing a max flow
Matchings in graphs, related terminologies and matching algorithms
Introduction to matchings under preferences
Stable matching and its variants