1. Design and Analysis of Algorithms [CSC 403].

Topics taught: (Coming soon) 

References:

1. Books:

• Introduction to Algorithms (Second and Third Edition), Cormen et. al. (CLRS), Publisher: PHI.
• Algorithm Design, Kleinberg and Tardos, Publisher: Pearson.
• Algorithms (Fourth Edition, part I), Sedgewick and Wayne, Publisher: Addison-Wesley Professional.

2. Lecture notes:

• COS 226, Princeton University Course on Algorithms and Data Structures Fall 2012 (1 up version). (https://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures.php)
• Introduction to Algorithms 6.046J/18.401J (Lecture slides). (www.cs.virginia.edu/~robins/cs6161/slides/Cormen_Algorithms_Slides.pdf)
• A Second Course in Algorithms (CS261, winter 2016), Tim Roughgarden, Stanford University. (https://theory.stanford.edu/~tim/notes.html)

3. Video lectures:

• CSE-IITKGP NMEICT T10KT
• UHMICSAlgorithms
• https://www.youtube.com/watch?v=pRnKTFo1zss&list=PLtkAfVCgA693fNJCZkdFqs0awgynxmcAa
• https://www.youtube.com/watch?v=5Y8Lfsreeck&list=PL7DC83C6B3312DF1E
• MIT OpenCourseWare
• https://www.youtube.com/watch?v=kiFfp-HAu64

2. Game Theory and its applications (2019-20) [CS 9042]

Lessen Plan:

• Lecture 1: Introduction to Game Theory (definition, strategies, some motivating examples such as Prisoner's Dilemma, house allocation problem, auction) and Some general guidelines discussed (such as COs of the course, How they can map it with POs, We will use Google Classrooms and Gradescopes for assignments and grade evaluation to asses the students)
• Lecture 2: Introduction to Game Theory (more motivating examples such as voting, recommendation system, peer-to-peer system etc. and discussion of jargons such as Pareto optimality, Strategyproofness etc.), Some proof of these concepts in terms of DRAW algorithm discussed.
• Lecture 3: Concepts on DRAW continued. Some of the varients of DRAW and its propoerties (strategyproofness, Pareto-optimality etc.) discussed. Rules of the game matters.
• Lecture 4: One sided market vs Two sided market. House allocation and Kidney exchange problems are at length. TTCA algorithm with examples and their properties. Stable matching problem is introduced with examples.
• Lecture 5 and 6: Stable matching: (Two sided market is discussed), Motivations of the algorithm explained with serveral application scenerios (medical internships for students, law students for clerkship, stable marriage etc.), the model with mathematical formulation discussed. Deferred Acceptance algorithm discussed. two example scenerios are discussed - One when, the allocation remains same once allocated and the next when, once allocated, they improve over time by a possible rejection from the other side. Definition and why stability is important are discussed. Existence of stable matching with the proof (proof by contradiction). Multiple stable matching and its examples are discussed. More properties of Diferred Acceptance Algorithm (DAA) are discussed (such as Pareto optimality). Either side optimality with proof discussed. Key take-away of the two lectures: How to make a trade-off between two sides of the market. One side strategyproofness is discussed, if other side is misreporting, then what might happen is discussed. More reading and thinking: Is this existing admission system in India, at ny level is good? Can we do better with our algorithms discussed.  
•  Lecture 7: Voting in Computer Science: Motivation - Google Page Rank, Crowdsourcing, Participating Democracy. Majority Rule - Definition, implementation, Whether it is strategyproof or not with proof is discussed, Proof for Pareto optimal is given for exercise. Plurality Rule: Definition, Algorithm, an Example, It is not strategyproof proved by counter example, Falasy of democracy, Exercise: Find a bad example for this (One is given in the class).
• Lecture 8: First class test taken (10 Marks), Ranked Choice Voting is discussed with its properties of strategyproofness and NP-Hardness, Borda count is discussed with its properties and applications.
• Lecture 9: Question: Can the voting rules be efficient (for example strategyproof?), Arrow's impossibility Theorem and Gibbard-Saterthwaite Theorem discussed in the context of this questions. How to bypass these two theorems: Single-peaked preferences is discussed and Strategyprrof median voting rule is discussed

    Resources:

•  N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007, ISSN: 978-0521872829.
• T. Roughgarden, CS364A: Algorithmic Game Theory Course (Stanford University), 2013.
• T. Roughgarden, CS269I: Incentives in Computer Science Course (Stanford University), 2016.

3. Advanced Algorithms.

   Resources (Coming soon)

4. Special Interest

1.  Learning Manim created by Grant Sanderson of 3Blue1Brown. Maybe Manim is the future.