% CS5800 - Dynamic Programming Problems: Comparison table
% Compile with: pdflatex dp_comparison_table.tex
\documentclass[10pt]{article}
\usepackage[paperwidth=17in,paperheight=11in,margin=0.4in]{geometry}
\usepackage[table]{xcolor}
\usepackage{array}
\usepackage{amssymb,amsmath}

\definecolor{headcol}{HTML}{2F3E4E}
\definecolor{shadecol}{HTML}{EEF3F7}
\newcolumntype{L}[1]{>{\raggedright\arraybackslash\scriptsize}p{#1}}
\newcommand{\hd}[1]{\textbf{\textcolor{white}{#1}}}
\setlength{\tabcolsep}{3pt}
\renewcommand{\arraystretch}{1.25}
\pagestyle{empty}

\begin{document}
\begin{center}
{\Large\bfseries CS5800 -- Dynamic Programming Problems: Comparison}\\[3pt]
{\footnotesize Generated 2026-06-18.\quad Legend: $\Theta$ tight bound, $O$ upper, $\Omega$ lower;\ \ $\to$ arrow;\ \ $\gg$ much greater;\ \ $\star$ starred problem.\quad Shaded rows $=$ interval-DP family.}
\end{center}
\vspace{4pt}

\noindent\begin{tabular}{|L{3.6cm}|L{2.1cm}|L{4.9cm}|L{5.5cm}|L{3.2cm}|L{4.8cm}|L{3.6cm}|L{3.4cm}|L{5.3cm}|}
\hline
\rowcolor{headcol}
\hd{Problem} & \hd{Complete /10} & \hd{RT \& Mem (DP, bottom-up)} & \hd{Better bottom-up RT / Mem} & \hd{Memo skips subproblems?} & \hd{Memo helps with computation order?} & \hd{Major bugs} & \hd{Minor bugs} & \hd{Related ideas} \\
\hline
\textbf{Coin change} & 10 & $\Theta(nk)$ time, $\Theta(n)$ space; Make-Change $O(n)$ & $\Theta(nk)$ tight; space $\to \Theta(d_k)$ if value-only & No --- $d_1{=}1 \Rightarrow$ all $0..n$ reachable & No --- trivial (increasing amount $p$) & None & Recursive digression hardcodes $\{1,5,10\}$ & Unbounded knapsack (min-cost); DAG shortest path ($p\to p{-}d_i$) \\
\hline
\textbf{Checkerboard} & 9 & $\Theta(mn)$ time, $\Theta(mn)$ space; Check-Sol $\Theta(m)$ & $\Theta(mn)$ tight; space $\to \Theta(n)$ (one row) if value-only & No --- answer $=$ min over whole last row & No --- easy (row $1\to m$) & Borderline: recurrence wrong at $j{=}1,\,j{=}n$ (off-board reads); needs $\infty$ guard & $i$-loop should start at 2 (reads/clobbers row 0); min vs argmin (Check-Sol L1); prints row 0 (downto 2); $(l,k)\to(k,l)$ & Layered-DAG shortest path; grid/triangle min-path-sum; Viterbi \\
\hline
\textbf{Knapsack (0/1)} & 10 & $\Theta(nW)$ time; space \emph{stated} $\Theta(n^2)$ [\textbf{wrong}: $\Theta(nW)$]; Items $O(n)$ & $\Theta(nW)$ tight; space $\to \Theta(W)$ rolling row; Hirschberg traceback & \textbf{Yes} --- only $w{=}W{-}(\text{subset sum})$ visited; skips much of $\Theta(nW)$ when $W \gg \#\text{weights}$ & No --- easy (item by item, row-major) & \textbf{Incorrect claim:} space $\Theta(n^2)$ (should be $\Theta(nW)$) & ITEMS print / $W{-}{=}w[n]$ not nested under \texttt{if}; ``$0\le i,w\le n$'' should be $w\le W$ & Subset-sum / partition ($v{=}w$); unbounded $=$ coin change; fractional $=$ greedy \\
\hline
\textbf{LCS} & 10 & $\Theta(mn)$ time, $\Theta(mn)$ space; Print-LCS $O(m{+}n)$ & length-only space $\Theta(\min(m,n))$; Hirschberg; time $O(mn/\log n)$ Four-Russians; bit-parallel $O(mn/w)$ & Barely --- worst case (few matches) reaches all $mn$ & No --- easy (row-major) & None & ``proceeds'' $\to$ ``precedes'' & Edit / Levenshtein distance; Needleman--Wunsch; LIS $=$ LCS$(A,\text{sorted }A)$ \\
\hline
\textbf{Max-duration scheduling (weighted interval)} & 10 & $O(n\log n)$ (linear DP $+$ 2 sorts); $O(n)$ if keys sort linearly; space $O(n)$ & $O(n\log n)$ tight in comparison model; $O(n)$ with radix / pre-sorted & No --- skip-branch $dp[k{+}1]$ chains through all indices & Low --- sort by start, then a simple right-to-left pass & None & Setup table lists $G$ duration 3; $14{-}12{=}2$ (Gantt $+$ DP trace use 2) & Weighted interval scheduling; unit weights $\to$ activity selection (greedy); max-wt independent set on interval graph \\
\hline
\textbf{Jars on ladder (egg drop / HSR)} & N/A ($\sim$9, unsolved spec) & MinT$(n,k)$: $O(n^2k)$ time, $O(nk)$ space & dual MaxR$(k,q)\to O(nk)$, or $O(k{\cdot}\text{MinT})$ via $\sum C(q,i)$; Knuth monotonicity $\to O(nk)$; space $\to O(k)$ & No --- inner min over all first rungs requests every smaller $(j,k{-}1),(j,k)$ & Low --- nested increasing $(k,n)$; MaxR by increasing $q$ & None (statement) & MaxR$(k,q)$ in B vs MaxR$(q,k)$ in C-hint (arg-order flip) & Classic egg-drop; MinT $\leftrightarrow$ MaxR DP-dual; $\sum C(q,i)\ge n$ $=$ decision-tree bound; ties to Optimal BST \\
\hline
\textbf{Longest hike $\star$} & N/A ($\sim$9, unsolved spec) & $\Theta(n^2)$ time, $\Theta(n^2)$ space; row-major fill \textbf{invalid} & Part A (ints $\le 29000$): counting-sort buckets $\to \Theta(n^2)$. Part B (reals): Kahn/queue topological (BFS) $\to \Theta(n^2)$, vs $\Theta(n^2\log n)$ sort & No --- max over all starts $\Rightarrow$ all $n^2$ cells needed & \textbf{Yes, strongly} --- order is by altitude (not position); reals need BFS-queue or DFS-memo. The point of Part B & None (statement) & ``he matrix'' $\to$ ``the''; ``dont'' $\to$ ``don't'' & Longest path in a DAG (Lec-8 DP-as-DAG); topological-order DP; $+1$ edges $\Rightarrow$ acyclic; toroidal grid; counting-sort to order states \\
\hline
\textbf{Painters / fence (Split-Array-Largest-Sum)} & $\sim$8 (handwritten) & $\Theta(n^2k)$ time (prefix sums $\Rightarrow O(1)$/split); $O(nk)$ space $\to O(n)$ rolling & binary search on the answer $+ O(n)$ feasibility $\to O(n\log(\sum L))$ (no $k$); or monotone-split / D\&C $\to {\sim}\,O(nk\log n)$ & No --- $dp[i][p]$ all needed & Low --- nested increasing $(i,p)$ & None evident (handwritten) & --- & LeetCode 410 Split-Array-Largest-Sum; book/file allocation; makespan w/ contiguous blocks; \textbf{minimax} (bottleneck) objective $\Rightarrow$ max inside min; binary-search-on-answer \\
\hline
\rowcolor{shadecol}
\textbf{Bitonic tour (CLRS 15-3 / Chris)} & $\sim$8 (handwritten) & CLRS 2-D $B[i,j]$: $\Theta(n^2)$ time, $\Theta(n^2)$ space; $+\,O(n\log n)$ sort & Chris's 1-D $C[m]$: $\Theta(n^2)$ time, $O(n)$ space (split $j$ $+$ consecutive-chain prefix sums); sort $O(n\log n)$ & No --- min over all splits requests the chain & Low --- increasing $m$ (Chris) / increasing $j$ (CLRS) & None evident (handwritten) & (photo) $\sum$ upper limit reads ``$i{-}1$'', is ``$R{-}1$'' & Euclidean TSP (poly $x$-monotone special case); two-paths DP; CLRS 15-3 (14-3 4th ed); min-sum \\
\hline
\rowcolor{shadecol}
\textbf{Optimal BST (your notes / CLRS)} & $\sim$7 (handwritten sketch; HW6 Q1 finishes steps 3--5) & $\Theta(n^3)$ time, $\Theta(n^2)$ space ($e$, root, $w$ tables) & Knuth's optimization $\to O(n^2)$ (root monotone; QI holds: $w(i,j)$ split-independent); space $\Theta(n^2)$ & No --- inner min over all roots requests every interval (like matrix chain) & Mild --- by increasing interval length (diagonal), like matrix chain & None evident (handwritten) & (not symbol-audited) & Matrix chain (sibling; only OBST gets Knuth); polygon triangulation; Hu--Tucker / alphabetic codes; vs Huffman (greedy); $+w(i,j)$ $=$ ``every node sinks one level'' \\
\hline
\rowcolor{shadecol}
\textbf{Matrix chain} & 10 & $\Theta(n^3)$ time, $\Theta(n^2)$ space; Print $O(n)$ & $O(n\log n)$ (Hu--Shing, polygon partitioning) --- \emph{not} Knuth (added weight depends on split $k$); space $\Theta(n^2)$ & No --- inner min over all splits requests every interval & Mild --- by chain length (diagonal), not row-major & None & ``$k{=}i,\dots,j{+}1$'' should be $j{-}1$ (claim itself correct); ``splited / os / in and'' typos & Optimal BST (sibling); $=$ polygon triangulation (Hu--Shing); CYK \\
\hline
\end{tabular}

\vspace{8pt}
\noindent{\footnotesize \textbf{Interval-DP family} (shaded): matrix chain, Optimal BST, bitonic --- all split-at-$k$ over an interval, fill diagonally, and let memoization skip nothing; the speedups differ --- OBST $\to$ Knuth $O(n^2)$, matrix chain $\to$ Hu--Shing $O(n\log n)$, bitonic already $O(n^2)$ (Chris $\to O(n)$ space).\par
\smallskip
\textbf{Painters} is the lone minimax (bottleneck) DP --- its recurrence nests \emph{max} inside \emph{min} rather than summing, which is exactly why binary-search-on-the-answer applies to it and not to the additive DPs.}

\end{document}
