Programming Question

please give the comments. you can see the solution the teacher given. please follow the instructions. last time did not have enough comments to lose marks. also for last question please give good explanations

CSCI3136
Assignment 9
Instructor: Alex Brodsky
Due: 9:00am, Monday, July 19, 2021
1. [5 marks] In Assignment 8 you were asked to write a Scheme program (Factors.scm) that
computes the factors of an integer. Your solution probably used a separate helper function
to perform the actual loop (see solution to Assignment 8.)
Rewrite the factors function using a letrec expression so that the helper function is defined
inside the factors function. (See the reverse list example from Lecture 19.)
You can begin with your own solution to this problem from Assignment 8 or the provided
solution to Assignment 8 (Available July 15). Modify the file Factors.scm as described
above.
Input: One non-negative integer read from the console, e.g.,
12
Processing: Input will be a positive integer.
Output: Output a list of factors of the input. E.g., the output for the above input is:
(2 2 3)
2. [7 marks] In one of the examples, we saw the visitor pattern implemented on a list.
(define list-visitor (lambda (L visitor partial-result)
(if (null? L)
partial-result
(list-visitor (cdr L) visitor (visitor (car L) partial-result))
)
)
)
The function list-visitor takes three arguments: a list L, a visitor function, and a partial
result. It recursively visits each element in the list. At each element, list-visitor calls the
visitor function and passes to it the first of L and the partial result. The visitor function returns
a new partial result, which is used as the partial result for the next call to list-visitor. If
L is empty, then the partial result is returned.
The visitor function passed to the list-visitor is commonly called an aggregator because
it aggregates the values in the list to compute the result. For example, the + function would
be considered an aggregator.
Write a bst-preorder-visitor function which implements a pre-order traversal visitor pattern on the example BST implementation. Your implementation should take the same three
parameters as the list-visitor function.
1
CSCI3136
Summer 2021
Assignment 9
Input: The visitor function should take three arguments:
T a BST to be traversed
visitor function to be called on each value in the BST. The function takes two arguments:
a value stored in a BST node and the partial result. The function returns a new
partial result.
partial-result the partial result returned by the last call to visitor function.
Processing: You may assume that the BST is valid and include the dummy node in the
computations. I.e., assume the dummy node is part of the BST.
No error checking is necessary. You may assume that appropriate arguments will be
passed to bst-preorder-visitor
Return: bst-preorder-visitor should return the result of applying the visitor function to
each value in the BST in an preorder fashion.
You should test your code and we will test your code as well.
3. [8 marks] Suppose you wanted to determine whether a Scheme interpreter used lexical or dynamic scoping and shallow or deep binding. Come up with a Scheme expression that evaluates
to one of: (shallow lexical), (deep lexical), (shallow dynamic), or (deep dynamic)
depending on which of the four possible combinations that the interpreter implements.
Provide a brief description of how the expression works.
2
CSCI3136
Summer 2021
Assignment 9
Marking Scheme
1. Marking scheme for Question 1.
3 points
2 points
Approach
Solution
Solution looks correct
and covers all cases
Functionality
1 point
0 points
Solution uses letrec
as required
Solution does not use
letrec
Solution looks somewhat correct and covers some cases
No solution provided
Solution works on test
input
Solution works
some test inputs
on
Solution
work
does
not
2. Marking scheme for Question 2.
3 points
Approach
Solution
Solution looks correct
and covers all cases
Functionality
2 points
1 point
0 points
Solution
performs
correct traversal and
calls visitor in the
right order
Solution performs a
traversal and calls visitor
No traversal
formed
Solution looks mostly
correct and covers
some cases
Solution represents a
good attempt
No solution provided
Solution works on all
test input
Solution works
some test inputs
Solution
work
on
does
per-
not
3. Marking scheme for Question 3.
3 points
2 points
1 point
0 points
Approach
Approach
correctly
uses free variables
and calls a passed
function
Approach uses free
variables and calls a
passed function
Approach uses free
variables or calls a
passed function
Approach fails to
use free variables or
passed functions
Functionality
Solution will differentiate between all 4
cases
Solution will differentiate between 3 cases
Solution will differentiate between 2 cases
Solution will not work
Function of code explained
Function
of
code
poorly explained
Function of code not
explained
Explanation
4. Marking scheme for overall code clarity.
3 points
2 points
1 point
0 points
Understandability
Code is easy to understand
Code is a little hard to
understand
Code is unintelligible
or not submitted
Formatting
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
3
CSCI3136: Assignment 9
Summer 2021
Student Name Login ID
Student Number Student Signature
Mark
Question 1
Question 2
Question 3
Overall code clarity
Total
/5
/7
/8
/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