Applied Algorithms (CS 602)

Schedule: Tuesday, 3:30-5. Friday, 3:30-5. 

Venue:  CC 103

Pre-requisites: Expected to know basics of algorithms and data structures (CS 218/601), discrete math, graph theory. 

Course Contents: 

• Approximation Algorithms: 

  • Geometric independent set, set cover, hitting set, Traveling salesman problem, clustering (k-center/k-median), embedding, Steiner tree, etc. 

• Parameterized Algorithms: 

  • Introduction, basic kernelization, color coding, parameterized approximation algorithms: FPT-approximation, lossy kernelization, bidimensionality, etc.

• Advanced Data Structures:

• Geometry: orthogonal range search, point location, approximate nearest neighbors/LSH.

• Graphs: dynamic connectivity, dynamic reachability, approximate distance oracles.

• Other models: succinct data structures, external memory, streaming/sketching.

• Selected Topics from Online Algorithms. 

Learning Objectives: This course aims to equip students with the skills to design efficient algorithms.  We will explore various advanced algorithm design techniques and demonstrate how these techniques can be applied to solve different algorithmic problems. The course focuses on the mathematical aspects of algorithm design.

Selected Readings:  

1. David B. Shmoys and David P. Williamson, The Design of Approximation Algorithms.

2. Marek Cygan et al., Parameterized Algorithms. 

3. Vijay Vazirani, Approximation Algorithms, Springer, 2003.

4. Niv Buchbinder and Joseph Naor The design of competitive online algorithms via a primal-dual approach

5. Also, I'll provide links to relevant references. 

Grading: Grades will be based on a mid-sem (25%), a final (30%), two assignments (40%), and class participation (5%).