\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref,graphicx,xcolor}
\newcommand{\eps}{\varepsilon}
\newcommand{\fig}[2]{\begin{center}\includegraphics[scale=#2]{#1.pdf}\end{center}}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2020)\\
{\Large Homework 6} (due Mar 12 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks.
\begin{description}
\medskip
\item[General Note:] In any dynamic programming solution, you should
follow the steps below (if we explicitly state that pseudocode is not required, then step~4 may be skipped):
\begin{enumerate}
\item first give a clear, precise definition of the subproblems (i.e., what the recursive
function is intended to compute);
\item then derive a recursive formula to solve the subproblems (including
base cases), with justification or proof of correctness if the formula is not
obvious;
\item specify a valid evaluation order;
\item give pseudocode to evaluate your recursive formula bottom-up (with loops instead of recursion);
and
\item analyze the running time.
\end{enumerate}
{\em Do not jump to pseudocode immediately. Never skip step~1!}
\bigskip
\item[Problem 6.1:]\
\begin{enumerate}
\item[(a)] ($7.5$ points)
Given an array $A$ of $n$ numbers, describe an efficient dynamic programming algorithm to find the length of
a longest subsequence $S$ that is (strictly) increasing, such that both $S$ and
$S^R$ are subsequences of $A$. Here, $S^R$ denotes the reverse of $S$.
(For example, for $A=\langle 1, 2, 3, 4\rangle$, the optimal length is 1;
for $A=\langle 1, 15, 8, 2, 3, 5, 4, 3, 8, 10, 1,9\rangle$, the optimal length is 4, because both $\langle 1,3,5,8\rangle$ and $\langle 8,5,3,1\rangle$ are subsequences.)
Hint: for the definition of subproblems, let $L(i,j,k)$ be the
length of a longest increasing subsequence such that $S$ is a subsequence
of $A[i,\ldots,n]$ and $S^R$ is a subsequence of $A[1,\ldots,j]$, and
all elements in $S$ are greater than $A[k]$.
\item[(b)] ($2.5$ points)
Give pseudocode to output an optimal subsequence $S$ (not just its length).
\end{enumerate}
\bigskip
\item[Problem 6.2:]
We have $n$ jobs, where job $i$ starts at time $t_i$ and has value $v_i>0$, with $t_1