Homework 11
Due Date: Wed April 16, 9pm
Purpose To practice with accumulators and trees
Expectations
You should have a single file with your solutions to all of the exercises. Please label where your solution for each exercise begins very, VERY clearly! You should then submit this common file to each of the HW11-related entries on the Handin Server; the file should be named "HW11.rkt". We accept NO email submissions. Failure to submit a .rkt file will result in a 0 for that part.
You are only allowed to use the language specified at the top of this page: failure to do so will result in a 0. For this assignment, you must use ISL+Lambda. (remember to correctly set the mode in DrRacket). Using the wrong language will invalidate your submission and result in a score of 0, so please be careful.
Your code must conform to the guidelines outlined in the style guide on the course website. Pay particular attention to the list of prohibited functions in the guide. The style guide may be updated as the semester progresses so please remember to read it before submitting each assignment.
Unless otherwise stated, all data and functions you design must be designed according to the data and function design recipes (DR), resp., following all four steps in each case, with the exception of functions that call big-bang, for which you need no check-expects, as justified in class, and local functions, which need example comments in place of check-expects. All functions used inside big-bang must have check-expects, along with the other three steps of the design recipe.
-----------------------------------------------------------------------------
Introduction
For this assignment, you will be practicing applications of accumulators to various problems. An important constraint on the solutions for all of the exercises here: You are prohibited from using any list-creating functions; in particular, you may not ever call list, cons, or append, or any of the list abstractions. You may also not construct any new structures at all, so no calls to functions that begin with make-. The one exception is for constructing examples and tests. You are also not allowed to use define-struct, except in the data definitions we provided.
Exercise 1 Binary Search Trees Here is the data design for a binary tree of numbers:
(define-struct btnode [value left right]) ; A BinaryTree is one of ; - #false ; - (make-btnode Number BinaryTree BinaryTree) ; Interpretation: Represents a binary tree with nodes containing numbers ; Examples: <TO BE CREATED BY STUDENT> (define (bt-temp bt) (cond [(boolean? bt) ...] [(btnode? bt) (... (btnode-value bt) ... (bt-temp (btnode-left bt)) ... (bt-temp (btnode-right bt)) ...)])) From this data definition, we can derive the definition for a special class of binary trees known as a binary search tree (BST). A binary search tree is defined as a subset of binary trees:
; A BST is a BinaryTree that is constrained to be a binary search tree: ; At every _(make-btnode value left right)_ in a BST, all node-values in the ; _left_ subtree are less than _value_ and all node-values in the _right_ ; subtree are greater than _value_. For simplicity’s sake, and without loss of generality, we typically constrain a BST to not have any duplicate values. (It is trivial to extend BSTs to allow duplicates, but it is easier to describe w/o duplicates.)
For this exercise, design the function valid-bst? which accepts a BinaryTree and produces #true if and only if its argument is a BST.
One naive way to solve this problem would be to write a function that produces a list of the node values, and then checks that the list is in ascending order. The problem with this approach is that it effectively visits all nodes twice: once in the tree, and then again in the list. You will get no credit if you use this approach.
In fact, for this problem, you are prohibited from using any list-creating functions (see the additional prohibited functions in the general intro section above). So, no list, cons, or append, or any of the list abstractions. You may also not create any additional structures at all, and specifically, you may not use define-struct nor any functions that begin with make-, except to construct examples and tests. This implies you specifically cannot call make-btnode from inside your functions.
You must use an approach that visits each node at most once (i.e., call node-value only once on any given node). However, you can use local definitions to fetch and temporarily save a value field–then using that local variable multiple times would not count as multiple access.
Hints:
You will need to write a helper function with two accumulators.
ISL has the two constant values -inf.0 ands +inf.0, which represent negative infinity and positive infinity, respectively. These might be useful. In particular, (< -inf.0 x) and (> +inf.0 x) will be true for any real numerical value x.
Try drawing a BST with at least five nodes. What are the constraints on the values at each node?
Exercise 2 Smaller Accumulator Problems
Note: the same restrictions against using list functions outlined in the introduction apply to all of the problems here!
Here’s the data design for a non-empty list:
; A [NEList-of X] is one of: ; - (cons X empty) ; - (cons X [NEList-of X]) ; Intepretation: Represent a list of elements of type X, which has at least one element (define (nelox-temp nelox) (cond [(empty? (rest nelox)) (... (first nelox) ...)] [(cons? (rest nelox)) (... (first nelox) ... (nelox-temp (rest nelox)) ...)])) Design the function index-of-max which accepts a non-empty list of numbers, and returns the index within the list of the greatest number in the list. If this number occurs more than once in the list, you must return the index of the first occurrence. For example:
(check-expect (index-of-max (list 1 5 9 4 7 9 3)) 2)
; A ParString is a String over the alphabet {"(",")"} ; representing an expression consisting of parentheses only. (define PS-0 "") (define PS-1 "()") (define PS-2 "(())") (define PS-3 "()()") (define PS-4 "())(") (define PS-5 "()(") (define PS-6 "())") (define PS-7 ")(") Design a function balanced-paren? that takes a ParString and returns true iff the string represents an expression with correctly nested parentheses. This means that parentheses occur in pairs across the expression (no unaccounted-for "(" or ")"), and a closing parenthesis can only occur when there is a pending open parenthesis. For example, the expressions represented by ParStrings PS-0 through PS-3 are correctly nested, while the others are not.
For this problem, you are allowed to use the function explode, which technically builds a list.
Include at least ten meaningful check-expects (eight of which can be the examples from above, but feel free to use others).
Hint: use an accumulator that tracks ... what? Also, consider the explode function, which turns the string into a list of length-1 strings, making it easier to process the expression.
The Fibonacci numbers, which are the numbers in the following sequence: 0 ,1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55 ,89 ,144 ,... are defined by the recurrence relation: Fn = Fn-1 + Fn-2, with seed values F0 = 0 and F1 = 1. Design the function fibonacci which consumes a NaturalNumber and produces its Fibonacci number. For example, (fibonacci 11) should produce 89.
Use accumulators to make your implementation efficient, i.e., the computation should take time directly proportional to the index. The time it takes to compute the 200th Fibonacci number should be roughly double the time it takes to compute the 100th.