September 01, 2019 ⋅ 44 min read ⋅ Courses

Order the following functions in order of increasing asymptotic growth

- $n^{1/2}$
- $\frac{1}{8}n^{3}$
- $n^{3}-2n$
- $n^{2}-\sqrt{n}+7$
- $\frac{1}{2}n-n^{\frac{1}{2}}$
- $\frac{n^{2}}{n^{0.6}}$
- $\sqrt{n^{3}}$
- $7n-13$
- $83$
- $\sqrt[3]{n} + 20$

One way of comparing algorithms is by comparing their asymptotic growth. Increasing order

- $83$
- $\sqrt[3]{n} + 20$
- $n^{1/2}$
- $7n-13 \equiv \frac{1}{2}n-n^{\frac{1}{2}}$
- $\frac{n^{2}}{n^{0.6}}$
- $\sqrt{n^{3}}$
- $n^{2}-\sqrt{n}+7$
- $\frac{1}{8}n^{3} \equiv n^{3}-2n$

Theorem: $f_{1}(n)\ \epsilon\ O(g_{1}(n))$ Def: $O(g) = \{f:R \Rightarrow R\ |\ \exists n_{0} > 0, \exists c_{2} > 0, f_{1}(n) \leq c_{2}g_{1}(n)\ for\ all\ n \geq n_{0}\}$

- The purpose of $c_2$ is to say that no matter what value of $c_{2}$ is used, $f_{1}(n)$ will always be smaller than $g_{1}(n)$.
- $c_{2}g_{1}(n)$ will always be slower than or equal to $f_{1}(n)$ above the threshold of $n_{0}$ where $n_{0}$ is
~~the intersection between~~$f_{1}(n)$~~and~~$g_{1}(n)$; correction: where $n_{0}$ is an arbitrarily chosen constant. - $n_{0}$ and $c_{2}$ are correlated.

notion | idea | interpretation | pronunciation |
---|---|---|---|

$o(g)$ | $<$ | f grows strictly slower than g | little-oh |

$O(g)$ | $\leq$ | f grows no faster than g | big-oh |

$\theta(g)$ | $=$ | f grows as fast as g | theta |

$\Omega(g)$ | $\geq$ | f grows no slower than g | big-omega |

$\omega(g)$ | $>$ | f grows strictly faster than g | little-omega |

Ex: If $f_{1}(n) = n^{2}$, $g_{1}(n) = n^{3}$, then $f_{1}(n)\ \epsilon\ O(g_{1}(n))$. Proof: Let $n_{0} = 1$ and $c_{2} = 1$.

Def: $o(g) = \{f, \forall c_{2}>0, \exists n_{0} > 0, 0 \leq f(n) \leq c_{2}g(n)\ for\ all\ n \geq n_{0}\}$.

- No matter how much we speed up algorithm $g$ (speed up comes in the form of $c_{2}$), the algorithm $f$ will always be faster once the input size is big enough (the threshold comes in the form of $n_{0}$.

Ex: If $f_{1}(n) = n^{2}$, $g_{1}(n) = n^{3}$, then $f_{1}(n)\ \epsilon\ o(g_{1}(n))$. Proof: Let $n_{0} = 500$ and $c_{2} = \frac{1}{500}$, then we want $n^{2} \leq c_{2}n^{3}$. Given $c_{2}$, set $n_{0} = \frac{1}{c_{2}} + 1$ so there is always a threshold for any given speedup. The plus one is just to guarantee the threshold but it could be any number added.

- Theta is a combination of big-oh and big-omega; it isn’t faster and isn’t slower, it’s the same.
- $c_{1}$ is the slow down factor, $c_{2}$ is the speedup factor.

Properties of big-O

- $f\ \epsilon\ o(g) \Rightarrow f\ \epsilon\ O(g)$. If $f$ is strictly slower than $g$, then $f$ is slower (no faster) than $g$.
- $f\ \epsilon\ \omega(g) \Rightarrow f\ \epsilon\ \Omega(g)$.
- $f\ \epsilon\ O(g)\ \&\ f\ \epsilon\ \Omega(g) \Leftrightarrow f\ \epsilon\ \Theta(g)$.
- $f\ \epsilon\ O(g) \Leftrightarrow g\ \epsilon\ \Omega(f)$.
- $f\ \epsilon\ \Theta(g) \Leftrightarrow g\ \epsilon\ \Theta(f)$.
- $f\ \epsilon\ o(g) \Leftrightarrow g\ \epsilon\ \omega(f)$.

- Logs come from cutting the search space usually in half hence $log_2()$.
- We assume all logs have base 2.
- Theorem: $\forall a, b > 1, n > 0, log_{a}(n)=\frac{log_{b}(n)}{log_{b}(a)}$. Lets you switch the log base.
- Examples
- $7log(n)\ \epsilon\ \Theta(log(n))$
- $(log(n))^{7}\ \epsilon\ \omega(log(n))$
- $log(7^{n}) = n\ log(7)\ \epsilon\ \Theta(n)$

- Theorem: $\forall a, b > 0, \lim_{n\to\infty} \frac{(log(n))^{b}}{n^{a}} = 0$
- The intuition is that the top is faster than the bottom.
- Any log-power is smaller than any polynomial.

- Examples
- $(log(n))^{2}\ \epsilon\ o(n)$
- $(log(n))^{2}\ \epsilon\ o(\sqrt{n})$
- $(log(n))^{7}\ \epsilon\ o(n^{1/100})$
- $(log(n))^{2}\ \epsilon\ o(\frac{n}{(log(n))^{2}})$

- Ordering example
- $\frac{n}{log\ n}$
- $log\ n$
- $\sqrt n$
- $log(log\ n)$
- $(log\ n)^{2}$
- $n$
- $\sqrt{log\ n}$
- $(log\ n)(log\ log\ n)$
- $\frac{n}{(log\ n)^{2}}$
- $\frac{(log\ n)^{2}}{n}$ (Not an algorithm)

- Answer in increasing growth order
- $\frac{(log\ n)^{2}}{n}$
- $log(log\ n)$
- $\sqrt{log\ n}$
- $log\ n$
- $(log\ n)(log\ log\ n)$
- $(log\ n)^{2}$
- $\sqrt{n}$
- $\frac{n}{(log\ n)^{2}}$
- $\frac{n}{log\ n}$
- $n$

- One helpful tip for ordering algorithms is to cancel the same terms on both sides.
- Theorem: $log(n!)\ \epsilon\ \Theta(n\ log(n))$
- Suppose we have a deck of cards, we want to find some permutation where they’re sorted.
- The search space is $n!$ and applying $log()$ to it means we split the search space in half for every iteration.
- $n! \leq n^{n}$, then log both sides to get $log(n!) \leq n\ log(n)$ which is the big-O bound of the theorem.
- $n! = n \cdot (n-1) \cdot (\frac{n}{2} + 1)(\frac{n}{2})...1 \geq (\frac{n}{2})^{\frac{n}{2}}$, then log both sides to get $log(n!) \geq \frac{n}{2}log(\frac{n}{2})$ which is the big-Theta bound of the theorem.

- An algorithm transforms an input into an output by performing some transformation on the input.
- What is an efficient algorithm?
- An algorithm that is fast. Doesn’t have to be optimal.
**An algorithm is efficient if it runs in polynomial time in the input size. (Will show up on final exam)**

- $2^{n} < n! < n^{n}$
- Poly logs, subpolys, polys are efficient. Super polys, exps, and superexps aren’t efficient. (For exams, if asked for an efficient algorithm, then it must be in the first three groups).

- Proof techniques
- Our greedy algorithm never makes a bad choice.
- Our greedy algorithm always makes a good choice.
- Our greedy algorithm stays ahead.
- Our greedy algorithm is on the way to produce an optimal.
- At any stage r during the computation subset Ar can be extended to an optimal solution.

- Pieces of Candy
- You can pick 4 pieces of candy.
- We want to maximize the total weight of candy.
- Greedy heuristic: Always pick the heaviest remaining piece.

- Greedy algorithms are typically simple and can be stated in one line.
- Candy pickings
- Input: Integers $n,\ k$ with $1\leq k\leq n$. Weights $w_{1}, w_{2}, ..., w_{n}$.
- Output: Heaviest subset $A \subseteq \{1, 2, ..., n\}$ of size k. $weight(A) = \sum_{i\ \epsilon\ A} w_{i}$.
- Theorems
- Our algorithm produces a valid solution.
- Our algorithm produces an optimal solution.
- Our algorithm runs in polynomial time.

- Proof
- What we want: Subset $A_{r}$ can be extended to an optimal solution for all $0 \leq r \leq k$. (If we can proof this then we are done).
- Proof by contradiction. Assume there is some $j$ such that $A_{j}$ can’t be extended to an optimal solution. Aka assume there’s a state that can’t be extended to an optimal solution.
- Let $r = smallest\ j$ such that $A_{j}$ can’t be extended to an optimal solution.
- $A_{0} = \{\} \cup \{9, 4, 8, 10\}$ where $\{9, 4, 8, 10\}$ is an extension that would lead to an optimal solution.

- $A_{1} = \{9\} \cup \{4, 8, 10\}$
- $A_{r-1} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{b_{r}, b_{r+1}, ..., b_{n}\}$ where $\{b_{r}, b_{r+1}, ..., b_{n}\}$ is an extension that would lead to an optimal solution.

- $A_{r} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{a_{r}\}$ ← The step where we made a mistake aka we can’t extend to an optimal solution.
- Fact 1: $\bar{A_{r}} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{a_{r}\} \cup \{b_{r+1}, b_{k}\}$
- Observation 1: $\bar{A_{r}}$ has size $k$ so it is a valid set.

- The indices $\{a_{1},..., a_{r-1}, a_{r}\}$ are all distinct because the greedy algorithm picks only distinct indices by definition of our greedy algorithm.
- The indices $\{a_{1}, ..., a_{r-1}, b_{r+1}, ..., b_{k}\}$ are distinct because it’s part of an optimal solution by definition.
- The index of $a_{r}$ is distinct from $\{b_{r+1}, ..., b_{k}\}$ because had it been one of them, then $A_{r}$ could have been extended.

- Fact 1: $\bar{A_{r}} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{a_{r}\} \cup \{b_{r+1}, b_{k}\}$
- $A_{r-1}^{*} = \{a_{1}, ..., a_{r-1}\} \cup \{b_{r}\} \cup \{b_{r+1}, ..., b_{k}\}$ is an optimal solution.

- $\bar{A_{r}} = \{a_{1}, ..., a_{r-1}\} \cup \{a_{r}\} \cup \{b_{r+1}, ..., b_{k}\}$ is our greedy solution.
- Fact 2: We want to argue $value(\bar{A_{r}}) \geq value(A_{r-1}^{*})$ by arguing that $weight(a_{r}) \geq weight(b_{r})$.
**We know that**$weight(a_{r}) \geq weight(b_{r})$**because the greedy algorithm picks the heaviest among the remaining pieces.**- From Fact 1 and Fact 2, we can conclude that $\bar{A_{r}}$ is a valid and optimal solution. That is a contradiction to our assumption that $A_{r}$ can’t be extended to an optimal solution.

- Proof by contradiction is the same as proof by induction.

- Interval scheduling
- Input: Set of n jobs. Each job has a starting time $s_{i}$ and a finishing time $f_{i}$.
- Output: Select as many non-overlapping jobs as possible.

- Approaches
~~Pick the shortest job of the next available jobs.~~~~Pick the next available job / job that starts first.~~- Pick the job that ends the first.
- Split ties arbitrarily.
- Among jobs that do not overlap already picked jobs.

- Answer to handout: {4, 11, 8, 1, 10}
- A good algorithm
- Outputs a valid solution.
- Outputs an optimal solution.
- Runs in poly time.

- For the interval scheduling GA
- By definition of the GA, we will never pick a job that overlaps so the solution is valid.
- The proof that it gives an optimal solution is given below.
- The GA is poly time as we can sort the job deadlines in $n log(n)$ time.
- Proof idea: GA never makes a bad choice (on our way to construct an optimal solution).
- Theorem: Subset $A_{s}$ can be extended to an optimal solution for all $0 \leq s \leq k^{*}$.
- Proof by contradiction.
- Assume there exists some $j$ such that $A_{j}$ cannot be extended to an optimal solution.
- Let $r$ be the smallest $j$ such that $A_{j}$ cannot be extended to an optimal solution. In other words, let $r$ be the first time we make a mistake.
- Then $A_{r-1} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{b_{r},...\}$ can be extended to an optimal solution but $A_{r} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{a_{r}\}$ cannot be extended.
- Let the extension be $\{b_{r}, b_{r+1},...,b_{k}\}$ be an optimal extension.
- We aren’t going to argue that $A_{r}$ is in the optimal extension because there might be multiple optimal solutions.
- We’re going to argue that $A_{r}$ can be extended to an optimal solution to contradict our assumption.
- Because $A_{r}$ is the greedy choice, we know that $a_{r}$ will end before or at the same time as $b_{r}$.
- Then extend $A_{r}$ by $\{b_{r+1}, ..., b_{k}\}$ but the extension is not necessarily valid because $a_{r}$ and $b_{r+1}$ could overlap.
- The solution to this problem is to sort the optimal extension and to replace the earliest job with the greedy choice. Let $b_{r}$ be the job that finishes the earliest among jobs $\{b_{r}, b_{r+1}, ...\}$.
- There’s a greedy choice and that choice can be substituted into an optimal extension.

- Dijkstra’s Greedy Algorithm
- For all $u\ \epsilon\ V$, set $d(u) = \infty$. Set $S_{0}=\{s\}$, $d(s)=0$, $A_{0}=\{\}$.
- For $k=1$ to $n-1$, do
- Find $v\ \epsilon\ V\ not\ in\ S$ with $min\{d(u) + l(u,v)\}$ ← Greedy choice
- Set $d(v) = d(u) + l(u,v)$, $S_{k}=S_{k-1} \cup \{v\}$, $A_{k} = A_{k-1} \cup \{(u,v)\}$

- Single source shortest path problem
- Input: Directed graph $G=(V,E)$, connected source $s\ \epsilon\ V$. Non-negative weights for each edge.
- Goal: A shortest path from s to every other vertex $v\ \epsilon\ V$.

- Solution is a tree rooted at s.
- GA is to grow a shortest-path tree.
- The proof depends on choosing paths that we will never regret.
- Proof
- We only pick edges that we’ll never regret.

- Kruskal algorithm
- Presort edges $e_{1}, e_{2},...,e_{m}$ so that $c(e_{1}) \leq c(e_{2}) \leq c(e_{m})$ where $c(...)$ is the cost of the edge.
- $F_{o} = \{\}$, $k=0$
- For i = 1 to m
- If $F_{k} \cup \{e_{i}\}$ is acyclic then $F_{k+1} = F_{k} \cup \{e_{i}\}$ and $k=k+1$.

- Return $F_{k}$ and $k_{gr}$ where $k_{gr} = k$.

- Minimum Spanning Tree (MST)
- Undirected graph with non-negative edge costs.

- Trees are paths that are unique paths.
- A spanning tree has n - 1 edges.
- A tree contains a unique path from every vertex to every other vertex.
- If we add an edge to a spanning tree, then we introduce a unique cycle.
- One GA to obtain the MST is to remove the edge with the greatest cost without making the graph disconnected.
- Kruskal’s Heuristic
- Pick the cheapest cost edge that doesn’t introduce a cycle.

- Whenever we have a cycle, we can remove the edge with the most cost.
- Theorem: Kruskal’s algorithm outputs a MST. (Assume Kruskal’s alg outputs a tree)
- Proof by contradiction.
- Assume there is some $k$ such that $F_{k}$ can’t be extended to an optimal solution. Aka Kruskal’s algorithm made a mistake.
- Let r = smallest such k. So $F_{r-1}$ can be extended to an optimal solution but $F_{r}$ can’t.
- Let $F_{r-1}^{*} = F_{r-1} \cup \{e_{r},...,e_{n-1}\}$ be the optimal solution and $F_{r} = F_{r-1} \cup \{e_{x}\}$ be the set where we made the mistake.
- Because of the greedy choice, the edge GA picked must be at least the same cost as the optimal solution.
- So we can extend $F_{r}$ to an optimal solution by $\bar{F_{r}} = (F_{r-1} \cup \{e_{x}\} - \{e_{y}\})$.

- Huffman Codes
- Input: A set of n symbols. $S = \{s_{1}, s_{2}, s_{n}\}$ with frequencies $f_{1}, f_{2}, f_{n}$.
- Output: An optimal prefix-free code over {0, 1} for those frequencies

- Example
- Message (M) = “appletrees”
- StdEnc(M) = 01.1.1.00.0.000.10.0.0.11 ← Not an accurate encoding because the decimal is a third symbol.
- Prefix-free code: a code that is unambiguous by having each encoding not have the same prefix.

symbol | frequency | standard encoding (std enc) |
---|---|---|

e | 3 | 0 |

p | 2 | 1 |

l, a, r, s, t | 1 | 00, 01, 10, 11, 000 |

- Observation 1: More frequently used characters should be have a shorter encoding. $f_{i} > f_{j} \rightarrow \lvert E(s_{i}) \rvert \leq \lvert E(s_{j}) \rvert$
- A prefix-free code is a binary tree.
- Swap leaves to get higher frequencies closer to the root.
- If you keep swapping subtrees until no longer possible, then we get an optimal prefix-free code.
- In practice, the tree is built bottom up.
- GA means I can locally find an improvement.
- If it seems that I can make a local improvement, then GA will probably apply.

- Recurrences
- Mergesort ($\Theta(nlog(n))$)
- $T(2)=1$
- $T(n)=2T(\frac{n}{2})+n$

- Bubblesort ($\Theta(n^{2})$)
- $T(1)=0$
- $T(n)=T(n-1)+n$

- Binary search ($\Theta(log(n))$)
- $T(1)=1$
- $T(n)=T(\frac{n}{2})+1$

- Integer multiplication ($\Theta(n^{log_{2}(3)}) \approx \Theta(n^{1.57})$)
- $T(1)=1$
- $T(n)=3T(\frac{n}{2})+1$

- Mergesort ($\Theta(nlog(n))$)
- Multiplication of complex numbers
- Input: (a + bi)(c + di)
- Output: (ac - bd) + (bc + ad)i

- Faster algorithm for multiplying two complex numbers
- 3 multiplications (1 at r, 1 at s, 1 at t)
- 5 additions/subtractions (2 at r, 2 at e, 1 at f)

```
r = (a + b)(c + d) = ac - bd + bc - ad
s = bc
t = ad
e = ac - bd = r - s + t
f = ad + bc = s + t
```

- Multiplication of large integers
- $ab * cd$ where a is the upper half of the bit string, b is the lower half of the bit string, and ab is the entire number represented as a bit string.
- $(a \cdot 2^{n/2} + b)(c \cdot 2^{n/2} + d)$
- $(ac)2^{n} + (ad + bc)2^{n/2} + bd$ where $2^{n}$ and $2^{n/2}$ are shifts.
- Apply the same trick when multiplying two complex numbers.
- Requires 3 multiplications, 4 additions, and 2 shifts.

- When explaining recursion, describe the recursive step, not the entire process. Avoid using iteration to describe recursion. E.g. For all, for each, etc.
- Matrix multiplication
- For each entry in the answer matrix, it requires $O(n)$ operations so constructing the entire answer matrix requires $O(n^{3})$ since $n \cdot n^2 = n^3$.
- Recursive method
- Split each matrix into quadrants.

- Mergesort recurrence: $T(n) = 2T(n/2) + n + n$
- $2T(n/2)$ because we split the input in half and we have to sort two subarrays.
- $+ n + n$ because we divide the array and later merge it

- Example
- $[7, 3, -11, 5, 4, -3, 7, 2, -9, -8, 12, -2]$
- Sample output: $[5, 4, -3, 7, 2] = 15$.

- Brute force is $\Theta(n^{3})$ because we try all starting indices and all ending indices. Getting the starting and ending indices is $n^{2}$ and getting the indices between them is $n$.
- D&C is to split the array into two subarrays and to calculate the largest sum of those subarrays. We also need to care for the case when the solution crosses the border.
- We ask each subarray for its
- Largest subarray
- Largest subarray touching the dividing border
- Largest subarray touching its edges
- Total sum

- Each subarray returns four pieces of information.
- Whatever I ask my children, I must also give to my parent.
- The largest sum of an array must come from three cases
- The left subarray
- The right subarray
- A combination of the left and right subarray

- Runtime of $T(n) = 2T(n/2) + \Theta (n) + \Theta(1)\ \epsilon\ \Theta(n log n)$
- Dividing is linear time if we copy the array into two subarrays.
- Merging is clearly constant time $\Theta(1)$. We need to compute 4 numbers from 8 numbers.

- $T(n) = 2T(n/2) + \Theta (1) + \Theta(1)\ \epsilon\ \Theta(n)$
- If the division were constant time, then the algorithm would be linear. It can be if we pass indices for the start and end of the subarray instead of copying.

- Master Theorem
- Let $T(n) = aT(n/b) + f(n)$ where $a$ is the number of subproblems, $b$ is the size of each subproblem, and $f(n)$ is the cost of dividing and merging.
- Depth = $log_{b}(n)$.

- Input: n points $(x_{1}, y_{1}), ..., (x_{n}, y_{n})$
- Output: the two closest points
- $\{dist(p, p') = \sqrt{|x-x'|^2 + |y-y'|^2}\}$
- Trivial algorithm: $\Theta(n^2)$
- Now: $\Theta(n\ log(n))$
- Master theorem
- Case 1: Many leaves so the cost is mostly the leaves. More expensive to solve subproblems.
- Case 2: Leaves and root are the same cost. Same to solve subproblems.
- Case 3: Few leaves so the cost is mostly the root. Cheaper to solve subproblems.

- To solve for the closest points in a plane
- Divide the plane into half
- Find the half by presorting
- Solve each half recursively and deal with the border somehow
- Whatever we get as input, our children should get as input

- Algorithm

```
Presort (n log n Time)
P_x = all n points sorted with respect to x-axis
P_y = all n points sorted with respect to y-axis
Divide (Linear Time)
Q_x = left half of points sorted with respect to x-axis
Q_y = left half of points sorted with respect to y-axis
R_x = right half of points sorted with respect to x-axis
R_y = right half of points sorted with respect to y-axis
Merge
d = min(d_left, d_right)
d_final = min(d_left, d_right, d_border)
```

- We want to merge in linear time to get n log n time.
- Discard all points that are delta (d) away from the border.
- We use P_y to get the points closer to the border in linear time.

- D&C = Recursion with non-overlapping
- DP = Recursion with overlapping subproblems
- Develop recursively
- Implement iteratively

- Don’t use memoization because it doesn’t speak enough about recursion.
- Master theorem
- $f(n)$ is the cost of the root, $n^{log_b(a)}$ is the cost of the leaves.
- Master theorem doesn’t apply to non-polynomial separated functions, only to poly-separated functions.

- Job selection
- Input: wages $w_1, w_2, ..., w_n$ (wages for 1 day of work)
- Output: Earn as much as possible
- Constraint: You cannot work 2 days in a row
- Examples
- E.g. $[4, 3, 2, 4, 1]$ (n = 5)
- Work on days 1 and 4 to earn 8.
- E.g. $[6, 9, 2, 1, 4, 5, 3]$ (n = 7)
- Work on days 2, 5, and 7 to earn 16.
- E.g. $[6, 9, 2, 1, 4, 5, 3, 4]$ (n = 8)
- Work on days 2, 4, 6, and 8 to earn 19.

- Greedy doesn’t work because we can’t extend the solution from n = 7 to n = 8.
- A small change at the end changes the solution so this is a global problem.
- Solution
- Recursively think about solving the subproblems.
- Either we work day n or we don’t work day n.
- If we work day n, then we can’t work day n - 1. Work optimally among the first n - 2 days.
- If we don’t work day n, then we work optimally among the first n - 1 days.
- We pick the better of the two conditionals.

- Proof
- Base case
- (n = 1) work day 1
- (n = 2) work the day with the higher wage

- The important idea is to ask what is the optimal value from the children.
- What value do you want from your children?
- $C[k]$ = optimal value we can earn among days $1, 2, ..., k$.
**CORE OF ALGORITHM**

- Base case
- $C[n] = max\{w_n + C[n-2], C[n-1]\}$. Either we work for wage $w_n$ or we don’t work.
- $C[k] = max\{w_k + C[k-2], C[k-1]\}$ for $k \geq 3$.

- $C[2] = max\{w_1, w_2\}$
- $C[1] = w_1$

- Implementation (Bottom-Up)
- E.g. $[6, 9, 2, 1, 4, 5, 3, 4]$ (n = 8)
- Base case: $C = [6, 9]$
- Completed C: $C = [6, 9, 9, 10, 13, 15, 16, 19]$
- Output 19 as the total we will earn.
- Remember to output a value from your algorithm.

- Weighted Interval Scheduling
- We can make a small change to the problem (changing a weight to infinity) that changes the entire solution.
- Think in terms of the number of jobs (n), not the number of days (d).
- Solution
- Presort the intervals with respect to finishing time. (Break ties arbitrarily)
- Either we work job n and earn wage w
- Work optimally among jobs that finishes before job n starts.

- Or we don’t work job n and don’t earn w
- Work optimally among jobs 1, …, n-1

- $C[n]$ = maximum amount we can earn among jobs 1 through n.

- $C[k]$ = max amount we can earn among jobs 1 through k ($k \geq 1$)
- Either we work job n so: $w_n + max_j\{C[j] \vert f_j \leq s_n\}$ (we want to maximize the wage for jobs that finish before n starts)
- Or we don’t work job n so: $C[n-1]$ (work optimally among $n-1$ jobs)
- Then we take the max of both cases to get $C[n]$.
- $C[1] = w_1$ for the base case.

- Our algorithm developed today is not poly-time.
- Problem
- Input
- n items
- weights $w_1, w_2, ..., w_n$
- values $v_1, v_2, ..., v_n$.
- Knapsack of capacity W

- Output
- Fill knapsack with as valuable load as possible (not overfill)

- Example
- (w=10, $25), (w=15, $30), (w=20, $80), (w=30, $100)
- Knapsack of size 45
- An optimal solution: $\{1, 2, 3\}$. The optimal value: $135

- Solution
- Either we pick item n
- The knapsack capacity changes. Remaining capacity is $W - w_n$ where $W$ is the knapsack capacity before we chose n. If it doesn’t fit then don’t consider it.
- We earn the the value of n plus the optimal value among 1 to $n-1$.

- Or we don’t pick item n
- Earn optimally among items 1 to $n-1$.
- Remaining capacity doesn’t change.

- $C[n, W]$ = maximum value in knapsack of capacity $W$ among items 1 through n.

- Either we pick item n
- $C[k, T]$ = maximum value in knapsack of capacity $T$ among items 1 through k.
- A 2D array where the rows are the number of items and the columns are the capacity of the knapsack.
- Populating the array takes $\Theta(n \cdot W)$ which is not poly-time. Poly-time means an algorithm that runs in polynomial time on the input size. It’s actually exponential.
- $C[n, W] = max(C[n-1, W- w_n] + v_n (either\ case), C[n-1,W] (or\ case))$
- $C[k, T] = max(C[k-1, T-w_k] + v_k (either\ case), C[k-1,T] (or\ case))$
- Base cases
- 0 capacity = 0 value
- 0 items = 0 value

- DP = Recursion

- Input

- Longest common subsequence
- Input: Two string X and Y of lengths n and m. $X = x_1, x_2, ..., x_n$ and $Y = y_1, y_2, ..., y_n$.
- Output: Length of a LCS of X and Y.
- A subsequence, Z, of a string can be obtained by deleting some symbols in the string.
- Examples
- X = dynamic, Y = static, Z = aic
- X = algorithms, Y = matchings, Z = aths

- Solution
- LCS($X_a, X_b$) = LCS(X, Y) (if $a = b$) or LCS($X_a, Y$) or LCS($X, Y_b$) (if $a \neq b$)
- LengthLCS($X_a, X_b$) = lengthLCS(X, Y) + 1 (if $a = b$) or max{lengthLCS($X_a, Y$), lengthLCS($X, Y_b$)} (if $a \neq b$)
- $LCS(X, \epsilon) = \epsilon$, $LCS(\epsilon, Y) = \epsilon$, $lengthLCS(\epsilon, Y) = 0$, $lengthLCS(X, \epsilon) = 0$.

- Starting from the end/back of X and Y. Recursively apply the following function.
- If the end symbols match, then remove the end symbols and call this algorithm again.
- If the end symbols don’t match, then call this algorithm twice. Once on the full first string and the second string with the end symbol removed, and once on the first string with the end symbol removed and the full second string.
- Subproblem is a prefix of X and a prefix of Y.
- $C[i,j]$ = value of the subproblem $LCS(x_1, ..., x_i, y_1, ..., y_j)$.

- The storage of the subproblem solutions is a 2D array where the rows are prefixes of Y and the columns are prefixes of X. Each cell holds the length of the LCS of $x_1, ..., x_i$ and $y_1, ..., y_j$. The output is the value at the top right of the 2D array.
- Number of subproblems is $\Theta(nm)$ because subproblems is $(n+1)(m+1)$. Since each subproblem takes constant time, the runtime is $\Theta(nm)$.

- Printing the LCS

```
PrintLCS(C, n, m, X, Y) # Call subroutine
PrintLCSRec(C, i, j, X, Y): # Define subroutine
if i == 0 or j == 0:
return
if C[i, j] == "Diagonal":
PrintLCSRec(C, i - 1, j - 1, X, Y)
print(X[i])
elif C[i, j] == "Horizontal":
PrintLCSRec(C, i - 1, j, X, Y)
else:
PrintLCSRec(C, i, j - 1, X, Y)
```

- Matrix Chain Multiplication
- Input
- matrices $A_1, A_2, .., A_n$
- integer n
- dimensions $p_0, p_1, ..., p_n$. (Matrix $A_i$ has dimensions ($p_{i-1}, p_i$))

- Output
- the fastest way (order of multiplication) to compute the product $B = A_1 A_2 ... A_n$.

- Dimensions of B $(p_0, p_n)$, $A_1$ $(p_0, p_1)$, $A_2$ $(p_1, p_2)$, … $A_n$ $(p_{n-1}, p_n)$.
- Cost of multiplying two matrices, one of $(p, q)$ and one of $(q, r)$, is $pqr$.
- Example
- $A_1 (4, 6), A_2 (6, 2), A_3 (2, 2), B (4, 2)$
- Two multiplications: $(A_1 A_2)A_3$ or $A_1(A_2 A_3)$.
- The first one costs 64, the second one costs 72. So the first chain multiplication is cheaper.

- The key insight is that there’s a last multiplication, we just don’t know where.
- Last multiplication
- $Cost(A_{1-n}) = min\{cost(A_{1-k}) + cost(A_{(k+1)-n}) + (p_0p_kp_n)\}$ where $1 \leq k \leq n - 1$.

- The cost equation is the smallest cost to compute the product $(A_1A_2...A_n)$.
- General cost: $Cost(A_{i-j}) = min\{cost(A_{i-k}) + cost(A_{(k + 1) - j}) + (p_{i-1}p_kp_j)\}$ where $i \leq k \leq j - 1$.
- Base cases: $Cost(A_{i-i}) = 0$ where $1 \leq i \leq n$.

- Solution storage: $C[i, j] = cost(A_{i-j})$ which is a 2D array.
- Rows are j, columns are i.
- Output the cell at i = 1 and j = n so $C[1, n]$.
- Base cases are the diagonal so we get a diagonal of zeros.
- We don’t use half of C (bottom-right triangle) because i must be less than j.
- We fill out C diagonally.
- Solving one cell in C requires the solutions down and right.
- It takes $\Theta(n)$ per cell for $\Theta(n^2)$ cells so the algorithm takes $\Theta(n^3)$.

- Input

- Problem 1 Asymptotics
- $f_1 = n log_4(n)$
- $f_2 = 4 log_2(n)$
- $f_3 = n^4$
- $f_4 = n^{1/4}$
- $f_5 = 2^{log_4(n)} = n^{log_4(2)} = n^{0.5}$

- Running Times
- $S(n) = S(\sqrt{n}) + \frac{n}{2} \approx n$ > $T(n) = T(\frac{n}{2}) + \sqrt{n} \approx \sqrt{n}$
- $S(n) = 4S(\frac{n}{2}) + nlog(n) \approx n^2$ > $T(n) = 8T(\frac{n}{4}) + nlog(n) \approx n^2$
- $S(n) = log(n!) \approx nlog(n)$, = $T(n) = 3T(\frac{n}{3}) + n \approx nlog(n)$
- $S(n)=S(\frac{n}{2})+S(\frac{n}{2}$