401 kms

What is Dynamic Programming?

Breaking problem into subproblems and reusing their solutions

What are the 3 parts of ANY DP problem?

1. Subproblem definition 2. Choices 3. Bellman equation

What is a Bellman equation?

Recurrence relation that builds the DP solution from subproblems

Template for solving DP problem?

1. Define subproblem DP[…] 2. Identify choices 3. Write Bellman eq 4. Set base case 5. Fill table

What is the DP subproblem in Knapsack?

Max value using first i items and budget w → DP[i][w]

Bellman equation for Knapsack?

If cost > w → DP[i

DP subproblem in Word Segmentation?

Max goodness of first i letters → DP[i]

Bellman equation for Word Segmentation?

DP[i] = max over j < i of DP[j] + goodness(j+1 to i)

Base case in DP?

Usually DP[0] = 0 or DP[0][0] = 0

Exam strategy for DP problems?

1. Define DP subproblem 2. Write Bellman eq 3. Set base case 4. Fill table step

Time complexity of Knapsack DP?

O(nC)

Time complexity of Bellman

Ford?

Algorithm to compute shortest paths to target node t in graph with negative edges

Reverse all edges. Run Bellman

How to store path info in Bellman

Ford?

How to print path from s to t?

Start at s, follow pred[] to t, print nodes on path

How do I find time complexity easily?

Count # of loops and how many things they touch. Multiply together.

Dynamic Programming (DP) problem meaning:

We solve small problems, store the answers, and build up to solve the big problem.

bellman equation for DP[i]?

DP[i] = max over j of (DP[j

BFS

A way to explore a graph by checking all neighbors first before going deeper (like ripples in water)

DFS

A way to explore a graph by going deep along one path before backtracking

Topological Sort

For tasks with dependencies, this puts tasks in order so each comes after its prerequisites

DAG Shortest Path

If tasks have no cycles, you can sort them and find shortest path super fast

Bipartite Graph

A graph where you can split nodes into 2 groups and edges only go between groups (not inside)

Check Bipartiteness

Color nodes with 2 colors. If it works without conflicts, graph is bipartite

Strongly Connected Components

A chunk where every node can reach every other node (in both directions)

Minimum Spanning Tree (MST)

Connects all dots with the least total wire (no loops, covers everything)

Kruskal’s Algorithm

Start with cheapest wires and keep adding until everything is connected

Prim’s Algorithm

Start from one dot and always add the cheapest wire going out

Interval Scheduling

Pick as many non

Interval Partitioning

Find out how many rooms you need to host all events (based on overlapping)

Scheduling to Minimize Lateness

Do the tasks with the earliest deadlines first to avoid being late

Huffman Coding

Compress text by giving short codes to common letters and long codes to rare ones

Coin Change Greedy

Keep taking biggest coins that fit the amount (works well with US coins, not always in weird coin systems)

Clustering (Greedy)

Group dots into k blobs by cutting the longest wires in MST

Optimal Caching

When your memory is full, throw out the item you won’t need for the longest time

Weighted Interval Scheduling DP

Choose best set of non

Knapsack DP

Pick items to fit in a backpack to get most value without going over weight limit

Sequence Alignment DP

Line up two sequences (like DNA or words) in the best matching way

Segmented Least Squares DP

Split data into chunks and fit best lines to balance accuracy + simplicity

RNA Secondary Structure DP

Find best way to match base pairs in RNA (A

Bellman

Ford DP

Distance Vector Protocol

Every computer updates its map of network distances by talking to neighbors

Merge Sort

Split list into halves, sort them, and merge back together

Count Inversions

Count pairs that are out of order by modifying merge sort

Master Theorem

Shortcut to solve problems where you split things into smaller chunks repeatedly

Closest Pair of Points

Split dots into halves, solve each, and check if closer pairs cross middle

Integer Multiplication (Karatsuba)

A faster trick to multiply big numbers by splitting into pieces

Matrix Multiplication

Split big grids into smaller grids and multiply faster

Convolution and FFT

Super fast way to multiply polynomials (used in signal processing too)

P

Problems computers can solve quickly (like sorting a list)

NP

Problems where if someone shows you a solution, you can check it quickly (like Sudoku)

EXP

Problems that take crazy long time to solve (exponential time)

NP

Complete

SAT

Can you set true/false values to make a big AND/OR puzzle true? (The first NP

3

SAT

Vertex Cover

Can you pick a small set of dots that touches all lines?

Clique

Can you find a group of dots where every pair is connected?

Subset Sum

Can you pick numbers from a list that exactly add up to target?

Reduction

A way to turn one problem into another to compare difficulty

co

NP

PSPACE

Problems that may take a long time but only need a little memory

Ford

Fulkerson Algorithm

Max

Flow Min

Bipartite Matching via Flow

Use flow tricks to match pairs (like students to projects)

Disjoint Paths via Flow

See if you can find k separate paths from point A to B without overlap

Project Selection

Choose set of projects to do that gives highest reward (use flow tricks)

Baseball Elimination

Check if a baseball team can still win based on remaining games (uses flow)

Asymptotic Notation (Big O)

Describes how fast an algorithm grows when input gets big (ignores small details)

Big O

Upper bound ("at worst, it’s this slow")

Big Omega

Lower bound ("it’s at least this fast")

Big Theta

Tight bound ("it’s exactly this speed")

O(1)

Instant, constant time

O(log n)

Tiny increase as input grows (like binary search)

O(n)

Linear, doubles if input doubles

O(n log n)

Fast

O(n²)

Slow for big data (like bubble sort)

O(2ⁿ)

Bad! Explodes fast (like brute force subsets)

Polynomial Time

Reasonably fast (n², n³ etc. is still manageable)

Exponential Time

Too slow to be useful for big inputs