Applied Algorithms (CS 602)

Fall 2026

Course Information:

Instructors       Teaching Assistants

Sujoy Bhore                       Himanshi Singh, Devdan Dey, Vedapalli Hemanth Venkata

Arpit Agarwal         

Lectures       Office Hours

Venue: KR 125             Thursday, 5-6 PM.

Timings: Tue. 2-3:30 PM, Fri. 2-3:30 PM. 

Course description:  This course offers a rigorous and interactive study of the fundamental concepts, design paradigms, and analytical techniques that form the modern algorithmic toolkit. It emphasizes both the theoretical foundations needed to establish correctness and efficiency and the problem solving insight required to model complex computational problems and apply these techniques effectively.

Course Contents (tentative): 

• • Metric Traveling Salesman Problem. 

  • Metric Steiner Tree. 

  • PTAS for Euclidean TSP. 

  • Set Cover and Max Coverage. 

  • Max-Cut, SDP, Rounding/integrality gaps. 

  • 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 Policy: Mid sem (35), End Sem (40), Two assignments (20). Class Participation (5).