\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 CS256:~Algorithm Design and Analysis \hfill #1} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #2 \normalsize{(#3)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #4 \hfill  } }
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}

\begin{document}
\homework{Spring 2024}{Assignment 4}{due 04/03/2024 9:59pm}{Sam McCauley}{}

\begin{question}
	The following word problem is \emph{related} to divide and conquer, but the final solution is not necessarily a divide and conquer algorithm like the ones we've seen.  This question is more about divide and conquer intuition.

	One of your Amazon packages has been lost.  You suspect that it's in a specific warehouse, so you take your tracking number and drive over to the warehouse to find your package.

	Unfortunately, on arrival, you find that there are no people at the warehouse, only a fairly unhelpful robot.  The robot will only answer questions of the form: ``what is the $i$th largest tracking number in the warehouse?''  The robot will either give you the $i$th largest tracking number, or answer that there are fewer than $i$ packages in the warehouse (despite its limited capabilities, the robot always answers these questions correctly).

	\bigskip
	(a) Assume for a second that you know that there are $n$ packages in the warehouse.  Describe in 1-2 sentences how to determine if your package is in the warehouse (in other words, if one of the packages in the warehouse has your tracking number) by asking the robot $O(\log n)$ questions.

	\begin{solution}
		
	\end{solution}

	(b) In reality, you have no bound on the number of packages in the warehouse $n$.\footnote{To be clear, due to the efficiency of Amazon, assume you have \emph{no} upper bound on the number of packages in the warehouse; it could potentially be larger than any number you come up with.  The only way you can bound the number is via questions to the robot.}  Describe how you can, nonetheless, determine if your package is in the warehouse by asking the robot $O(\log n)$ questions.  

	\bigskip
	\textbf{Hint:}  If you obtain a bound on $n$ via your questions, you can essentially use your answer from part (a).

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

\newpage

\begin{question}(Erickson 3.3) Suppose you are given a $1$-indexed array $A[1,\ldots, n]$ of numbers, which may be positive,
negative, or zero, and which are not necessarily integers. 

Describe and analyze an algorithm that finds the largest sum of elements
in a contiguous subarray $A[i \ldots j]$. So if the array consists of only positive numbers, then the largest sum of contiguous elements would just be the sum of all the elements.   
If the array is only made up of negative numbers, then the largest subarray is made up of the number closest to $0$.  (To simplify things, we are not allowing empty subarrays).

As an example consider an array $A = [-6, 12, -7, 0, 14, -7, 5]$, then the contiguous subarray with the largest sum is $[12, -7, 0, 14]$ with the sum of $19$.
If the subarray is $B=[-4, -1]$, then the contiguous subarray with the largest sum is $[-1]$ with the sum of $-1$.



\textbf{Note.} This problem has been a standard computer science interview question
since at least the mid-1980s and can be solved via a variety of approaches.  We will use a dynamic-programming approach for this question.  


This dynamic programming problem is similar to the longest increasing subsequence problem we discussed in class.

\begin{itemize}
    \item {\bf Subproblem definition:} Let $M(i)$ denote the optimal (largest) subarray sum ending at index $i$ of the array (and including $A[i]$).
    
    \item {\bf Recurrence:}  
    
		\begin{solution}
			\textcolor{red}{Students, fill in the recurrence}
		\end{solution}

    \item {\bf Base Case:}  
    
		\begin{solution}
			\textcolor{red}{Students, fill in the base case}
		\end{solution}

    \item {\bf Final solution:} given by taking the maximum over all the $M(j)$'s that is, $\max_{1 \leq j \leq n} M(j)$.
    
    
		\begin{solution}
			\textcolor{red}{Students, fill in the final solution}
		\end{solution}
    
    \item {\bf Memoization structure:}  We can store the values of $M[1, \ldots, n]$ in a linear size array. 

    \item {\bf Evaluation order:} the evaluation of the dynamic program proceeds left to right, starting from $j = 1$ and going up to $j = n$.
    
    \item {\bf Time and space analysis:}  

		\begin{solution}
			\textcolor{red}{Students, fill in the time and space analysis} 
		\end{solution}
\end{itemize}

\end{question}


\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, the maximum weight of an independent set in the path in Figure~\ref{fig:path} is $14$.

%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}\caption{The maximum weight of an independent set is $14$ in this example.}\label{fig:path}
  \end{figure}
  
  



\begin{enumerate}[label = (\alph*)]
  \item Give a counterexample (a simple counterexample suffices!) to show that the following ``pick the heaviest weight'' greedy algorithm does not always work.  You should say what the greedy algorithm returns,
   and what the correct answer is.

    \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}

	\begin{solution}
		\textcolor{red}{Students, give your counterexample here}
			%The following code includes an image file; it may be helpful if you want to draw your solution

			%\begin{center}
				%\includegraphics[width=.7\linewidth]{figure.png}
		%\end{center}
	\end{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.  
\begin{itemize}
    \item {\bf Subproblem definition:} 

		\begin{solution}
			\textcolor{red}{Students, fill in the subproblem definition}
		\end{solution}
    
    \item {\bf Recurrence:}  
    
		\begin{solution}
			\textcolor{red}{Students, fill in the recurrence}
		\end{solution}

    \item {\bf Base Case:}  
    
		\begin{solution}
			\textcolor{red}{Students, fill in the base case}
		\end{solution}

    \item {\bf Final solution:} 

		\begin{solution}
			\textcolor{red}{Students, fill in the final solution}
		\end{solution}
    
    
    
    \item {\bf Memoization structure:}  We can store the values in a linear size array. 

    \item {\bf Evaluation order:} the evaluation of the dynamic program proceeds left to right, starting from $j = 1$ and going up to $j = n$.
    
    \item {\bf Time and space analysis:}  

		\begin{solution}
			\textcolor{red}{Students, fill in the time and space analysis} 
		\end{solution}
\end{itemize}
\end{enumerate}
\end{question} 




\newpage
\begin{question}(Kleinberg Tardos 6.3) Let $G = (V, E)$ be a directed acyclic graph where the topological ordering
of nodes is $v_1, \ldots, v_n$.  A  reminder that a topological ordering of a DAG has the following property: {\em each edge goes from a node with a lower index to a node with a higher index. That is, every directed
edge has the form $v_i, v_j$ with $i < j$.}  Thus, the source node $v_1$ has no incoming edges.
 
We further assume that in graph $G$ each node except $v_n$ has at least one outgoing edge.
See Figure~\ref{fig:2} for an example.



Given $G$ and its topological ordering, we want to find the {\em length} of the longest path that begins
at $v_1$ and ends at $v_n$.  (The length of a path is the number of edges in it.)

\begin{figure}[h]
\centering
	\includegraphics[width=.7\linewidth]{dag.png}
	\caption{The correct answer for this ordered graph is 3: 
the longest path from $v_1$ to $v_n$ uses the three edges $(v_1, v_2),(v_2, v_4)$, and $(v_4, v_5)$.}\label{fig:2}
\end{figure}

\begin{enumerate}[label=(\alph*)]

\item Show that the following algorithm does not correctly solve this problem, by giving a counterexample (again, a simple counterexample is fine). In your
example, you should say what the correct answer is and what the above algorithm finds.

    \begin{itemize}[noitemsep, nolistsep]
      \item Set $w = v_1$ and $L =0$ 
      \item While there is an edge out of node $w$:
        \begin{itemize}
          \item Choose the edge $(w, v_j)$ for which $j$ is as small as possible 
          \item Set $w = v_j$ and increment $L$ by $1$
        \end{itemize}
      \item Return $L$ as the length of the longest path 
    \end{itemize}

	\begin{solution}
		\textcolor{red}{Students, give your counterexample here}
			%The following code includes an image file; it may be helpful if you want to draw your solution

			%\begin{center}
				%\includegraphics[width=.7\linewidth]{figure.png}
		%\end{center}
	\end{solution}



\item Give an efficient dynamic programming algorithm that returns the {\em length} of the longest path that
begins at $v_1$ and ends at $v_n$.
\begin{itemize}
    \item {\bf Subproblem definition:} 

		\begin{solution}
			\textcolor{red}{Students, fill in the subproblem definition}
		\end{solution}
    
    \item {\bf Recurrence:}  
    
		\begin{solution}
			\textcolor{red}{Students, fill in the recurrence}
		\end{solution}

    \item {\bf Base Case:}  
    
		\begin{solution}
			\textcolor{red}{Students, fill in the base case}
		\end{solution}

    \item {\bf Final solution:} 
    
		\begin{solution}
			\textcolor{red}{Students, fill in the final solution}
		\end{solution}
    
    
    \item {\bf Memoization structure:}  We can store the values in a linear size array. 

    \item {\bf Evaluation order:} the evaluation of the dynamic program proceeds left to right, starting from $j = 1$ and going up to $j = n$.
    
    \item {\bf Time and space analysis:}  

		\begin{solution}
			\textcolor{red}{Students, fill in the time and space analysis} 
		\end{solution}
\end{itemize}

\end{enumerate}
\end{question}

\end{document}



