%%Do not change font size
\documentclass[12pt]{article}
\usepackage{amsthm,amssymb,fullpage}
\begin{document}

\begin{center}
\begin{tabular}{|c|}
\hline
CS 5800: Algorithms \hspace{9cm} Virgil Pavlu\\
{\bfseries \large Homework 6: Dynamic Programming part II}\\  \hline

% {\bfseries \large Homework 04}\\ \hline
\end{tabular}
v1
\end{center}

%\section{Write here}
% \textbf{\large{Instructions}}
% 
% \begin{enumerate}
% \item Please review the grading policy  outlined in the course information page.
% \item You must also write down with whom you worked on the assignment. If this changes from problem to problem, then you should write down this information separately with each problem.
% \item Problem numbers (like Exercise 3.1-1) are corresponding to CLRS $3^{rd}$ edition. While the $2^{nd}$ edition has similar problems with similar numbers, the actual exercises and their solutions are different, so make sure you are using the $3^{rd}$ edition.
% \end{enumerate}


\textbf{\large{Problems}}
\begin{enumerate}

\item (optional, no credit). Using the class notes (without the book), finish the Optimal BST and completely write the solution (including the DP recipe elements 1,2A,2B,3,4,5). Then compare your writeup with the book chapter.  

\item Jars on a ladder problem. Given a ladder of $n$ rungs and $k$ identical glass jars, one has to design an experiment of dropping jars from certain rungs, in order to find the highest rung (HS) on the ladder from which a jar doesn't break if dropped. 

	\textit{Idea: With only one jar (k=1), we can't risk breaking the jar without getting an answer. So we start from the lowest rung on the ladder, and move up. When the jar breaks, the previous rung is the answer; if we are unlucky, we have to do all n rungs, thus n trials.
	Now lets think of k=log(n): with log(n) or more jars, we have enough jars to do binary search, even if jars are broken at every rung. So in this case we need log(n) trials. Note that we can't do binary search with less than log(n) jars, as we risk breaking all jars before arriving at an answer in the
	worst case.} %One can devise the following mixed strategy: do binary search until only one jar stands, then switch to linear search... but is this strategy optimal (minimum number of drops required for worst case)?}
	
Your task is to calculate $q=MinT(n,k)$= the minimum number of dropping trials any such experiment has to make, to solve the problem even in the worst/unluckiest 
case (i.e., not running out of jars to drop before arriving at an answer).
$MinT$ stands for Minumum number of Trials.

	\textbf{A(5 points).} Explain the optimal solution structure and write a recursion for  $MinT(n,k).$

	\textbf{B(5 points).} Write the alternative/dual recursion for $MaxR(k,q)$ = the Highest Ladder Size $n$ doable with $k$ jars and maximum $q$ trials. Explain how $MinT(n,k)$ can be computed from the table $MaxR(k,q).$
$MaxR$ stands for the Maximum number of Rungs.
	
	\textbf{C(10 points).} For one of these two recursions (not both, take your pick) write the bottom-up non-recursive computation pseudocode.
	% that fills the entire table. 
	\textit{Hint: the recursion $MinT(n,k)$ is a bit more difficult and takes more computation steps, but once the table is computed, the rest is easier on points E-F below. The recursion in $MaxR(q,k)$ is perhaps easier, 
	but trickier afterwards: make sure you compute all cells necessary to get $MinT(n,k)$---see point B.}
	
	\textbf{D(10 points).} Redo the computation this time top-down recursive, using memoization. 
%	Is it actually filling the entire table, or the needed cells are fewer than all?
	
	\textbf{E(10 points).} Trace the solution. While computing bottom-up, use an auxiliary structure that can be used to determine the optimal sequence of drops for a given input $n,k$. The procedure TRACE($n,k$) should output the ladder rungs to drop jars, considering the dynamic outcomes of previous drops. \textit{Hint: its recursive. Somewhere in the procedure there should be an \textbf{if statement} like ``if the trial at rung x breaks the jar... else ...''}
	
\newpage	
\textbf{F(optional, no credit).} Output the entire decision tree from part E) using JSON to express the tree, for the following test cases : (n=9,k=2); (n=11, k=3); (n=10000,k=9). 
Turn in your program that produces the optimum decision tree for given n and k using JSON as described below.
Turn in a zip folder that contains: (1) all files required by your program (2) instructions how to run
your program (3) the three decision trees in files t-9-2.txt, t-11-3.txt and t-10000-9.txt (4) the answers
to all other questions of this homework.

To represent an algorithm, i.e., an experimental plan, for finding the highest safe rung for fixed n,k, and q we use a restricted programming language that is powerful enough to express what we need. We use the programming language of binary decision trees which satisfy the rules of a binary search tree. The nodes represent questions such as 7 (representing the question: does the jar break at rung 7?). The edges represent yes/no answers. We use the following simple syntax for decision trees based on JSON. The reason we use JSON notation is that you can get parsers from the web and it is a widely used notation.
A decision tree is either a leaf or a compound decision tree represented by an array with exactly 3 elements.

\begin{verbatim}
// h = highest safe rung or leaf 
{ "decision_tree" : [1,{"h":0},[2,{"h":1},[3,{"h":2},{"h":3}]]] }
\end{verbatim}

The grammar and object structure would be in an EBNF-like notation:
\begin{verbatim}
DTH = "{" "\"decision_tree\"" ":" <dt> DT. 
DT = Compound | Leaf. 
Compound = "[" <q> int "," <yes> DT "," <no> DT "]". 
Leaf = "{" "\"h\" " ":" <leaf> int "}".
\end{verbatim}


This approach is useful for many algorithmic problems: define a simple computational model in which to define the algorithm. The decision trees must satisfy certain rules to be correct.

A decision tree t in DT for HSR(n,k,q) must satisfy the following properties:
\begin{enumerate}
\item the BST (Binary Search Tree Property): For any left subtree: the root is one larger than the largest node in the subtree and for any right subtree the root is equal to the smallest (i.e., leftmost) node in the subtree.
\item there are at most k yes from the root to any leaf.
\item the longest root-leaf path has q edges.
\item each rung 1..n-1 appears exactly once as internal node of the tree.
\item each rung 0..n-1 appears exactly once as a leaf.
\end{enumerate}	

If all properties are satisfied, we say the predicate correct(t,n,k,q)
holds. HSR(n,k,q) returns a decision tree t so that correct(t,n,k,q).

To test your trees, you can download the JSON HSR-validator from the url:\\
\texttt{https://github.com/czxttkl/ValidateJsonDecisionTree}

\textbf{G(optional, no credit).} Solve a variant of this problem for $q$ = MinT(n,k) that optimizes the average case instead of the worst case: now we are not concerned with the worst case $q$, but with the average $q$. Will make the assumption that all cases are equally likely (the probability of the answer being a particular rung is the same for all rungs). You will have to redo points A,C,E specifically for this variant.
	
\vspace{10ex}	
\item (20 pts) Problem 14-2. Hint: try to use the LCS problem as a procedure.
\item (30 pts) Exercise 14.4-6. 
\item (optional, no credit) Suppose that you are the curator of a large zoo. You have just received a grant of \$$m$ to purchase new animals at an auction you will be attending in Africa. There will be an essentially unlimited supply of $n$ different types of animals, where each animal of type $i$ has an associated cost $c_i$. In order to obtain the best possible selection of animals for your zoo, you have assigned a value $v_i$ to each animal type, where $v_i$ may be quite different than $c_i$. (For instance, even though panda bears are quite rare and thus expensive, if your zoo already has quite a few panda bears, you might associate a relatively low value to them.) Using a business model, you have determined that the best selection of animals will correspond to that selection which maximizes your perceived profit (total value minus total cost); in other words, you wish to maximize the sum of the profits associated with the animals purchased.

Devise an efficient algorithm to select your purchases in this manner. You may assume that $m$ is a positive integer and that $c_i$ and $v_i$ are positive integers for all $i$. Be sure to analyze the running time and space requirements of your algorithm. 

\item (20 points) Problem 14-4.

% \item (20 points) Problem 14-10. Assume that you invest a fixed amount $d=10,000$ every year (i.e. you do not reinvest your profits).

% \item (Extra Credit 20 points) Problem 15-5.


\end{enumerate}


\end{document}
