\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
%\usepackage{xcolor}
\usepackage{graphicx,fancyhdr,algorithm,algorithmic}
\usepackage[space]{grffile}
\usepackage{titlesec}
\usepackage{multicol}
\usepackage{enumitem} 
\usepackage{tikz}
\usepackage{tikz-qtree}
\usetikzlibrary{arrows,automata}


\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

%some custom commands for problem 2
%want some nice colors
\definecolor{darkred}{rgb}{.87,0,0}
\definecolor{niceblue}{rgb}{.392,.584,.929}
%change the font, change the color, and raise the first word's letters slightly
\newcommand{\firstword}[1]{\textsf{{\color{darkred}{\raisebox{.3em}{#1}}}}}
\newcommand{\secondword}[1]{\textsf{{\color{niceblue}{#1}}}}


\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{question}{Problem}

\newenvironment{solution}{\bigskip\noindent{\it Solution.}  \ignorespaces}{\hfill\qed}

\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
\urlstyle{same}
\PassOptionsToPackage{hyphens}{url}
\newcommand{\homework}[6]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS 256:~Algorithm Design and Analysis \hfill} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #1 \normalsize{(#2)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #3 \hfill } }
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}



\begin{document}
\homework{Assignment 5}{due 10/24/2020}{Sam McCauley}{}{}{}

\noindent
{\bf Note on Dynamic Programs.} For full credit on a dynamic program, you must clearly state the following parts.
\begin{enumerate}[ leftmargin=*, noitemsep, label = (\alph*)]

\item {\em Subproblem definition:}  your subproblem must have an optimal substructure. 

\item {\em Recurrence:}  how should the next subproblem be computed using the previous ones? This is the core of your algorithm and its correctness.
A less ideal alternative to a recurrence is clear pseudocode for the final iterative dynamic-programming algorithm. 
\item {\em Base case(s):}  you need to start somewhere!  

\item {\em Final output:}  in terms of your subproblem.

\item {\em Memoization data structure:}  this is often obvious but should not be skipped.

\item {\em Evaluation order:}  describes the dependencies between the subproblems.

\item {\em Time and space analysis.} 
\end{enumerate}

For this assignment, these are sufficient to argue correctness (that is to say, if you explain why the above parts are correct, that's sufficient to show that your algorithm works properly).

\bigskip

The problems in this assignment are in (approximate) order of difficulty.  We'll be seeing a number of dynamic programming examples over the next few lectures.  Some of the later, more diffiuclt problems will likely become easier as you get more practice with dynamic programming.





\newpage
\begin{question}(Kleinberg Tardos 6.1) 
Let $G = (V, E)$ be an undirected graph with $n$ nodes. A subset of the nodes is called an \emph{independent set} if no two of them are joined by an edge. Finding large independent sets is difficult in general; but here we'll see that it can be done efficiently if the graph is simple enough.
	
Call a graph $G =(V, E)$ a path if its nodes can be written as $v_{1}, v_{2}, . . . , v_{n}$, with an edge between $v_{i}$ and $v_{i+1}$, for $i \in \{1, 2, \ldots, n-1\}$. With each node $v_{i}$, we associate a positive integer weight $w_{i}$. The problem we want to solve is the following: Find an independent set in a path $G$ whose total weight is as large as possible.

For example, given the following path

%latex can do for loops and (albeit annoyingly) some math!
%this can help make drawing figures a little easier
\begin{figure}[h]
    \centering
    \begin{tikzpicture}
      %this draws the nodes
      \node [style={circle,draw}] (0) at (2,0) {1};
      \node [style={circle,draw}] (1) at (4,0) {8};
      \node [style={circle,draw}] (2) at (6,0) {6};
      \node [style={circle,draw}] (3) at (8,0) {3};
      \node [style={circle,draw}] (4) at (10,0) {6};
      %this draws the lines
      \foreach \x in {0,...,3}
        \pgfmathtruncatemacro{\nextnode}{\x + 1}
        \draw[thick] (\x) to (\nextnode) ;
    \end{tikzpicture}
  \end{figure}
  The maximum weight of an independent set is 14.



\begin{enumerate}[label = (\alph*)]
  \item Give a counterexample to show that the following ``pick the heaviest weight'' greedy algorithm does not always work.
    \begin{itemize}[noitemsep, nolistsep]
      \item Start with $S = \emptyset$
      \item While some node remains in $G$
        \begin{itemize}
          \item Pick a node $v_i$ of maximum weight and $v_i$ to $S$
          \item Delete $v_i$ and its neighbors from $G$
        \end{itemize}
      \item Return $S$
    \end{itemize}



  \item Give a simple exponential-time recursive algorithm that gives a correct solution.


  \item Give a dynamic-programming algorithm that takes an $n$-node path $G$ with weights and returns the {\em value} of the independent set of maximum total weight.  
\end{enumerate}
    
\end{question}
\begin{solution}
\end{solution}

\newpage
\begin{question}(Erickson 3.6)
  Solving part (a) is sufficient for full credit on this problem; part (b) is extra credit.  However, I encourage you to (at least) think very hard about how to solve part (b), as it's excellent dynamic programming practice.

  \bigskip

  A shuffle of two strings  $X$ and  $Y$ is formed by interspersing the characters into a new string, keeping the characters of  $X$and  $Y$in the same order.For example, the string \textsf{BANANAANANAS} is a shuffle of the strings \textsf{\color{darkred} BANANA} and \textsf{\color{niceblue} ANANAS} in several different ways. 

  \bigskip

  %here's some latex for you!
  %the commands \firstword and \secondword are homemade commands, defined at the top
  %of the document.  The percent signs % are comments---but here they're used at the end
  %of the line to comment out the invisible "nextline" at the end of the line---much of the following
  % is on the same line.
  %\hspace{\fill} balances horizontal space---think of it as "pushing out" with equal force on either side
  \hspace{\fill}~
  \firstword{BANANA}\secondword{ANANAS}~
  \hspace{\fill}~
  \firstword{BAN}%
  \secondword{ANA}%
  \firstword{ANA}%
  \secondword{NAS}~
  \hspace{\fill}~
  \firstword{B}%
  \secondword{AN}%
  \firstword{AN}%
  \secondword{A}%
  \firstword{A}%
  \secondword{NA}%
  \firstword{NA}%
  \secondword{S}~
  \hspace{\fill}

  \bigskip

  Similarly, the strings \textsf{PRODGYRNAMAMMIINCG} and \textsf{DYPRONGARMAMMICING} are both shuffles of \textsf{\color{niceblue} DYNAMIC} and \textsf{\color{darkred} PROGRAMMING}:

  \bigskip
  \hspace{\fill}
  \firstword{PRO}%
  \secondword{D}%
  \firstword{G}%
  \secondword{Y}%
  \firstword{R}%
  \secondword{NAM}%
  \firstword{AMMI}%
  \secondword{I}%
  \firstword{N}%
  \secondword{C}%
  \firstword{G}
  \hspace{\fill}
  \secondword{DY}%
  \firstword{PRO}%
  \secondword{N}%
  \firstword{G}%
  \secondword{A}%
  \firstword{R}%
  \secondword{M}%
  \firstword{AMM}%
  \secondword{IC}%
  \firstword{ING}~
  \hspace{\fill}
  \bigskip


  \begin{enumerate}[label = (\alph*)]
  \item Given three strings $A[1..m]$, $B[1..n]$, and $C[1..m+n]$, describe and analyze an algorithm to determine whether $C$ is a shuffle of $A$ and $B$.
  \item \textbf{(Extra credit: 5 pts)} A \textbf{smooth} shuffle of $X$ and $Y$ is a shuffle of $X$ and $Y$ that never uses more than two consecutive symbols of either string. For example,
    \begin{itemize}[itemsep=12pt]
      \item 
        \firstword{PR}%
        \secondword{D}%
        \firstword{O}%
        \secondword{Y}%
        \firstword{G}%
        \secondword{NA}%
        \firstword{RA}%
        \secondword{M}%
        \firstword{MM}%
        \secondword{I}%
        \firstword{I}%
        \secondword{C}%
        \firstword{NG}
        is a smooth shuffle of the strings \textsf{\color{niceblue}{DYNAMIC}} and \textsf{\color{darkred}{PROGRAMMING}}.
      \item 
        \firstword{DY}%
        \secondword{PR}%
        \firstword{N}%
        \secondword{OGR}%
        \firstword{A}%
        \secondword{A}%
        \firstword{M}%
        \secondword{MM}%
        \firstword{IC}%
        \secondword{ING}
        is a shuffle of \textsf{\color{darkred}{DYNAMIC}} and \textsf{\color{niceblue}{PROGRAMMING}}, but it is not a smooth shuffle (because of the substrings \textsf{OGR} and \textsf{ING}).
      \item 
        \firstword{XX}%
        \secondword{X}%
        \firstword{X}%
        \secondword{X}%
        \firstword{X}%
        \secondword{XX}%
        \firstword{XX}%
        \secondword{XX}%
        \firstword{XX}%
        \secondword{X}%
        \firstword{X}%
        \secondword{X}%
        \firstword{XX}
        is a smooth shuffle of the strings \textsf{\color{darkred}{XXXXXXX}} and \textsf{\color{niceblue}{XXXXXXXXXXX}}.
      \item There is no smooth shuffle of the strings \textsf{\color{darkred}{XXXX}} and \textsf{\color{niceblue}{XXXXXXXXXXXX}}.
    \end{itemize}
    Describe and analyze an algorithm to decide, given three strings $X$, $Y$,and $Z$, whether $Z$ is a smooth shuffle of $X$ and $Y$.

    \textit{Hint:} What do you need to change in order to build up a smooth shuffle rather than a normal shuffle?  What do you need to keep track of to ensure that you can make this distinction?
\end{enumerate}
  
\end{question}
\begin{solution}
\end{solution}



\newpage
\begin{question}(From Steve Skiena's {\em Algorithm Design Manual}) Consider the problem of storing $n$ books
on shelves in a library. The order of the books is fixed by the
cataloging system and so cannot be rearraged. 
Let book $b_i$ have thickness $t_i$ and height $h_i$, for $1 \leq i \leq n$. Let the length of each bookshelf at this library be $L$.
Suppose we have the freedom to adjust the height of each shelf to fit the tallest book on it. The cost of a particular layout is the sum, over each shelf, of the height of the largest book on 
that shelf.  (So if shelf $1$ has books with heights $(1, 5, 3)$ and shelf $2$ has books with heights $(2,4)$, the total cost is $5 + 4 = 9$.)

\begin{enumerate}[label = (\alph*),  leftmargin=*]
\item Give an example to show that the greedy algorithm of stuffing each shelf as full as possible (that is, fill the first shelf with as many books as possible until book $b_i$ does not fit, and then repeat the same process on subsequent shelves) does not always give the minimum overall height.  

\item Give a dynamic programming algorithm that computes the height of the optimal arrangement, and analyze its time and space complexity. (\emph{Hint. We have done a similar
example in class with a different cost function and constraints.}) 
\end{enumerate}

\end{question} 
\begin{solution}
\end{solution}

\end{document}



