CSCI3136 Assignment 9
Instructor: Alex Brodsky
Due: 9:00am, Monday, July 22, 2020
Note: While this assignment is released on Friday, July 10, the material for it will not be completely covered until Lecture 19 on Monday, July 13. Consequently, the assignment will not be due until Monday, July 20. But, if you wish to start early, Lecture 19 has been posted on Brightspace.
1. [5 marks] In Assignment 8 you were asked to write a Scheme program (Fib.scm) that computes the n¡¯th Fibonacci number, F (n), efficiently. Your solution probably used a separate helper function to perform the actual loop (see solution to Assignment 8.)
Rewrite the fib function using a letrec expression so that the helper function is defined inside the fib 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. Modify the file Fib..scm as described above.
Input: One non-negative integer read from the console, e.g., 7
Processing: Input will be an integer in the range 0 to 1000
Output: Output a single integer denoting F(n). E.g., for the above input, the output is:
13
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-inorder-visitor function which implements an in-order traversal visitor pat- tern on the example BST implementation. Your implementation should take the same three parameters as the list-visitor function.
1
CSCI3136 Summer 2020 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-inorder-visitor
Return: bst-inorder-visitor should return the result of applying the visitor function to each value in the BST in an inorder 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 eval- uates to one of: (lexical shallow), (lexical deep), (dynamic shallow), or (dynamic deep) depending on which of the four possible combinations that the interpreter implements.
Provide a brief description of how the expression works.
2
CSCI3136 Summer 2020 Assignment 9
Marking Scheme
1. Marking scheme for Question 1.
3 points
2 points
1 point
Solution uses letrec as required
0 points
Approach
Solution does not use
letrec
Solution
Solution looks correct and covers all cases
Solution looks some- what correct and cov- ers some cases
No solution provided
Functionality
Solution works on test input
Solution works on some test inputs
Solution does not work
2. Marking scheme for Question 2.
3 points
2 points
1 point
0 points
Approach
Solution performs correct traversal and calls visitor in the right order
Solution performs a traversal and calls vis- itor
No traversal per- formed
Solution
Solution looks correct and covers all cases
Solution looks mostly correct and covers some cases
Solution represents a good attempt
No solution provided
Functionality
Solution works on all test input
Solution works on some test inputs
Solution does not work
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 differen- tiate between all 4 cases
Solution will differen- tiate between 3 cases
Solution will differen- tiate between 2 cases
Solution will not work
Explanation
Function of code ex- plained
Function of code poorly explained
Function of code not explained
4. Marking scheme for overall code clarity.
3 points
2 points
1 point
0 points
Understandability
Code is easy to under- stand
Code is a little hard to understand
Code is unintelligible or not submitted
Formatting
Code is well format- ted and indented
Code is inconsistently formatted
Code is poorly for- matted or not submit- ted
Commenting
Comments are used where appropriate
No comments present or no code submitted
3
CSCI3136: Assignment 9
Summer 2020
Student Name
Login ID
Student Number
Student Signature
Mark
Question 1 Question 2 Question 3
Overall code clarity
/5 /7 /8 /5
Total
/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 Facultys 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 Universitys regulations regarding academic integrity.