Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

CS 614 | Jan-Apr 2022

Advanced Algorithms
(A part of the IITM Online Undergraduate Program.)

June — August 2023
About the Course

This course will explores the tradeoffs involved in coping with NP-completeness.

When we think about designing algorithms, we are usually very demanding in how we go about it: we require our algorithms to be fast and accurate on all conceivable inputs. This is asking for quite a bit, and perhaps it is not surprising that we cannot afford this luxury all the time. The good news is that most of the time we can make meaningful progress by relaxing just one of these demands:

  1. Give up on accuracy, but not completely: look for solutions that are good enough (approximation) and/or work with algorithms that report the right solution most of the time (Las-Vegas style randomization).

  2. Give up on coverage, a little bit: let your algorithms work well on structured inputs. Hopefully the structure is such that it is not too limiting and is interesting enough for some application scenario, and is also enough to give you algorithmic leverage, i.e, there’s enough that you can exploit to make fast and accurate algorithms.

  3. Give up on speed, to some extent: going beyond the traditional allowance of polynomial time, which is the holy grail of what is considered efficient, takes you places. You could either allow for your algorithms have super-polynomial running times, and optimize as much as possible while being accurate on all inputs (exact algorithms), or allow for bad running times on a bounded subset of instances (Monte-Carlo style randomization).

This course is an introduction to techniques in achieving specific trade-offs, and understanding the theoretical foundations of frameworks that help us establish when certain tradeoffs are simply not feasible.

Fig. Exploring tradeoffs between the demands of accuracy, speed, and coverage.
Target Audience

Anyone who is biting their nails from the NP-completeness cliffhanger at the end of their introduction to algorithms will probably enjoy this course.

Prerequisites

This is a theoretical course that will require mathematical maturity (in particular, the ability to understand and write formal mathematical proofs), and some background in the design and analysis of algorithms. Programming experience is tangentially useful but not necessary.

References
  1. The Design of Approximation Algorithms • David P. Williamson and David B. Shmoys
  2. Parameterized Algorithms • Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh
  3. Randomized Algorithms • Motwani and Raghavan
  4. Beyond the Worst-Case Analysis of Algorithms • Tim Roughgarden
  5. Algorithms • Jeff Erickson
Timings and Venue

Online

Register

This course is meant for students of the IITM online BS program. If you are not enrolled in this program, but are interested in following along, please feel free to do so by going through the materials here. Send me an email if you would like to have access to the assignment problems.

  • Lectures
  • Weekly Practice
  • Exams
Date Lecture Slides Notes Video
03 Jun, 2023 1. Greedy Algorithms

• Storing Files on Tape I
• Storing Files on Tape II
• Scheduling Classes I
• Scheduling Classes II
• Stable Matchings I
• Stable Matchings II
• Stable Matchings III

10 Jun, 2023 2. Matroids

• A Generic Optimization Problem
• Motivating the Definition
• Greedy Works!
• Examples of Matroids I
• Examples of Matroids II
• Scheduling with Deadlines I
• Scheduling with Deadlines II

17 Jun, 2023 3. Dynamic Programming

• Longest Increasing Subsequence
• Edit Distance I
• Edit Distance II
• Subset Sum
• Optimal BSTs I
• Optimal BSTs II
• Optimal BSTs III

24 Jun, 2023 4. Maximum Flows

• Flows
• Cuts
• Maxflow-Mincut I
• Maxflow-Mincut II
• Augmenting Paths
• Bipartite Matchings
• Other Settings

01 Jul, 2023 5. Applications of Flows

• Exam Scheduling I
• Exam Scheduling II
• Baseball Elimination I
• Baseball Elimination II
• Baseball Elimination III
• Project Selection I
• Project Selection II

08 Jul, 2023 6. NP-hardness

• P, NP, NP-hardness, NP-completeness I
• P, NP, NP-hardness, NP-completeness II
• Reductions and SAT
• 3SAT
• Maximum Independent Set
• Graph Coloring
• Subset Sum

15 Jul, 2023 7. Approximation Algorithms

• Introduction to Approximation Frameworks
• Vertex Cover via Maximal Matchings
• Vertex Cover via LP rounding
• TSP
• Metric TSP
• Set Cover I
• Set Cover II

22 Jul, 2023 8. Randomized Algorithms

• Monte Carlo v. Las Vegas
• Min-Cut Algorithm
• MAX SAT via the Probabilistic Method I
• MAX SAT via the Probabilistic Method II
• 2SAT via Markov Chains I
• 2SAT via Markov Chains II
• Primality Testing

29 Jul, 2023 9. Exact Algorithms

• Branch and Bound
• An Inclusion-Exclusion approach to Hamiltonian Path I
• An Inclusion-Exclusion approach to Hamiltonian Path II
• Dynamic Programming for TSP I
• Dynamic Programming for TSP II
• Local Search I
• Local Search II

05 Aug, 2023 10. Parameterized Algorithms

• Closest String I
• Closest String II
• Iterative Compression for FVS I
• Iterative Compression for FVS II
• Randomized Algorithm for k-Path I
• Randomized Algorithm for k-Path II
• DP over subsets - Set Cover

12 Aug, 2023 11. Kernelization

• Vertex Cover I (High-degree rule)
• Vertex Cover II (LP-based Reduction)
• Matrix Rigidity
• Feedback Arc Set on Tournaments I
• Feedback Arc Set on Tournaments II
• Max Sat
• Edge Clique Cover

19 Aug, 2023 12. Practical Approaches to Coping with Hardness

• SAT Sovlers
• SAT reductions I
• SAT reductions II
• LP solvers
• LP reductions I
• LP reductions II

No matching items
Issued Assessment Problems Solutions Due
03 Jun, 2023 Greedy Algorithms

• Storing Files on Tape
• Scheduling Classes
• Stable Matchings

10 Jun, 2023
10 Jun, 2023 Matroids

• A Generic Optimization Problem
• Motivating the Definition
• Greedy Works!
• Examples of Matroids
• Scheduling with Deadlines

17 Jun, 2023
17 Jun, 2023 Dynamic Programming

• Longest Increasing Subsequence
• Edit Distance
• Subset Sum
• Optimal BSTs

24 Jun, 2023
24 Jun, 2023 Maximum Flows

• Flows
• Cuts
• Maxflow-Mincut
• Augmenting Paths
• Bipartite Matchings
• Other Settings

01 Jul, 2023
01 Jul, 2023 Applications of Flows

• Exam Scheduling
• Baseball Elimination
• Project Selection

08 Jul, 2023
08 Jul, 2023 NP-hardness

• P, NP, NP-hardness, NP-completeness
• Reductions and SAT
• 3SAT
• Maximum Independent Set
• Graph Coloring
• Subset Sum

15 Jul, 2023
15 Jul, 2023 Approximation Algorithms

• Introduction to Approximation Frameworks
• Vertex Cover via Maximal Matchings
• Vertex Cover via LP rounding
• TSP
• Metric TSP
• Set Cover

22 Jul, 2023
22 Jul, 2023 Randomized Algorithms

• Monte Carlo v. Las Vegas
• Min-Cut Algorithm
• MAX SAT via the Probabilistic Method
• 2SAT via Markov Chains

29 Jul, 2023
29 Jul, 2023 Exact Algorithms

• Branch and Bound
• An Inclusion-Exclusion approach to Hamiltonian Path
• Dynamic Programming for TSP
• Local Search

05 Aug, 2023
05 Aug, 2023 Parameterized Algorithms

• Closest String
• Iterative Compression for FVS
• Randomized Algorithm for k-Path
• DP over subsets - Set Cover

12 Aug, 2023
12 Aug, 2023 Kernelization

• Vertex Cover
• Matrix Rigidity
• Feedback Arc Set on Tournaments
• MaxSat
• Edge Clique Cover

19 Aug, 2023
19 Aug, 2023 Practical Approaches to Coping with Hardness

• SAT Sovlers
• SAT reductions
• LP solvers
• LP reductions

26 Aug, 2023
No matching items
Issued Assessment Problems Solutions Due
TBA Mid-Term Quiz

-
TBA Final Exam

-
TBA Practice Exam

-
No matching items

© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×