2024-02-18

Sunday, February 18th, 2024

How far that little candle throws its beams! So shines a good deed in a naughty world.

— William Shakespeare

• ECS165A Milestone 2 thoughts
  • Instead of storing page bytearray in Page objects, I’m more tempted to have Bufferpool act as a context manager that returns ReadonlyPage or ReadwritePage objects when read/write is requested.

ECS122A Lecture: DP continued

• knapsack problem
  • input: Set of items $S$ with items 1 - n. Each item $i$ has a value v[i] and weight w[i].
  • output: set of items $A\subset S$ with maximum value such that the total weight of items is under capacity $W$ of knapsack
  • recurrence solution
    • For each item, we can either take it or not take it.
    • opt(n, W) = max(v[n] + opt(n-1, W - w[n]), opt(n-1, W))
      • either take the item (and subtract weight), or find the opt without taking the item (weight stays the same)
  • DP solution
    • general solution: for items 1 to $i$ with bag capacity $j\le W$
      • opt(i, j): max(v[i] + opt(i - 1, j - w[i]), opt(i - 1, j))
      • depends on previous solutions for subset of items and lesser bag capacities
    • we can calculate this from bottom-up (calculate from i=1 to i=n)
      • let m[i, j] store opt(i, j)
    • we don’t need traceback (unlike rod problem)
      • for example, if $W=100$ and $n=20$, we can check if v[20] + m[19, W - w[20]] == m[20, W] to see if item 20 should be taken
    • code: $O(nW)$
      • for j = 1 to W:
        • for i = 1 to n
          • `m[i, j] = max(v[i] + m[i - 1, j - w[i]], m[i-1, j])
• longest common subsequence problem (LCS)
  • input: $X=⟨x_1,x_2,x_3,\dots ,x_n⟩$, $Y=⟨y_1,y_2,y_3,\dots ,y_m⟩$
  • output: longest subsequence $⟨z_i,\dots ,z_j⟩$ that is part of both $X_m$ and $Y_n$ (subsequences don’t have to be substrings and don’t have to be continuous; plus, each element’s position in $X$ and $Y$ don’t have to be the same/aligned, though the order of elements has to be preserved); for example lcs(xatttab, aggae) = aa
  • cases given $X$ of length $m$ and $Y$ of length $n$
    • lcs(m, n) = (X[m] == Y[n]) + lcs(m - 1, n - 1) (ignore both, and only adds 1 to LCS if $X_m=Y_n$)
    • lcs(m, n) = lcs(m, n - 1) (ignore $Y_n$)
    • lcs(m, n) = lcs(m - 1, n) (ignore both $X_m$ and $Y_n$)
    • This can be calculated bottom up via a 2D matrix. Note the dependency between these 4 subproblems.
  • code: $O(mn)$
    • m[i, j] = opt(i, j): length of longest common subsequence for $X_{\mathrm{1..}i}$ and $Y_{\mathrm{1..}j}$
    • m[0, j] = 0 for all j is 0, and m[i, 0] for all i is 0 (both needed due to the - 1’s)
    • for i = 1 to m
      • for j = 1 to n
        • `m[i, j] = max(m[i - 1, j - 1] + match(X[i], Y[i]), m[i, j - 1], m[i - 1, j])
  • traceback ($O(m+n)$) needed to find actual LCS
    • repeatedly find and move to the max neighboring cell in m starting from bottom right
    • if you moved up or left, ignore one corresponding character
    • if you moved diagonally (towards top left), then either ignore both characters, or include the character in LCS if they match
• pretty printing problem
  • input: words $i$ to $j$ in a paragraph in a single line. For any word $i$, we know its length $w_i$.
  • we know there will at least be $j-i$ spaces to delimit words
  • let $M$ be the max display length of a line
  • cost function for a line from words $i$ to $j$: $\mathrm{cost}(i,j)={\left[M-\left({\sum }_{k=1}^j{w}_k\right)-(j-i)\right]}^3$ (cube it to heavily discourage unused space on the line)
  • output: a new array with line breaks inserted that minimizes the cost function for each line
  • we basically have to decide where the last line starts
  • opt(n) = min_x(cost(x, n) + opt(x - 1)): find the x that minimizes cost plus opt(x-1).
• Note that optimal substructure proof only depends on the problem, not the algorithm.
• optimal substructure proof revisited with pretty printing problem example
  • define optimal solution
    • opt = { set of lines such that words $w_1$ to $w_n$ are on the first line }
    • proof will also work if starting from the last line
  • prove words $w_{x+1}$ to $w_n$ on lines $l_2$ to $lr$ has minimum cost
  • define A as opt without line 1 ($w_1$ to $w_x$)
  • Assume A is not an optimal way for the subproblem. Assume there exists a better way B to print $w_{x+1}$ to $w_n$.
  • But the costs are the same. Contradiction.