Computing Research for Smart Sustainable Cities

Teaching

Advanced Algorithms

Covering approximation algorithms, randomized algorithms, online algorithms, algorithmic game theory

Blockchain & Verifiable Computing

Coming soon ...

A Course in "Advanced Algorithms"

Lecture 1: Computational Complexity 101

Basics of computational complexity theory, NP-hardness

Lecture 2: Greedy Approximation Algorithms

Approximation algorithms for set cover problem, Steiner tree problem

Lecture 3: LP & Approximation Algorithms

Basics of linear programming, LP duality, primal-dual schema approximation

Lecture 4: Approximation for Knapsack Problems

Approximation algorithms for knapsack problems, PTAS, FPTAS

Lecture 5: Probability Theory & Computing 101

Basics of probability theory, Markov inequality, Chebyschev’s inequality, Chernoff bounds

Lecture 6: Hashing & Applications

Random data structures, hashing, Bloom filter, count-min sketch, balls-and-bins model

Lecture 7: Random Routing & Load Balancing

Random routing on hypercubes, power-of two-choices, Cuckoo hashing

Lecture 8: Online Algorithms I

Online algorithms for buy-or-rent problem, processor power management, market trading

Lecture 9: Online Algorithms II

Online algorithms for caching, k-server, metrical task systems, online dating problem, prophet inequality

Lecture 10: Online Learning & Machine Learning

Online learning algorithms for experts problem, linear classifiers, boosting

Lecture 11: PCP Theorem & Zero-Knowledge Proofs

PCP theorem, inapproximability, zero-knowledge proofs

Lecture 12: Algorithmic Game Theory I

Non-cooperative game theory, price-of-anarchy, congestion games, coalition formation games

Lecture 13: Algorithmic Game Theory II

Algorithmic mechanism design, VCG mechanisms, auctions