Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog
  1. Advanced Algorithms
  2. Dynamic Programming
  • Advanced Algorithms
    • Greedy Algorithms
      • 1. Storing Files on a Tape
      • 2. A Scheduling Problem
      • 3. Stable Matchings
    • Matroids
      • 1. The Motivation
      • 2. The Definition
      • 3. Greedy Works!
      • 4. Scheduling with Deadlines
    • Dynamic Programming
      • 1. Longest Increasing Subsequence
      • 2. Subset Sum
      • 3. Set Cover
      • 4. Optimal BSTs
      • 5. Maximum Independent Set on Trees
    • Flows
      • 1. Flow-Cut Duality
    • Intractability
      • 1. Independent Set
    • Approximation
      • 1. Vertex Cover
      • 2. Set Cover
    • Randomized Algorithms
      • 1. Randomized QuickSort

Dynamic Programming

algonotes
lecturenotes
Published

June 16, 2023

Acknowledgements

I borrow the phrasing “what to store/how to compute” from my classroom experience at IMSc, specifically in a class taught by Venkatesh Raman. Some of the checklist is inspired by Erik Demaine’s treatment of the material in his MIT OCW course. The choice of problems is a subset of Jeff Erickson’s chapter on Dynamic Programming, and a lot of the notation is borrowed from there as well.

The dynamic programming approach to a problem involves miniaturizing the problem in a way that the pieces fit together to reveal a useful big picture — i.e, the answer you are after. Here’s the checklist:

  1. What are the fragments (AKA, what do we want to store)?
  2. Are the fragments going to be useful (AKA, where is the final answer)?
  3. Do we have a kickstart (AKA, what are the base cases)?
  4. How do the fragments come together (AKA, how do we compute the values that we have agreed to store)?
  5. Can we put the pieces together without getting stuck (AKA, are the dependencies in step #4 acyclic)?

Let’s execute this checklist on a few problems:

  1. Longest Increasing Subsequence
  2. Subset Sum
  3. Set Cover
  4. Optimal BSTs
  5. MIS on Trees

© 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

×