2024-02-08

Thursday, February 8th, 2024

Gratitude makes sense of our past, brings peace for today, and creates a vision for tomorrow.

— Melody Beattie

ECS165A Lecture

• pin is a latch to secure data structure level; latches are internal control mechanism; see https://stackoverflow.com/a/42464336
• pin guarantees that while the page is read, the page doesn’t become corrupted (suddenly replaced with another page or written with something else)
• lock is at the logical
• Modified pages require setting a dirty bit to true. When evicting dirty pages, they must be written to disk first.
• For crash recovery, we need to have a write-ahead log to ensure that dirty pages can be recovered if database crashes before the they are saved.

ECS122A Lecture

Greedy Proof Review

• greedy proof components that will be tested
  • greedy strategy proof (required for quiz 3)
  • optimal substructure proof (not required for quiz 3, but is required for midterm 2)
• greedy strategy proof (using breakpoint problem as an example)
  • step 1: state the greedy algorithm
    • example: choose the breakpoint furthest (such that the resulting set of breakpoints is smallest) from the current breakpoint that is still reachable (i.e. still has enough fuel left), i.e. $|bp-x|\le c$
  • step 2: define the optimal solution $S$ (i.e. as a set of choices/decisions)
    • example: Let $S=\left\{p_1,p_2,\dots ,p_r\right\}$ be the optimal solution. Size of $S$ is minimum, where $p_1=0$ (starting point) and $p_r=b_n$
  • step 3: define the “first” greedy choice (let’s refer to it as $a_1$)
    • example: Let $a_1$ be the greedy choice of the greedy strategy
      • We know $a_1-0\le c$ (starting from 0)
  • stet 4: prove that a new solution $A=S-\left\{S_1\right\}+\left\{a_1\right\}$ is still optimal
    • Why is $a_1\ge S_2$? It’s by definition of the greedy strategy, because it is the furthest possible from 0 that is still under $c$.
    • We know $S_3-S_2\le c$ by the definition of optimal solution.
    • We can have $-a_1\le -O_2$ (multiply both sides by -1), then ew can add $S_3$ to both sides
    • $S_3-a_1\le S_3-O_2\le c$ by transitive property
    • $a_1$ is reachable from $S_1$ by definition of greedy strategy (all under $c$).
    • $S_3$ is reachable from $a_1$ since $S_3-S_2\le c$
    • So $a_1$ has to be as optimal as $S_2$.
• optimal substructure proof (using breakpoint problem as example)

Dynamic Programming

• memoization: store solutions to smaller problems
• example: recursive Fibonacci sequence, but recursive calls are cached
• rod cutting problem
  • given
    • length $n$ of a rod we’re trying to sell
    • market prices for rods for lengths from 1 to $n$
  • goal
    • chop the rod into multiple segments such that the total sale revenue is maximum (assuming chopping is free)
  • bruteforce
    • $O(2^n\cdot n)$
    • iterate over all possible places to chop

DP solution to rod cutting problem

runtime: $O(n^2)$

step 1: state problem via recurrence - assume we know the optimal cut for a length $n$ is $x$ (inches), we know opt(n) = p[x] + opt(n-x) where p is an array of market prices. step 2: state general case of problem:

$$opt(i)=\underset{x\in [\mathrm{1..}i]}{\max }p[x]+opt(i-x)$$

step 3: bottom-up memoization r[i] is the optimal revenue for a rod with length $i$. We can build this array from 0 to $n$.

$$r[i]=\underset{x\in [\mathrm{1..}i]}{\max }p[x]+r[i-x]$$

Base cases: r[i]=p[1], r[0]=0. Building r[i] takes $O(n)$ (iterate from 1 to $i$). We need to build from r[0] to r[n] (also $O(n)$) So combined the DP solution takes only $O(n^2)$.

To actually output the best cuts, we need to have another array s, where s[i] stores the optimal cut for a rod of length $i$. This allows us to trace back all the cuts taken to get from $n$ to the most granular. For example, starting at a length of $n$, once s is calculated, we can use s[n] to get the first winning cut, s[n-s[n]] to get the next winning cut, etc.

Proof of correctness of DP algorithms only requires the optimal substructure proof in this class (i.e. subset of an optimal solution is optimal for its corresponding subproblem).

Proof (greedy strategy proof)

Given: opt cut strategy from rod length $n$

$$opt=\left\{x_1,x_2,\dots ,x_r\right\}$$

Prove: set $A=opt-\left\{x_1\right\}$ is optimal cut strategy for rod of length $n-x_1$.

Proof by contradiction

Assume $A$ is not optimal cut. There exists strategy B that is optimal for rod length $n-x_1$. `rev(B) > rev(A)