2021/2/15 COMP 3007
HOME COMP 3007
COMP 3007 – Assignment #2
COMP 3007
Outline
Lectures
Assignments
Schedule
Recursion & First-class Functions Due: Sunday February 14th @ 11:55pm
Question 1
In a file called a2q1_newton.scm, solve the following problems:
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, 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. [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
( if(<0)())
people.scs.carleton.ca/~arunka/courses/comp3007/assignments/a2/
1/6
2021/2/15 COMP 3007
(new-if (< x 0) (- x) x)
Question 2
In a file called a2q2_products.scm solve the problems below.
Recall the definition of general summation of numbers between two values as described in lecture.
a. [2 marks] Write a higher-order procedure called product analogous to the sum procedure from lecture. The procedure should generate a recursive process.
E.g. (product 1 5 (lambda(x)x)(lambda(x)(+ x 1))) ¡ú 120
b. [4 marks] Rewrite your solution to the previous problem to solve it 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.
Question 3
In a file called a2q3_palindromes.scm solve the following problems:
a. [5 marks] Write a procedure called (palindrome? s) that takes a string s as argument and returns true (#t) if s is palindrome.
(palindrome? "tacocat") ¡ú #t (palindrome? "taco cat") ¡ú #f
b. [7 marks] A k-palindrome is a string that can be made into a palindrome by ignoring up to k characters. Write a procedure called (k-palindrome? s k) that takes a string s and a non-negative integer k as arguments and returns true if s is a k- palindrome. You should not use lists or pairs in your solution. See additional tips for more.
For example,
(k-palindrome? "tahcohcat" 2) ¡ú #t (k-palindrome? "tahcohcat" 1) ¡ú #f
Question 4
In a file called a2q4_branching.scm, solve the problems below.
A function f is defined by the rules:
f(n) = n, if n<3
f(n) = 3f(n-1) + 2f(n-2) + f(n-3), otherwise
a [4 marks] Write a procedure that computes f by means of a recursive process
people.scs.carleton.ca/~arunka/courses/comp3007/assignments/a2/ 2/6
2021/2/15 COMP 3007
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 5
In a file called a2q5_pascal.scm, solve the problems below.
The following pattern of numbers is called Pascal's triangle. The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.
a. [5 marks] Write a procedure that, when given a row and column index, computes the relevant element of Pascal's triangle by means of a recursive process. Any invalid indices should return a value of 0.
For example,
(pascals 0 0) ¡ú 1 (pascals 2 0) ¡ú 1 (pascals 2 1) ¡ú 2 (pascals 4 2) ¡ú 6
b. [6 marks] Using your solution to the previous part, write a procedure (printTriangle n) that prints n rows of Pascal's triangle to the screen. For example,
(printTriangle 5) ¡ú
1
11
121 1331 14641
For testing, you may have the function return the entire triangle as a single string, or manually verify printed outputs.
Question 6
In a file called 2 6 h i solve the following problem people.scs.carleton.ca/~arunka/courses/comp3007/assignments/a2/ 3/6
2021/2/15 COMP 3007
In a file called , solve the following problem.
a2q6_hyperoperations.scm
A hyperoperation is a repeated sequence of arithmetic operations where, a hyperoperation of rank n is a repeated sequence of hyperoperations of rank n-1.
For example, Addition is a hyperoperation of rank 1. Multiplication is a hyper operation of rank 2.
Multiplication can be expressed as a sequence of additions: a * b = a + (a + (a + ... + a)) (b times)
Exponentiation is a hyper operation of rank 3: ab = a * (a * (a * ... * a)) (b times)
...a Tetration is the 4th rank hyper operation: a¡ü¡üb = a(a(a ))
This pattern continues with pentation, hexation, septation, etc...
[7 marks] Write a function called (hyper x) that takes a hyperoperator x as argument and returns the next higher rank hyperoperator.
For example:
(define my-mult (hyper +)) (my-mult 3 4) ¡ú 12
(define my-exp (hyper my-mult)) (my-exp 2 4) ¡ú 16
(define my-tetra (hyper my-exp)) (my-tetra 2 4) ¡ú 65536
Some notes:
This approach will have many special cases for zeroes and negative numbers, so you may assume exclusively positive integers in your solution.
Technically, addition is a hyperoperation made up of repeated increments, but this again leads to some special cases and inconsistencies, so you may assume addition as the lowest rank hyperoperation for your solution. That is, your function need only generate hyperoperations of rank 2 and up.
For any hyperoperation (H) with rank > 1, aH1 = a.
For testing, pentation and higher operations will be very computationally expensive. You should verify that the three hyperoperations shown here (multiplication, exponentiation, and tetration) work as they should. Note, your code is expected to be written such that higher operations would be possible if computational resources permitted.
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
people.scs.carleton.ca/~arunka/courses/comp3007/assignments/a2/ 4/6
2021/2/15 COMP 3007
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.
[5 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
Your solutions for this assignment are expected to use correct functional style as demonstrated in class. This means no use of looping constructs or mutable variables.
Don’t go using set! (or any built-in procedure with !) in your solutions for this assignment, please stick to the referential transparency you’re used to.
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.
Any code files that are not runnable (in DrRacket using R5RS) may result in deductions up to 100% 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.
Combine all files into a single .zip file for your submission. There is no mandatory naming convention for .zip files, but names should be clear and relevant.
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
people.scs.carleton.ca/~arunka/courses/comp3007/assignments/a2/
5/6
2021/2/15 p g COMP 3007
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
You should re-use your own functions wherever possible.
Some other built-in functions you might find useful (in addition to those covered in the lecture notes):
(string-length str) – returns the number of characters in a given string (string-ref str i) – returns the character at a specified index in a given string (substring str start [end]) – returns a substring of a given string between two indices [the ending index is optional].
(string-append str1 str2) – returns a string that is the concatenation of the two input strings
people.scs.carleton.ca/~arunka/courses/comp3007/assignments/a2/
6/6