;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname HW02) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f () #f)))
u;; **Problem 1**
;; Given
(define-struct BTMNode (key value left right)) ;; abbreviated name for BinaryTreeMapNode
;; A alpha-BTM (alpha-BinaryTreeMap is either
;; * empty, or
;; * (make-BTMNode key value left right) where
;; * key is a number;
;; * value is an alpha;
;; * left and right are of type alpha-BTMap
;; Generic Template for any function f with primary argument a of type alpha-BTM
#|
(define (f ... abstm ...)
(cond [(empty? abstm) ...]
[(BTMNode
... (BTMNode-key abstm)
... (BTMNode-value abstm)
... (f ... (BTMNode-left abstm) ...)
... (f ... (BTMNode-right abstm) ...)
... ]))
|#
;; A alpha-BSTM (alpha-BinarySearchTreeMap) is an alpha-BTM arbst that is either;
;; * empty, or
;; * a BTMNode (make-BTMNode k v l r) where every key in l < k and every key in r > k (implying key values are unique)
;; getBSTM: number BSTM -> symbol
;; Purpose: (getBSTM n abstm) returns the symbol s in the BTMNode matching n if such a BTMNode exists and empty otherwise
;; Examples
;; <##your test code goes here##>
;; Hint: you may want to define some number-BSTM constants to avoid text repetition in your test code
;; Template Instantiation
#|
<##your template code goes here##>
|#
;; Code
;; <##your code for getBSTM goes here##> (approximately 5 lines)
;; Analysis: searching trees vs. searching lists
;;<##your brief (a few lines) discussion goes here##>
;; **Problem 2**
;; In this problem, we assume the programmer and the reader are very familiar with the inductive type alpha-list (listOf alpha), so those associated data definition, examples, and
;; corresponding natural recursion template are omitted here.
;; For the sake of simplicity, we will represent an ordered pair (a,b) of type (alpha,beta) as two element list (list a b). We will call such a pair an alpha-beta-pair.
;; cross: number-list symbol-list -> number-symbol-pair-list
;; purpose: given a number-list nl and a symbol-list sl, (cross nl sl) returns a list of all possible pairs (n, s) where n is a member of nl and s is a member of sl.
;; Examples:
(check-expect (cross '(1 2) '(a b c)) '((1 a) (1 b) (1 c) (2 a) (2 b) (2 c)))
(check-expect (cross '(1 1) '(a b c)) '((1 a) (1 b) (1 c) (1 a) (1 b) (1 c)))
;; <##you need to include more examples, sufficient to cover your code including base cases and the simple inductive constructions.##>
;; Template Instantiations for cross
;; Hints:
;; 1. The visible function cross performs natural recursion on one argument (say nl). Introduce a cross-help function that performs natural recursion on the other argument (say sl).
;; 2. In developing your code, you may want to write and test cross-help first because it can be tested by itself while cross cannot.
;; 3. After giving the template instantiation for cross, show your development of cross-help including type contract, purpose statement, and template instantiation. You may
;; omit examples since they will be generated by your top level tests if your top-level coverage is good.
;; Template instantiation for cross
#|
<##your template instantiation for cross which invokes cross-help goes here##>
|#
;; <##your type contract, purpose statement, and template instantiation for cross-help all go here; examples for cross-help are optional##>
;; Code for cross and cross-help
;; Hint: Aim for simplicity; do not worry about using append to concatenate lists a linear number of times.
;;<##Your code for cross and any help functions goes here.##>
;; Problem 3
;; As in Problem 2, we assume the programmer and the reader are very familiar with the inductive type alpha-list (listOf alpha). Hence, the associated data definition, examples, and
;; corresponding natural recursion template are omitted here. The function that you must write below is discussed in detail in Section 17.6 of the book. But we expect you to develop
;; a better solution given the following guidance. In your definition of merge, use simple structural case-splitting on both list arguments WITHOUT ANY RECURSION. The second case
;; split is nested inside one arm of the first case split; the ordering of the argument queries does not matter. For the case where the result cannot be immediately computed without
;; help (both arguments are non-empty), delegate the remainder of the computation to a help function merge-help. In contrast to the code for the merge function, the code for
;; merge-help function is recursive but its argument types are not identical. One argument is a non-empty ascending number-list and the other is simply an
;; ascending number-list. The template for merge-help case splits on whether the possibly empty list is empty or non-empty and performs quasi-structural recursion (it may
;; swap arguments, but the sum of the length of the two arguments strictly decreases in every call).
;; We will use the wrapper (ascending ...) enclosing a number-list parameter in a type contract to indicate that the parameter must be bound to an ascending [technically
;; non-descending] number-list. We will similarly use the wrapper (non-empty ...) enclosing a (possibly restriced) number-list parameter to indicate that the parameter must be bound
;; to a non-empty number-list.
;; merge; (ascending number-list) (ascending number-list) -> (ascending number list)
;; purpose; given two ascending number-lists nl1 and nl2, (merge nl1 nl2) returns the list containing all elements in both lists in ascending order
;; Examples
;; <##your examples for merge and merge-help (assuming you define one) go here##>
;; Template Instantiation for merge
;; <##your template instantiation for merge invoking merge-help goes here##>
;; <##your type contract, purpose statement, and template instantiation for merge-help go here; examples are optional.##>
;; Code
;;<## your code for merge-help and merge goes here; merge-help first ##>
;; Problem 4
;; The Fibonacci function fib is defined by the recursion equation:
;; fib(n) = fib(n-1) + fib(n-2) for n > 1
;; where fib(0) = fib(1) = 1.
;; The following Racket program computes fib(n) using this definition:
(define (fib n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))
;; <##Your type contract, purpose statement, examples, and template instantation for fastFib go here.##>
;; Hints;
;; 1. Your template instantiation for fastFib will be trivial because it will delegate essentially all of the computation to the help function fastFib with the
;; following description:
;; fibHelp: nat nat nat -> nat
;; Purpose: (fibHelp k fn-k-1 fn-k-2) returns (fib n) provided that fn-k-1 = (fib (- n k 1), fn-k-2 = (fib (- n k 2))
;; Note: in Racket (- n k i) returns (n-k)-i
;; Examples (included here to show you how fastFib works
;(check-expect (fibHelp 0 1 1) 2)
;(check-expect (fibHelp 0 2 1) 3)
;(check-expect (fibHelp 1 (fib 9) (fib 8)) (fib 11))
;; 2. You need to fully develop fibHelp as a Racket function; some of what you need appears above in the description of fibHelp including template instantiation. Examples
;; for fibHelp are optional but you already have three given above.
;; Code
;; <## your code for fastFib and fibHelp goes nere, fibHelp first ##>
;; Problem 5 (Extra Credit)
;; This problem is reasonably hard and time-consuming so if you are interested, don't tackle it until you have done the regular problem very thorougly. You can hand in a solution to
;; extra credit problem (in contrast to the main assignment) as late as Sunday at 11:59pm.