Applied Algorithms (CS 602)
Applied Algorithms (CS 602)
Sujoy Bhore Himanshi Singh, Devdan Dey, Ved Danait
Arpit Agarwal
Venue: CC 101. Thursday, 5-6 PM.
Timings: Tue. 3:30-5 PM, Fri. 3:30-5 PM.
Course description:
This course will offer a rigorous & interactive introduction to the fundamental concepts and techniques that define the modern algorithmic toolkit. It will emphasize both the theoretical foundations underlying these algorithms & the understanding needed to apply them effectively in practice.
Pre-requisites:
Expected to know basics of Algorithms and Data Structures (CS 218/601), Discrete Math, Graph Theory, and Linear Algebra.
Course Contents (tentative):
Metric Traveling Salesman Problem.
Metric Steiner Tree.
PTAS for Euclidean TSP.
Basics of Metric Embeddings, Applications.
Dimensionality reduction, Johnson-Lindenstrauss Lemma.
Approximate Nearest Neighbor Searches.
Clustering, Data Summarization.
Load Balancing, VC dimension & Applications.
Online Algorithms: Scheduling, Matching, Steiner tree.
Streaming Algorithms: Distinct elements, frequency moments, etc.
Online Learning with MWU, and Convex Optimization.
Reference Books:
The Design of Approximation Algorithms, David P. Williamson and David Shmoys.
Approximation Algorithms, Vijay Vazirani.
Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan.
Online Computation and Competitive Analysis, Allan Borodin and Ran El-Yaniv.
Data Streams: Algorithms and Applications, S. Muthukrishnan.
Foundations of Data Science, Avrim Blum, John Hopcroft, Ravindran Kannan.
Beyond the Worst-Case Analysis, Tim Roughgarden.
Grading: Based on mid-sem (25%), final (30%), two assignments (40%), and scribes (5%).