CSCI 3136 Dalhousie University Binary Research Tree Programming Project

CSCI3136Assignment 10
Instructor: Alex Brodsky
Due: 9:00am, Monday, July 26, 2021
1. [5 marks] In one of the examples for Lecture 20, we saw how to implement a closure that
can be used with the list-visitor function to compute the average of a list. Using the
example as a starting point, implement a function called new-max2, which returns a closure
that can be used with the list-visitor function to compute the second largest number in
a list of numbers.
Write the new-max2 function in a file called max2-visitor.scm.
2. [5 marks] A list iterator iterates over a list. Each time the iterator is called, it returns
the next item in a list. Implement a function called new-sqrt-iterator that takes a list of
numbers as an argument and returns an iterator (implemented using a closure) that returns
the square root of the next item in the list when it is called. Once the list is empty, the
boolean #f should be returned. For example
> (define sql (new-sqrt-iterator ’(1 2 3 4)))
> (sql)
1
> (sql)
1.4142135623730951
> (sql)
1.7320508075688772
> (sql)
2
> (sql)
#f
>
Write the new-sqrt-iterator function in a file called sqrt-iterator.scm.
Note: Scheme has an sqrt function that returns the square root of a number.
3. [5 marks] Using your code from Question 2 as a starting point, Implement a function called
new-square-iterator that takes a list of numbers as an argument and returns an iterator
(implemented using a closure) that returns the perfect square in the list when it is called.
Once the list is empty, the boolean #f should be returned. For example
> (define squ (new-square-iterator ’(1 2 3 4)))
> (squ)
1
> (squ)
1
CSCI3136
Summer 2021
Assignment 10
4
> (squ)
#f
>
Write the new-square-iterator function in a file called square-iterator.scm.
Note: the Scheme expression (integer? (sqrt x)) evaluates to true if and only if the
square root of x is an integer.
4. [5 marks] Rewrite the following code as a tail-recursive function, called product-tr. Write
the product function in a file called product.scm.
(define product (lambda (L)
(if (null? L)
1
(* (product (cdr L)) (car L))
)
)
)
5. [Bonus 5 marks] Using the code in bst.scm as a starting point implement a function called
new-bst-iterator that takes a BST as an argument and returns an iterator (implemented
using a closure) that returns the next item in a pre-order traversal of the BST when it is
called. Once the traversal is complete, the boolean #f should be returned.
Write the new-bst-iterator function in the file bst.scm.
Marking Scheme
1. Marking scheme for Questions 1, 2, 3, 4, and 5 (Bonus).
Solution
3 points
2 points
1 point
0 points
Solution looks correct
and covers all cases
Solution looks mostly
correct and covers
some cases
Solution represents a
good attempt
No solution provided
Solution works on test
input
Solution works
some test inputs
Solution
work
Functionality
on
does
not
2. Marking scheme for overall code clarity.
Understandability
Formatting
2 points
1 point
0 points
Code is easy to understand
Code is a little hard to understand
Code is unintelligible or not
submitted
Code is well formatted and
indented
Code is inconsistently formatted
Code is poorly formatted or
not submitted
Comments are used where
appropriate
No comments present or no
code submitted
Commenting
2
CSCI3136: Assignment 10
Summer 2021
Student Name Login ID
Student Number Student Signature
Mark
Question 1
Question 2
Question 3
Question 4
Bonus Question 4
Overall code clarity
Total
/5
/5
/5
/5
/5
/5
/25
Comments:
Assignments are due by 9:00am on the due date. Assignments must be submitted electronically via Brightspace. Please submit a zip (.zip) file of your code. Please do not use another
archiving format as the markers may not be able to open it.
Plagiarism in assignment answers will not be tolerated. By submitting their answers to
this assignment, the authors named above declare that its content is their original work and
that they did not use any sources for its preparation other than the class notes, the textbook,
and ones explicitly acknowledged in the answers. Any suspected act of plagiarism will be
reported to the Faculty’s Academic Integrity Officer and possibly to the Senate Discipline
Committee. The penalty for academic dishonesty may range from failing the course to expulsion from the university, in accordance with Dalhousie University’s regulations regarding
academic integrity.
;
;
;
;
Binary Search Tree
Idea: represent a BST node as (value left right)
if left == () there is no left child
if right == () there is no right child
(load “io.scm”)
; main binary search tree loader
; params: list of strings to be inserted into the BST
; return: a BST
(define load-bst (lambda (values)
(let ((dummy ‘(“@” () ())))
; use a dummy
node to avoid boundary
(load-bst-helper dummy values)
; cases
)
)
)
; recursive helper used to iterate over the list and
insert items into
; a BST
; params: root: root of BST
;
values: remaining list of strings to be
inserted
; return: a BST
(define load-bst-helper (lambda (root values)
(if (null? values)
; empty list
is the base case
root
(let ((elem (car values)) (remaining (cdr
values)))
; use a couple
(let ((new-root (add-to-bst root
elem)))
; let to make call
(load-bst-helper new-root
remaining)
; simpler
)
)
)
)
)
; insert a new string into the BST, using standard
algorithm
; params: root: root of BST
;
values: remaining list of strings to be
inserted
; return: a BST
(define add-to-bst (lambda (root value)
; we use root-val, left, and right, a couple
times
; so compute once, use many
(let ((root-val (car root)) (left (car (cdr
root)))
(right (car (cdr (cdr
root)))))
(if (string