CS/ECE 374: Algorithms (I)

Spring 2020. (with Prof. Chan).

CS/ECE 374 covers fundamental tools and techniques from theoretical computer science, including design and analysis of algorithms, formal languages and automata, computability, and complexity. Specific topics include regular and context-free languages, finite-state automata, recursive algorithms (including divide and conquer, backtracking, dynamic programming, and greedy algorithms), fundamental graph algorithms (including depth- and breadth-first search, topological sorting, minimum spanning trees, and shortest paths), undecidability, and NP-completeness.

CS 473: Algorithms (II)

Spring 2018, Fall 2016 (with Prof. Chekuri).

A list of high-level topics that we hope to cover (this list is tentative): Divide and conquer, FFT. (Advanced) Dynamic Programming. Shortest path algorithms and negative cycle detection. Randomization in algorithms and data structures. Network flows and applications. Matchings. Basics of linear and convex programming. NP-Completeness and reductions. Basics of approximation and online algorithms.

CS 598 RM: Algorithmic Game Theory

Fall 2019, Fall 2018, Spring 2017 (Listed in the Instructors Rated as Excellent by Students @ U. of Illinois), Spring 2016

Algorithmic game theory has become more relevant than ever before with the advent of online markets, ad auctions, social networks, and recommendation systems, where rational agents interact to achieve selfish goals. The last two decades have witnessed the development of a rich theory in this area and deep mathematical connections have been established. The first half of the course will provide a broad introduction to games and market models, solution concepts, classical as well as recent developments in the field on equilibrium computation & complexity, mechanism design, price of anarchy, matching markets, game dynamics, and others. The second half will address a selection of advanced topics and research projects.

At Georgia Tech

Spring 2013

CS 8803: Advanced Topics in Algorithmic Game Theory
Co-taught with Jugal Garg and Georgios Piliouras

A research oriented course focusing on the intersection of computer science and game theory. During the first half of the course, the participants will be exposed to key ideas and results from algorithmic game theory. In the second part we will be exploring research tangents, looking into open questions and working on formulating novel problems.

Spring 2014

Equilibrium Computation.
Co-taught with Vijay V. Vazirani

Among the most novel and significant additions to the theory of algorithms and computational complexity over the last decade has been deep insights into the computability of equilibria, both Nash and market. In this course we will cover various algorithmic and hardness results for Nash and market equilibrium computation.