Home Comp 3007
COMP 3007 – Assignment #2
• COMP 3007
◦ Outline
◦ Lectures
◦ Assignments
◦ Schedule
Recursion & First-class Functions
Due: Sunday October 11th by 11:55:00pm
Objectives: practice with recursion, iteration, first-class & higher-order functions, lambdas, and closures.
For each problem you should use the provided file and function names, failure to do so will result in zero marks for the affected solutions.
Question 1
In a file called a2q1_cbrt.scm, answer the following questions.
a. [5 marks] Newton’s method for cube roots is based on the fact that if y is an approximation to the cube root of x (i.e., y ≈ ∛x), then a better approximation is given by the value: (x/y2+2y)/3
Use this formula to implement a cube-root procedure analogous to the square-root procedure from the lecture notes. Your code should use nested functions and free variables wherever possible.
b. [3 marks] Modify your solution to the previous part to allow the user of the cube-root procedure to pass in their own function for determining when the estimate is “good enough”. The passed in function should take the guess and input number as arguments and return true (#t) if the guess is a “good-enough” approximation of the cube-root of the input number, and false (#f) otherwise.
E.g. (cube-root 27 good-enough-to-0.1?) → 3.001274406506175
Include in your solution, testing done with at least 3 different good-enough functions (these can be defined or lambdas). You may rename the modified function so as not to conflict with your solution to part a.
c. [2 marks] Consider the (new-if) procedure as shown below. Replace the standard if inside cbrt-iter with a call to new-if instead. Does the new version work? Explain why or why not.
(define (new-if predicate consequent alternate)
(cond (predicate consequent)
(else alternate)))
;example usage
(new-if (< x 0) (- x) x)
Question 2
In a file called a2q2_product.scm, answer the following questions.
a. [2 marks] Recall the procedure sum for computing the general summation of numbers between two values as described in lecture. Write a higher-order procedure called product analogous to the sum procedure from lecture. The procedure should use a recursive process.
E.g. (product 1 5 (lambda(x)x)(lambda(x)(+ x 1))) → 120
b. [5 marks] Rewrite your solution to the previous problem using an iterative process. Call this procedure product-it
c. [3 marks] Using your solution to either of the previous problems, produce the given Pi notations below (click to see each larger).
i. 
ii. 
iii. 
Question 3
A function f is defined by the rules:
f(n) = n, if n<3
f(n) = f(n-1) + 2f(n-2) + 3f(n-3), otherwise
In a file called a2q3_branching.scm, answer the following questions.
a. [4 marks] Write a procedure that computes f by means of a recursive process. Illustrate that your answer is recursive by showing the substitution model for (f 5) in comments below your code.
b. [7 marks] Write a procedure that computes f by means of an iterative process. Illustrate that your answer is iterative by showing the substitution model for (f 5) in comments below your code.
Question 4
[6 marks] Gold-bar™ Chocolate Bars are wrapped in real gold foil, which can be collected and traded in for new bars of chocolate!
In a file called a2q4_chocolate.scm, write a program called bars that takes the following arguments and determines how many bars of Gold-bar™ Chocolate you afford in total:
wallet is the amount of money you have (integer, >=0)
price is the cost per bar of chocolate (integer, >0)
wrappers is how many wrappers you need to trade to get a free bar (integer, >1)
For example:
(bars 10 3 3) → 4
(bars 15 3 3) → 7
Question 5
[16 marks total] In this problem you will first construct an abstraction representing a playing card, and then you’ll use that to implement a simple card game.
Some initial guidelines:
• Your outputs (user prompts, displays, etc) do not need to match the provided examples, but must contain/convey the relevant information.
• You may not use lists, pairs, or variable mutatations (set! or similar) in your implementation. Any solutions that do will receive zero marks for part a of this question. why tho?
• Place all of your answers to this question in a file called a2q5_cards.scm.
The Problems:
a. [6 marks] Create an abstraction that represents a single playing card, with a constructor called randomCard. randomCard should take no arguments and return a function. The returned function should represent a playing card with a random suit and number such that the following interactions would be valid: (define c1 (randomCard)) ;construct a card
b. (define c2 (randomCard)) ;construct a 2nd card
c. (c1 “suit”) => “diamonds” ;select the suit from the card
d. (c1 “num”) => 5 ;select the number from the card
e. (c1 “suit”) => “diamonds” ;note, this is a fixed random value…
f. (c2 “suit”) => “clubs” ;this other card has a different random suit
g. (c2 “num”) => 13 ;and number
h.
The random suit should be a value from the set {“spades”,”clubs”,”hearts”,”diamonds”}, and the number should be in the range [2,14] representing a valid playing card (where 11 = jack, 12 = queen, 13 = king, 14 = ace). 14?
To generate a random number in drracket’s scheme, you have to first borrow the rng from the racket language.
(#%require (only racket/base random))
i. (random min max) ;to generate an integer in the range [min,max)
j.
k. [2 marks] Create a function called displayCard that implements a display into the playing card abstraction. The function should take a single playing card as argument and display its number and suit to the console. Note: card numbers 11, 12, 13, and 14 should be displayed as J, Q, K, and A respectively.
E.g.,
l. (define myCard (randomCard))
m. (displayCard myCard)
n. => A of hearts
o.
p. [8 marks] Create a function called play-war that plays a variant of the cardgame War. The game should proceed in rounds, where each round consists of the following steps:
◦ deal a card for the player
◦ deal a card for the cpu
◦ display both cards
◦ declare a winner (highest card wins)
q. Each round should result in a score of +1 when the player wins, or -1 when they lose. In the event of a tie, a tiebreaker round should be played. The winner of the tie breaker round is the winner of the original round.
The game should repeat, asking the player if they would like to play another round, until they answer no. How? Note: the user should not be prompted to play another round before a tie-breaker round, this should happen automatically when there is a tie.
At the end of the game (when no more rounds are to be played), the player’s final score should be returned.
Some sample playthroughs can be seen here.
Documentation & Testing
Documentation
• Ensure that your name and student number are in comments at the top of all files.
• Document the purpose of each function including its expected inputs (parameters) and output (return).
• Ensure that your code is well-formatted and easily readable; a happy TA is a generous TA.
• Please note, copying and pasting the assignment guidelines does not constitute sufficient documentation, and will receive zero marks.
• You may use any code or text found in lecture or the assignment but you must cite the source correctly.
Testing
• You are required to include testing runs of every function in your submission.
• The specific tests required depend on the question at hand, but should cover all valid inputs and all possible branches of your code.
• Unless otherwise specified, you may assume inputs supplied are of the correct type.
• Fabricated test outputs will result in 0 marks for a question.
• Your test cases are expected to be unique where appropriate
• Please note, copying and pasting the provided example runs does not constitute sufficient testing, and will receive zero marks.
• For best practices: Comment your testing as to what you are testing and why, giving expected output as well as observed output and explanations for any differences.
[10 marks total]
An example submission including documentation and testing can be found here: primes.scm.
A similar example demonstrating unit testing (borrowed from Racket) can be found here: primes.scm.
You are free to use either approach (or find your own).
Submission Guidelines
• Any files that are not runnable (in DrRacket using R5RS) will result in a mark of 0 for that question.
• You must use any and all provided file and function names for your submission. Failure to follow the prescribed naming conventions will result in a grade of zero for the affected questions.
• Do not use set! (or any built-in procedure with !) in your solutions for this assignment.
• Do not use any external libraries unless otherwise stated. Unsolicited use of imports will result in a mark of zero for any solutions in the given file.
• Combine all files into a single .zip file for your submission.
• Submit your assignment using cuLearn before the due date.
• Marks will be deducted for late submissions.
• You are responsible for submitting all files and ENSURING that the submission is completed successfully.
• If you are having issues with submission, contact me before the due date, afterwards late deductions will apply.
• Please see the course outline for all submission guidelines.
Additional Tips
About the read function:
The read function returns exactly the symbols as typed. This means if you enter “hello” you get a string, and if you enter 42 you get an integer. If you type simply x (or anything resembling a scheme variable name) you get a datatype called a symbol. We’ll discuss symbols and the quote special form in chapter 4 of the lecture notes, but for now you can use the following pattern to do comparisons on symbols: (if (eq? userInput ‘y) “yes!” “no!”)
Some other built-in functions you may find useful:
• (modulo value base),
• (read),
• (log num),
• (floor num),
• (ceiling num),
• (expt num1 num2),
• (number->string num),
• (string-append str1 str2).