\section{1D DP}

%%%%%%%%%%%%%%%%%%%%
\begin{frame}{$f^{(S(n))} = 1$}
  \begin{exampleblock}{$f^{(S(n))} = 1$ (Problem 7.2)}
	\begin{displaymath}
	  f(n) = \begin{cases}
		n - 1 & \text{if } n \in \mathbb{Z}^{+} \\
		n / 2 & \text{if } n \% 2 = 0 \\
		n / 3 & \text{if } n \% 3 = 0
	  \end{cases}
	\end{displaymath}

	\centerline{$S(n):$ minimum number of steps taking $n$ to 1.}
  \end{exampleblock}

  \pause
  \[
	S(i): \text{minimum number of steps taking } i \text{ to } 1
  \]

  \pause
  \[
	S(i) = 1 + \min \set{S(i-1), S(i/2) (\text{if } n\%2 = 0), S(i/3) (\text{if } n\%3 = 0)}
  \]

  \[
	S(1) = 0
  \]
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{$f^{(S(n))} = 1$}
  Collatz ($3n+1$) conjecture:
  \begin{displaymath}
	f(n) = \begin{cases}
	  n / 2 & \text{if } n \% 2 = 0 \\
	  3n + 1 & \text{if } n \% 2 = 1
	\end{cases}
  \end{displaymath}

  \[
	f^{\ast}(n) = 1 ?
  \]

  \pause
  \vspace{0.50cm}
  \begin{quote}
	``Mathematics may not be ready for such problems.''\\
	\hfill --- Paul Erdős
  \end{quote}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Longest increasing subsequence}
  \begin{exampleblock}{Longest increasing subsequence (Problem 7.3)}
    \begin{itemize}
      \item Given an integer array $A[1 \ldots n]$
      \item To find (the length of) a longest increasing subseqence.
    \end{itemize}
  \end{exampleblock}

  \[
    5,2,8,6,3,6,9,7 \implies 2, 3, 6, 9
  \]
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Longest increasing subsequence}
  \begin{description}
	\item[Subproblem:] $L(i):$ the length of the LIS of $A[1 \ldots i]$
	\item[Goal:] $L(n)$
	  \pause
	\item[Make choice:] whether $A[i] \in LIS[1 \ldots i]$?
	\item[Recurrence:] 
	  \[
		L(i) = \max \set{L(i-1), 1 + \max_{j < i \land A[j] \le A[i]} L(j)}
	  \]
	  \pause
	\item[Init:]
	  \[
		L(0) = 0
	  \]
	\item[Time:] 
	  \[
		O(n^2) = \Theta(n) \cdot O(n)
	  \]
  \end{description}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Longest increasing subsequence}
  \fignocaption{width = 0.40\textwidth}{figs/LIS-example.png}

  \centerline{Longest path distance in the DAG!}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Maximum-sum subarray}
  \begin{exampleblock}{Maximum-sum subarray (Google Interview)}
    \begin{itemize}
      \item Array $A[1 \cdots n], a_{i} >=< 0$
      \item To find (the sum of) a maximum-sum subarray of $A$
    \end{itemize}
	
    \[
      A[-2,1 ,-3,4,-1,2,1,-5,4] \implies [4,-1,2,1]
    \]
  \end{exampleblock}

  \pause
  \begin{description}
	\item[Subproblem:] $\text{MSS}[i]$: sum of an $\text{MS}[i]$ of $A[1 \cdots i]$
	\item[Goal:] $\text{mss} = \text{MSS}[n]$
	\pause
	\item[Make choice:] Is $a_{i} \in \text{MS}[i]$?
	\item[Recurrence:]
	  \[ 
		\text{MSS}[i] = \max \set{\text{MSS}[i-1], \textcolor{red}{???}}
	  \]
  \end{description}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Maximum-sum subarray}
  \begin{description}
	\item[Subproblem:] $\text{MSS}[i]$: sum of an $\text{MS}[i]$ \textcolor{red}{\it ending with} $a_{i}$
	\item[Goal:] $\text{mss} = \max\limits_{1 \le i \le n} \text{MSS}[i]$
	\pause
	\item[Make choice:] Where does the $\text{MS}[i]$ start?
	\item[Recurrence:]
	  \[ 
		\text{MSS}[i] = \max \set{\text{MSS}[i-1] + a_{i}, a_{i}} \text{ \textcolor{red}{(Proof!)}}
	  \]
	\pause
	\item[Init:]
	  \[
		\text{MSS}[0] = 0
	  \]
	  \pause
	\item[Time:] $\Theta(n)$
  \end{description}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Maximum-sum subarray}
  \begin{columns}
	\column{0.40\textwidth}
	  \fignocaption{width = 0.60\textwidth}{figs/programming-pearls.jpg}
	\column{0.60\textwidth}
	  \begin{description}[<+->][Michael Shamos]
		\item[Ulf Grenander] $O(n^3) \implies O(n^2)$
		\item[Michael Shamos] $O(n \log n)$, onenight
		\item[Jon Bentley] Conjecture: $\Omega(n \log n)$
		\item[Michael Shamos] Carnegie Mellon seminar
		\item[Jay Kadane] $O(n)$, \uncover<6->{\textcolor{red}{$\le 1$ minute}}
	  \end{description}
  \end{columns}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}<beamer:0>{Maximum-sum subarray}
  \begin{columns}
	\column{0.55\textwidth}
	  \begin{algorithmic}
		\State $\text{MSS}[0] \gets 0$
		\ForAll{$i \gets 1 \dots n$}
		  \State $\text{MSS}[i] \gets \max\set{\text{MSS}[i-1] + a_i, 0}$
		\EndFor
		\State \Return $\max\limits_{i = 1 \dots n} \text{MSS}[i]$ 
	  \end{algorithmic}
	  \pause
	\column{0.50\textwidth}
	  \begin{algorithmic}
		\State $\text{mss} \gets 0$
		\State $\text{MSS} \gets 0$
		\ForAll{$i \gets 1 \dots n$}
		  \State $\text{MSS} \gets \max\set{\text{MSS} + a_i, 0}$
		  \State $\text{mss} \gets \max\set{\text{mss}, \text{MSS}}$
		\EndFor
		\State \Return $\text{mss}$
	  \end{algorithmic}
  \end{columns}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Maximum-product subarray}
  \begin{exampleblock}{Maximum-product subarray (Problem 7.4)}
	\begin{itemize}
	  \item Array $A[1 \dots n]$
	  \item Find maximum-product subarray of $A$
	\end{itemize}

	\begin{enumerate}[(1)]
	  \item $a_i \in \mathbb{N}$
	  \item $a_i \in \mathbb{Z}$
	  \item $a_i \in \mathbb{R}$ 
	\end{enumerate}
  \end{exampleblock}

  \pause
  \vspace{0.60cm}
  \centerline{sum \emph{vs.} product}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Maximum-product subarray}
  \centerline{Subproblem: $\text{MaxP}[i], \text{MinP}[i]$}

  \begin{table}
	\renewcommand{\arraystretch}{1.5}
	\centering
	\begin{tabular}{|L||C|C|C|C|C|C|C|}
	  \hline
	  &	& \frac{1}{2} & 4 & -2 & \textcolor{red}{5} & \textcolor{red}{-\frac{1}{5}} & 8 \\ \hline
	  \text{MaxP}[i] & 1	& \frac{1}{2} & 4 & -2 & 5 & 8 & 64 \\ \hline
	  \text{MinP}[i] & 1	& \frac{1}{2} & 2 & -8 & -40 & -1 & -8  \\ \hline
	\end{tabular}
  \end{table}

  \begin{align*}
	\text{MaxP}[i] &= \max\set{\text{MaxP}[i-1] \cdot a_i, \text{MinP}[i-1] \cdot a_i, a_i} \\
	\text{MinP}[i] &= \min\set{\text{MaxP}[i-1] \cdot a_i, \text{MinP}[i-1] \cdot a_i, a_i}
  \end{align*}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Reconstructing string}
  \begin{exampleblock}{Reconstructing string (Problem 7.9)}
    \begin{itemize}
      \item String $S[1 \cdots n]$
      \item Dict for \emph{lookup}:
		\begin{displaymath}
		  \text{dict}(w) = \left\{ \begin{array}{ll}
			\text{true} & \textrm{if } w \textrm{ is a valid word}\\
			\text{false} & \textrm{o.w.}
		  \end{array} \right.
		\end{displaymath}
	  \item Is $S[1 \cdots n]$ valid (reconstructed as a sequence of valid words)?
    \end{itemize}
  \end{exampleblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Reconstructing string}
  \begin{description}
	\item[Subproblem:] $V[i]$: Is $S[1 \cdots i]$ valid?
	\item[Goal:] $V[n]$
	\pause
	\item[Make choice:] Where does the last word start?
	\item[Recurrence:] 
	  \[ 
		V[i] = \bigvee_{j = 1 \ldots i} (V[j-1] \land \text{dict}(S[j \cdots i]))
	  \]
	\pause
	\item[Init:]
	  \[
		V[0] = \text{true}
	  \]
	\item[Time:]
	  \[
		O(n^2) = \Theta(n) \cdot O(n)
	  \]
  \end{description}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Hotel along a trip}
  \begin{exampleblock}{Hotel along a trip (Problem 7.15)}
    \begin{itemize}
      \item Hotel sequence (distance): $a_{0} = 0, a_{1}, \cdots, a_{n}$
      \item $a_0 \leadsto a_n$ 
	  \item Stop at only hotels
      \item Cost: $(200 - x)^{2}$ 
      \item To minimize overall cost
    \end{itemize}
  \end{exampleblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Hotel along a trip}
  \begin{description}
	\item[Subproblem:] $C[i]$: minimum cost when the destination is $a_{i}$
	\item[Goal:] $C[n]$
	\pause
	\item[Make choice:] What is the last but one hotel $a_{j}$ to stop?
	\item[Recurrence:] 
	  \[
		C[i] = \min_{0 \le j < i} \set{C[j] + (200 - (a_{i} - a_{j}))^{2}}
	  \]
	\pause
	\item[Init:]
	  \[
		C[0] = 0
	  \]
	\item[Time:] 
	  \[
		O(n^2) = \Theta(n) \cdot O(n)
	  \]
  \end{description}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Highway restaurants}
  \begin{exampleblock}{Highway restaurants (Problem 7.16)}
	\begin{itemize}
	  \item Locations: $L[1 \dots n]$
	  \item Profits: $P[1 \dots n]$
	  \item Any two hotels should be $\ge k$ miles apart
	  \item To maximize the total profit
	\end{itemize}
  \end{exampleblock}

  \begin{description}
	\item[Subproblem:] $T[i]$: max profit achievable using only $L[1 \dots i]$
	\item[Goal:] $T[n]$
	  \pause
	\item[Make choice:] Whether to open a restaurant at $L_i$?
	\item[Recurrence:] 
	  \begin{align*}
		T[i] &= \max\set{T[i-1], P_i + T[\text{prev}(i)]} \\
		\text{prev}(i) &= \max\set{j \mid j < i \land L_i - L_j \ge k}
	  \end{align*}
	  \pause
	\item[Init:] $T[0] = 0$
  \end{description}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Weighted interval/class scheduling}
  \begin{exampleblock}{Weighted interval/class scheduling (Problem 7.14)}
    \begin{itemize}
      \item Classes: $\mathcal{C} = \set{c_{1}, c_{2}, \cdots, c_{n}} \quad c_{i} \triangleq \langle g_{i}, s_{i}, f_{i} \rangle$
      \item Choosing non-conflicting classes to maximize your grades
    \end{itemize}
  \end{exampleblock}

  \fignocaption{width = 0.40\textwidth}{figs/weighted-interval.png}
  \centerline{\textcolor{red}{sort $\mathcal{C}$ by finishing time.}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Weighted interval/class scheduling}
  \centerline{Greedy algorithms fail:}
  
  \vspace{0.30cm}
  \begin{columns}
	\column{0.50\textwidth}
	  \fignocaption{width = 0.40\textwidth}{figs/weighted-interval-greedy-finish-time.pdf}{\centerline{By finishing time.}}
	  \pause
	\column{0.50\textwidth}
	  \fignocaption{width = 0.75\textwidth}{figs/weighted-interval-greedy-weights.pdf}{\centerline{By weights.}}
  \end{columns}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Weighted interval/class scheduling}
  \begin{description}
	\item[Subproblem:] $G[i]$: the maximal grades obtained from $\set{c_{1}, c_{2}, \cdots, c_{i}}$
	\item[Goal:] $G[n]$
	  \pause
	\item[Make choice:] Choose $c_{i}$ or not?  
	\item[Recurrence:] 
	  \begin{align*}
		G[i] &= \max \set{G[i-1], G[\text{prev}(i)] + g_{i}}  \\
		\text{prev}(i) &= \max\set{j \mid j < i \land c_{i} \cap c_{j} = \emptyset}
	  \end{align*}
	  \pause
	\item[Init:] $G[0] = 0$
	\item[Time:] $O(n \log n) + T(\text{prev}(i)) + O(n) \cdot O(1)$
  \end{description}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Weighted interval/class scheduling}
  Why is ordering necessary?
  \fignocaption{width = 0.50\textwidth}{figs/weighted-interval-unordered.pdf}

  \[
	G[7] = \max \set{G[6], G[\set{1,3,5}] + g_{7}}
  \]

  \begin{center}
	subproblems changed: all $O(2^{n})$ subsets
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Weighted interval/class scheduling}
  What about sorting by starting time?
  \fignocaption{width = 0.50\textwidth}{figs/weighted-interval-starting-time-ordered.pdf}

  \[
	G[6] = \max \set{G[5], G[\set{2,3}] + g_{6}}
  \]

  \begin{center}
	subproblems changed: all $O(2^{n})$ subsets
  \end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%
