%---------change this for every latex homework
\def\yourid{mst3k}
\def\collabs{list collaborators's computing IDs}
\def\sources{Cormen, et al, Introduction to Algorithms. \emph{(add others here)}}
% -----------------------------------------------------
\def\duedate{Friday, April 15, 2022 at {\bf 11:30 pm}}
\def\duelocation{via Gradescope}
\def\htype{Basic}
\def\hunit{C}
\def\hnumber{1}
\def\course{{cs4102 - algorithms - spring 2022}}%------
%-------------------------------------
%-------------------------------------
\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage[top=1in,bottom=1.4in,left=1.25in,right=1.25in,centering,letterpaper]{geometry}
\usepackage{color}
\definecolor{mdb}{rgb}{0.1,0.6,0.4}
\definecolor{cit}{rgb}{0.05,0.2,0.45}
\pagestyle{myheadings}
\markboth{\yourid}{\yourid}
\usepackage{clrscode}
\usepackage{listings}
\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\handout}{
\renewcommand{\thepage}{Unit \hunit: \htype~Homework \hnumber~-~\arabic{page}}
\noindent
\begin{center}
\vbox{
\hbox to \columnwidth {\sc{\course} \hfill}
\vspace{-2mm}
\hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}\hunit\hnumber{\Large\MakeLowercase{\htype}}(\yourid)}}
}
\end{center}
\vspace*{1mm}
\hrule
\vspace*{1mm}
{\footnotesize \textbf{Collaboration Policy:} You are encouraged to collaborate with up to 3 other students, but all work submitted must be your own {\em independently} written solution. List the computing ids of all of your collaborators in the \texttt{collabs} command at the top of the tex file. Do not share written notes, documents (including Google docs, Overleaf docs, discussion notes, PDFs), or code. Do not seek published or online solutions for any assignments. If you use any published or online resources (which may not include solutions) when completing this assignment, be sure to cite by naming the book etc.\ or listing a website's URL. Do not submit a solution that you are unable to explain orally to a member of the course staff. Any solutions that share similar text/code will be considered in breach of this policy. Please refer to the syllabus for a complete description of the collaboration policy.
\vspace*{1mm}
\hrule
\vspace*{2mm}
\noindent
\textbf{Collaborators}: \collabs\\
\textbf{Sources}: \sources}
\vspace*{2mm}
\hrule
\vskip 2em
}
\newcommand{\solution}[1]{\color{blue}\hfill\break\noindent\textbf{Solution:} #1\color{black}}
\newcommand{\altsolution}[1]{\color{blue}\hfill\break\noindent\textbf{Solution (Alternative):} #1\color{black}}
%\newcommand{\solution}[1]{}
%\newcommand{\altsolution}[1]{}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
%\dontprintsemicolon
%\linesnumbered
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{practice}{\sc\color{cit}practice}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newcommand{\Z}{\mathbb{Z}} % This might be useful for Integers!
\begin{document}
\thispagestyle{empty}
\handout
%----Begin your modifications here. Add your answer in the \solution environment for each question
% Create an algorithm problem (Former exam problem)
\begin{problem}Birthday Prank\end{problem}
Prof Hott's brother-in-law loves pranks, and in the past he's played the nested-present-boxes prank. I want to repeat this prank on his birthday this year by putting his tiny gift in a bunch of progressively larger boxes, so that when he opens the large box there's a smaller box inside, which contains a smaller box, etc., until he's finally gotten to the tiny gift inside. The problem is that I have a set of $n$ boxes after our recent move and I need to find the best way to nest them inside of each other. Write a \textbf{dynamic programming} algorithm which, given a list of dimensions (length, width, and height) of the $n$ boxes, returns the maximum number of boxes I can nest (i.e. gives the count of the maximum number of boxes my brother-in-law must open).
\solution{
Your answer here!
}
\begin{problem}Arithmetic Optimization\end{problem}
You are given an arithmetic expression containing $n$ integers and the only operations are additions ($+$)
and subtractions ($-$). There are no parenthesis in the expression. For example, the expression might be: $1 + 2 - 3 - 4 - 5 + 6$.
You can change the value of the expression by choosing the best order of operations:
\begin{align*}
((((1 + 2) - 3) - 4) - 5) + 6 &= -3 \\
(((1 + 2) - 3) - 4) - (5 + 6) &= -15\\
((1 + 2) - ((3 - 4) - 5)) + 6 &= 15
\end{align*}
% You may not create multiplications; i.e., the following expression is {\em not} allowed:
% \[ (1 + 2)(-3 - 4 - 5) + 6. \]
Give a {\bf dynamic programming} algorithm that computes the maximum possible value of the expression. You may assume that
the input consists of two arrays: \texttt{nums} which is the list of $n$ integers and
\texttt{ops} which is the list of operations (each entry in \texttt{ops} is either \texttt{'+'}
or \texttt{'-'}), where \texttt{ops[0]} is the operation between \texttt{nums[0]} and \texttt{nums[1]}. \emph{Hint: consider a similar strategy to our algorithm for matrix chaining.}
\solution{
Your answer here!
}
\begin{problem}Optimal Substructure\end{problem}
Please answer the following questions related to \emph{Optimal Substructure}.
\begin{enumerate}
\item Briefly describe how you used \emph{optimal substructure} for the Seam Carving algorithm.
\solution{
Your answer here!
}
\item Do we need optimal substructure for Divide and Conquer solutions? Why or why not?
\solution{
Your answer here!
}
\end{enumerate}
\begin{problem}Dynamic Programming\end{problem}
\begin{enumerate}
\item If a problem can be defined recursively but its subproblems do not overlap and are not repeated, then is dynamic programming a good design strategy for this problem? If not, is there another design strategy that might be better?
\solution{
Your answer here!
}
\item As part of our process for creating a dynamic programming solution, we searched for a good order for solving the subproblems. Briefly (and intuitively) describe the difference between a top-down and bottom-up approach. Do both approaches to the same problem produce the same runtime?
\solution{
Your answer here!
}
\end{enumerate}
\begin{problem} Gradescope Submission \end{problem}
Submit a version of this \verb|.tex| file to Gradescope with your solutions added, along with the compiled PDF. You should only submit your \verb|.pdf| and \verb|.tex| files.
\end{document}