\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref,graphicx,xcolor}
\newcommand{\eps}{\varepsilon}
\newcommand{\fig}[2]{\begin{figure}[h]\begin{center}%
\includegraphics[scale=#2]{#1.pdf}\end{center}%
\end{figure}}
\newlength{\mylength}
\newcommand{\scratch}[1]{\makebox[0in][l]{#1}\settowidth{\mylength}{#1}{\color{red}\rule[.6ex]{\mylength}{1pt}}}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2024)\\
{\Large Homework 6} (due Mar 7 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks.
\bigskip\noindent
{\bf Note:} In dynamic programming problems, you should
follow all the steps below, unless stated otherwise:
\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 your subproblems (including
base cases), with justification/explanation;
\item specify a valid evaluation order;
\item give pseudocode to evaluate your recursive formula bottom-up (using tables, and loops instead of recursion);
and
\item analyze the running time;
\item and if we explicitly ask for it, give pseudocode to output an optimal solution rather than just the optimal value.
\end{enumerate}
{\em Do not jump directly to pseudocode. Do not skip step~1!}
\begin{description}
\bigskip
\item[Problem 6.1:]
\newcommand{\INC}{\mbox{\tt /}}
\newcommand{\DEC}{\mbox{\tt\symbol{92}}}
For a sequence of distinct numbers $B=\langle b_1,b_2,\ldots,b_\ell\rangle$,
define its associated string $\sigma(B) = c_1 c_2\cdots c_{\ell-1}\in \{\INC,\DEC\}^*$
where $c_i=\INC$ if $b_ib_{i+1}$.
Consider the following problem: given a sequence of distinct numbers $A=\langle a_1,a_2,\ldots,a_n\rangle$,
find a subsequence $B=\langle a_{i_1},a_{i_2},\ldots,a_{i_\ell}\rangle$ with $i_1 7$.
This was first proved in 2018; the proof is far from obvious\ldots\ you don't need to know this.)
\begin{enumerate}
\item[(a)] (80 pts)
Design and analyze an efficient dynamic programming algorithm to compute the optimal length.
Aim for $O(n^2)$ running time for full credit.
(Hint: consider defining $L(i,\INC\DEC)$
to be the maximum length of a subsequence $B$ of $\langle a_1,a_2,\ldots,a_i\rangle$
subject to the constraints that the last element of $B$ is $a_i$, and $\sigma(B)$ ends in $\INC\DEC$ and avoids $\INC\DEC\INC$ and $\DEC\INC\DEC$.
Define other subproblems similarly\ldots)
\smallskip
\item[(b)] (20 pts)
Give pseudocode to output an optimal subsequence.
\end{enumerate}
\bigskip
\item[Problem 6.2:]
\newcommand{\stair}{\textsc{staircase}}
For a set $Q$ of points with positive $x$- and $y$-coordinates in 2D,
define $\stair(Q)$ to be the region
\[ \{(x,y):\ \mbox{$0\le x\le q.x$ and $0\le y\le q.y$ for some $q=(q.x,q.y)\in Q$}\}.
\]
Consider the following problem:
given a set $P$ of $n$ points with positive distinct $x$- and $y$-coordinates in 2D, and given a number $k\le n$,
find a subset $Q\subseteq P$ of at most $k$ points such that
the area of $\stair(Q)$ is maximized.
(The higher-dimensional version of this problem is useful as a way to identify ``important'' points in a large dataset.
Below is an example of a feasible solution $Q$, shown in red, for $k=4$.)
\fig{hw6fig}{1.1}
\vspace{-2ex}
\begin{enumerate}
\item[(a)] (80 pts)
Design and analyze an efficient dynamic programming algorithm to compute the optimal area
(you don't have to output an optimal subset).
Aim for $O(n^2k)$ running time for full credit.
(Hint: Why may we assume that $Q$ is decreasing, i.e., the points of $Q$ are of
the form $q_1,\ldots,q_\ell$ with $q_1.x<\cdots\cdots>q_\ell.y$?)
\smallskip
\item[(b)] (20 pts)
Instead of maximizing the area,
suppose we change the problem to finding a subset $Q\subseteq P$ that maximize the number of points
of $P$ inside $\stair(Q)$. Describe the changes to your recursive formula (no need to
give complete pseudocode again), and show that the algorithm can be implemented
in $O(n^3)$ time (do not assume that $k$ is a constant).
(Bonus: A correct solution that has running time $O(n^2k)$ or better instead of $O(n^3)$ may receive up to 5 extra points.)
\end{enumerate}
\end{description}
\end{document}