To practice working with multiple complex inputs.

Expectations
    • You and your partner must submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept no email submissions.
    • You must use the language specified at the top of this page.
    • Your code must conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses, so revisit it before submitting each assignment. (You can resubmit as many times as you like until the due date without penalty.)
    • Unless otherwise stated, every function and data definition that you design, including helper functions, must follow all steps of the design recipe.
Failure to comply with these expectations will result in deductions and possibly a 0 score.
Graded Exercises:
This homework is primarily exercising your abilities with manually handling multiple complex inputs. For all exercises, unless an explicit exemption is indicated, you cannot use any function that extracts from, summarizes or modifies, a list; so, no calls to list-ref, reverse, length, second, third, fourth, etc., nor any list abstractions (you had sufficient practice with those on past homeworks and the exam). You are only allowed to call first and rest, and the predicates empty? and cons? on lists. (For data types other than lists, there are no such restrictions.) The usual rule of having a sufficient number of test cases applies, with a minimum of 3, but this is only a lower limit: some functions will clearly need more tests.
Exercise 1 Design the predicate function list-prefix? that accepts two lists of Numbers, and returns #true if the first list is a prefix of the second list, meaning all the elements of the first list occur, in that specific order, as the first n elements of the second list.
Exercise 2 Design the function max-splice which given two lists of Numbers, will create the shortest resulting list which begins with all of the elements of the first list, in original order, and ends with all of the elements of the second list, again in original order, taking advantage of any overlap to shorten the result. Here are a couple of illustrative examples:
(check-expect (max-splice '(1 2 3 4) '(2 3 4 5)) '(1 2 3 4 5))
; but:
(check-expect (max-splice '(1 2 3 4) '(2 2 3 4 5)) '(1 2 3 4 2 2 3 4 5))
In your implementation, you may use your solution for list-prefix? from the previous exercise.
Exercise 3 Design the predicate function valid-results?, which is given three lists of equal length:
    • a list of input values
    • a list of functions
    • a list of results
For each member i of the first list, it will apply the function at the corresponding position in the second list to i, and compare the output with the result in the corresponding position in the third list. valid-results? should return #true if all of the function call outputs match the expected results.
Exercise 4 Design the function assign, which matches up members of a list of roles, each of type Symbol, with corresponding members of a list of people, which are of type String; if the list of people is shorter, unfilled roles are paired with #false (so the second field should be a [Maybe String]; however, if the list of people is longer, the extra people (beyond the number of roles) should be ignored. The result should be a [List-of Assignment], defined here:
(define-struct assignment (role person))
; An Assignment is a (make-assignment Symbol [Maybe String])
For the next set of exercises, you will be using a very simple version of a data type for representing a binary tree:
(define-struct bt [value left right])
; A BT (Binary Tree) is one of:
; - 'none
; - (make-bt Symbol BT BT)
Exercise 5 For this problem, you will design the function tree-equiv, which compares two trees for alignment, with an important twist: it allows any two trees to be considered equivalent if each contains subtrees equivalent to one of the subtrees in the corresponding other tree. So, these two trees would be reported as equivalent:
; 
;          a                          a
;       /     \                    /     \
;      b       c                  c       b  
;     / \     / \                / \     / \
;    d   e   f   g              f   g   e   d
; 
Another way to think of it is: for a family tree, what if instead of a father and mother, you just identified two equivalent parents? (For this, you will need more than the typical number of test cases.)
Exercise 6 Design the function find-subtree, which given two parameters: a tree, as well as a subtree to scan for (both of type BT), will search the main tree (the first parameter) for the matching subtree. Here, we are looking for an exact match, all the way down to the leaves (the value 'none), and not a flippable one as in the previous exercise. Note that values stored at various nodes can repeat, so you cannot simply look for a matching root node and asume the subtree therefore matches. Also, you can stop at the first full match, in the case where the subtree occurs multiple times in the main tree.
Exercise 7 Design a function max-common-tree, which given two binary trees (again, continuing with the data type given earlier in this homework, of type BT), will compare the two trees starting with the root of each, returning a tree that shares the maximum number of nodes with both source trees, starting from the root. Since the resulting tree must also be a BT, it will have leaves with the symbol 'none— 'none):
; 
;  t1:     A                 t2:      A
;       /     \                    /     \
;      B       C                  B       X  
;     / \     / \                / \     / \
;    D   E   F   G              D   Y   F   n
;   / \ / \ / \ / \            / \ / \ / \
;   n n n n n n n n            n n n n n n 
 
;            result1:   A         result2:    A
;                    /     \               /     \
;                   B       n             B       n
;                  / \                   / \
;                 D   n                 n   n
;                / \
;               n   n
; 
The tree result1 is the correct answer. Note that the node 'F doesn’t appear in the common tree, even though it appears in the same position, and with the same value, in both source trees, because the node 'C in tree t1 does not match corresponding node 'X in tree t2, cutting off anything below them. While result2 is in fact a common tree of both t1 and t2, it is not the maximal such tree, and is therefore incorrect.
Exercise 8 To find an existing value in a Binary Search Tree (BST), you have to turn left or right correctly at every node as you descend a BST, by examining the value stored at each node you visit, and then deciding to go down the left or right branch. Your goal for this exercise is to design a function that can validate a search algorithm’s decisions as it descends a BST, as well as the correctness of the BST’s structure, at least the part you traverse. You will design a function valid-bst-path? , which is passed a binary search tree, and a number that is stored in that tree, as well as a search path, defined as a [List-of Dir], i.e., a sequence of 'left and 'right turns. Your function must validate every left/right decision in the given path, as well as whether you end up at the correct node. It should return #true if the passed path makes the correct branching decision at each node, as well as arriving at the desired node. Note that just arriving at the correct node at the end is not sufficient, since you are also validating parts of what might be a malformed tree. You do not have to validate the whole BST: just opportunistically check the parts along the path.
You can assume that a Dir data type is already defined, as follows:
; A Dir is one of:
; - 'left
; - 'right
Note that while you should typically call out to a helper function to handle the Dir data type in the [List-of Dir], here you are allowed to handle it directly in the main function as we did in the lecture example involving a FamilyTree and AncestorPath, but only if the design is still sufficiently simple and clear.
Exercise 9 Design the function merge, that takes two ordered lists containing elements of the same type (not necessarily numbers!), and produces a single resulting ordered list. Note that the user passes in a comparison function lt-func, which takes two parameters, and will return #true if the first parameter is "less than", i.e., should come before, the second. You are not allowed to call DrRacket’s sort function!