int ","DT "," DT "]". Leaf = "{" "\"h\" " ":" int "}". \end{verbatim} \noindent 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. \\ \\ \noindent A decision tree t in DT for HSR(n,k,q) must satisfy the following properties: (a) 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. (b) there are at most k yes from the root to any leaf. (c) the longest root-leaf path has q edges. (d) each rung 1..n-1 appears exactly once as internal node of the tree. (e) each rung 0..n-1 appears exactly once as a leaf. \\ \noindent 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). \\ \noindent To test your trees, you can download the JSON HSR-validator from the url: \noindent\texttt{https://github.com/czxttkl/ValidateJsonDecisionTree} \\ \noindent\textbf{G(extra credit, 20 points).} 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. \solution \begin{prob} \textbf{(20 points)} Problem 15-2. Hint: try to use the LCS problem as a procedure. \end{prob} \solution \begin{prob} \textbf{(30 points)} Exercise 15.4-6. \end{prob} \solution \begin{prob} \textbf{(Extra Credit 20 points)} \end{prob} 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. \solution \begin{prob} \textbf{(20 points)} Problem 15-4. \end{prob} \solution \begin{prob} \textbf{(20 points)} Problem 15-10. \end{prob} \solution \end{document}