# Dynamic Programming
## Optimal Substructure
A problem $P$ is said to exhibit **optimal substructure** property if:
- Let $S$ be an optimal solution to problem $P$
- Then $S$ incorporates (i.e. contains) solution to the subproblems of $P$

Note that optimal substructure views the problem from having a big problem and use the subsolution (smaller solution) to solve the subproblems. This is slightly different from wishful thinking where it views of solution of subproblem can build up to solve a larger problem. (TLDR: optimal substructure is large-to-small, wishful thinking is small-to-large)

### Proving Optimal Substructure
- Assume you have optimal solution to the original problem
- Prove that the subsolution is also optimal to the subproblems
- Usually you can use cut-and-paste argument
- Cut-and-paste argument: "cutting out" the nonoptimal solution to each subproblem and "pasting in" the optimal one, you show that you can get a better solution to the original problem (a contradiction)

Refer to CLRS pg. 379

# Greedy
An algorithm that makes the best choice at the moment, i.e. it finds the local optimum, then do the same thing for smaller subproblem.

## Proving Correctness
You have to be able to prove two things:
- Optimal substructure
- Greedy choice property

## Greedy Choice Property
Prove that there exists an optimal solution $S$ to a problem $P$ such that it contains your choice as the solution.

Usually this is proven by:
- Assuming your choice $c$ is already in solution, then it's true
- If not, then you can swap things out, say $k \in S$. Swapping $k$ and $c$ does not make your solution worse.

# Maximum Flow
Given a simple directed graph $G = (V, E)$ without anti-parallel edges. Each edge has a capacity, where $c(u, v)$ denotes the capacity of edge $(u, v)$. Given a source $s$ and sink $t$. Determine the maximum flow from $s$ to $t$.

## Modelling

# Linear Programming