COMP 3007  Assignment #2
Recursion & Firstclass Functions
Due: Friday February 7^{th} @ 11:55pm
Question 1

[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/y^{2}+2y)/3
Use this formula to implement a cuberoot procedure analogous to the squareroot procedure from the lecture notes. Your code should use nested functions and free variables wherever possible. 
[2 marks] Consider the
(newif)
procedure as shown below. Replace the standard if inside cbrtiter with a call to newif instead. Does the new version work? Explain why or why not.
(define (newif predicate consequent alternate)
(cond (predicate consequent)
(else alternate)))
;example usage
(newif (< x 0) ( x) x)
Question 2
Recall the definition of general summation of numbers between two values as described in lecture (copied here for reference):
(define (sum a b term next)
(if (> a b)
0
(+ (term a)
(sum (next a) b term next))))

[2 marks] Write a higherorder procedure called
product
analogous to sum procedure from lecture. The procedure should generate a recursive process.
E.g.(product 1 5 (lambda(x)x)(lambda(x)(+ x 1))) → 120

[5 marks] Rewrite your solution to the previous problem using an iterative process. Call this procedure
(productit)
 [3 marks] Using your solution to either of the previous problems, produce the given PI notations below.

[5 marks] Write a procedure called
(palindrome? s)
that takes a strings
as argument and returns true (#t) ifs
is palindrome. 
[7 marks] A kpalindrome is a string that can be made into a palindrome by ignoring up to k characters. Write a procedure called
(kpalindrome? s k)
that takes a strings
and a nonnegative integerk
as arguments and returns true if s is a kpalindrome. For example,
(kpalindrome? "tahcohcat" 2) → #t
(kpalindrome? "tahcohcat" 1) → #f
You may find the following builtin procedures useful for the above problems:

(stringlength str)
 returns the number of characters in a given string 
(stringref 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].
A function f is defined by the rules:
f(n) = n, if n<3
f(n) = f(n1) + 2f(n2) + 3f(n3), otherwise
 [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.
 [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.
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.

[5 marks] Write a procedure that computes elements of Pascal's triangle given row and column indices. Any invalid indices should return a value of 0.
For example, 
[7 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,
(pascals 0 0) → 1
(pascals 2 0) → 1
(pascals 2 1) → 2
(pascals 4 2) → 6
(printTriangle 5)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
A hyperoperation is a repeated sequence of arithmetic operations where, a hyperoperation of rank n is a repeated sequence of hyperoperations of rank n1.
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: a^{b} = a * (a * (a * ... * a))
(b
times)
Tetration is the 4th rank hyper operation: a
↑↑b = a^{(a(a...a))}
This pattern continues with pentation, hexation, septation, etc...
[6 marks] Write a function called (hyper x)
that takes a hyperoperator x as argument and returns the next higher rank hyperoperator.
For example:
(define mymult (hyper +))
(mymult 3 4) → 12
(define myexp (hyper mymult))
(myexp 2 4) → 16
(define mytetra (hyper myexp))
(mytetra 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.
 For testing you should create the three hyperoperations shown here (multiplication, exponentiation, and tetration), and validate that they work as they should.
 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 1 and up.

For any hyperoperation (H) with rank > 1,
a
H1 = a
.
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 wellformatted and easily readable; a happy TA is a generous TA.
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.
 The example runs provided in the guidelines above may not be sufficient.
 Unless otherwise specified, you may assume inputs supplied are of the correct type.
 Fabricated test outputs will result in 0 marks for a question.
 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.
An example submission including documentation and testing can be found here: primes.scm
Submission
 Any files that are not runnable (in DrRacket using R5RS) will result in a mark of 0 for that question.
 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.
 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.
20200205