Problem 1
5 points
If you want to get aboard ship for this voyage of 1311X you've got to
answer the boarding plank guard's question correctly: "Explain the differences
between augmentive and tail recursion"
Captain Kurt The Balding is quie a believer in the do-it-yourself style of running a ship. In fact, rumor has it that he has an orange apron hidden in his collection of stylish pirate regalia. In order to make sure that you, the aspiring Scheme-pirate-to-be, have your ducks in a row, he's going to have you re-write some existing Scheme functions. And no, you may not use the function you're supposed to be re-writing in your solution.
Problem 2
10 points
First off, write a function that replicates the functionality of the
existing scheme function remainder. Write your function using
augmentive recursion and call it remainder-ag. NOTE: You may
not use division in your remainder mimicing functions.
Examples:
> (remainder-ag 3 10) 3 > (remainder-ag -10 3) -1 > (remainder-ag -8 -3) -2 > (remainder-ag 10 3) 1
Problem 3
10 points
Not bad, but this time write a function that replicates the functionality
of remainder using tail recursion. Call your function
remainder-tr.
Problem 4
10 points
So far so good, now write a function called expt-ag which mimics
the functionality of the built in function expt using augmentive
recursion. This function takes exactly two arguments: an integer and a
positive integer, and it returns the first argument raised to second
argument.
Examples:
> (expt-ag 2 3) 8 > (expt-ag -8 7) -2097152 > (expt-ag 3 0) 1
Problem 5
10 points
Write a tail-recursive version of the expt function. Call it
expt-tr.
Problem 6
10 points
Show the substitutional model of evaluation for the function call:
> (expt-ag 3 5)
Problem 7
10 points
Write a function called my-if whose basic functionality mimics
that of the built-in function if. It will take in exactly
three arguments: test-condition, if-true, and if-false. If the
test-condition evaluates to true, then return if-true, otheriwse
return if-false. The ONLY function you may use is the built-in
function cond.
Sample usage:
(define (foo num)
(my-if (> num 0)
#t
#f))
;;; my-if definitiongoes here
If the function foo were called in DrScheme, the results would be: > (foo 1) #t > (foo 0) #f
Problem 8
15 points
After a few months at sea, Captain Kurt sometimes gets a little goofy
(perhaps his pirate hat is on too tight). One day during the voyage, when
there hadn't been even the slightest breeze since the night before, Kurt
climbed up to the crow's nest and yelled "Today is not opposite day! Now
everybody stop rowing!" Now, as luck would have it, this happened on
payday, so Kurt decided to reverse the digits of everybody's paycheck. Help
Kurt out by writing a function called reverse-digits which will take
in an integer and return it with the digits reversed. HINT: use remainder and quotient
Examples:
> (reverse-digits 123) 321 > (reverse-digits -42) -24
Problem 9
10 points
Kurt likes to sing, and his favorite songs to sing are Christmas songs.
One day he was bellowing the carol "The Twelve Days of Christmas" when a
thought struck him: "I wonder how many presents I would get on any given day
of Christmas?" Help Kurt out by writing a recursive function to calculate
how many presents Kurt will get on any given day of Christmas. Remember
that you get 1 present the first day, 2 presents + 1 present the second day,
3 presents + 2 presents + 1 present on the third day, etc... Call your
function presents-on-day.
Examples:
> (presents-on-day 1) 1 > (presents-on-day 3) 6
Problem 10
10 points
Now Kurt's wondering how many presents he'll have total. Help him out by
writing a function called presents-through-day that will calculate
how many presents he will have accumulated through a given day. For example,
on the first day he'll have one present. On the second day he'll have his
one present from the first day plus three presents from the second day, etc...
Examples:
> (presents-through-day 1) 1 > (presents-through-day 3) 10>
Problem 11
10 points
One afternoon during the voyage, Kurt was hanging out in his quarters
reading Elements, which is a really old math book written in 300 BC
by a (now deceased) guy named Euclid. In this book Euclid describes an
algorithm to find the Greatest Common Denominator of any two numbers. The
Greatest Common Denominator (abbreviated GCD) of two numbers is the largest
number that evenly divides (ie, no remainder) those two numbers. For
example, the GCD of 18 and 12 is 6. The algorithm given by Euclid is:
Kurt thinks (and his crew of able-bodied TA's agree) that this sounds like a
perfect opportunity for you to practice your recursive skills. Write a
function called my-gcd which will take in two integers and return
their GCD.
Examples:
> (my-gcd 3 4) 1 > (my-gcd 100 10) 10 > (my-gcd 12 18) 6
Problem 12
15 points
While reading all of his math books, Kurt discovered that prime numbers have
some pretty cool properties. He wants you to write him a function that will
take in a number and return #t if the number is prime and #f it if is not.
A number is prime if its only factors are one and the number itself. One
method to decide if a number (let's call that number n) is prime is to
divide all numbers less than the square root of n into n and see if the
remainder is ever zero. Confused? How about an example:
Is 11 a prime number?
The square root of 11 is about 3.31.
(remainder 11 1) ==> 0, so 1 is a factor.
(remainder 11 2) ==> 1, so 2 is not a factor.
(remainder 11 3) ==> 2, so 3 is not a factor.
1, 2, and 3 are the only whole numbers less than 3.31, and since 1 is the
only factor, then 11 is prime.
Call your function is-prime?
Problem 13
10 points
Every morning Kurt has some of the crew line up on the deck for
inspection. The number of crew members who line up varies from day to day
(sometimes people are sick, sometimes they sleep in, etc...). Kurt wonders
how many possible permutations there are if he has n crew total and
r of them show up on any given day. Luckily for him, this relates
directly to a function you may have seen in math class. It's sometimes
referred to as the nPr function. It takes in exactly two positive
integers, n and r, and give an answer according to the following formula:
n! -------- (n - r)!Write a function called nPr which will take in exactly two arguments and will return the answer according to the above formula. HINT:Think about abstraction. What function have you seen in lecture that you can reuse here? Will you use augmentive or tail recursion? What if we have a large number of pirates?
> (nPr 10 5) 30240 > (nPr 4 4) 24
Problem 14
10 points
Sometimes Kurt has to make committees to keep things on the ship running.
One night Kurt was lying in bed, trying to go to sleep, when a thought
popped into his head: "If I have n pirates and need a committee of r people,
how many possible ways can I create that committee?" Luckily for Kurt, this
relation between the number of unordered groups you can form of size r from a
larger group of size n is given by the nCr function. This function
is defined to be:
n!
----------
r!(n - r)!
Help Kurt get some sleep by writing a function called nCr which will
take in exactly two arguments: n and r, and will return the correct value,
based on the above formula.> (nCr 5 2) 10 > (nCr 30 4) 27405
Problem 15
10 points
Kurt's first mate, Angry Dan, is deathly afraid of the Bermuda Triangle.
He's so afraid of it that sometimes he gets scared of other famous triangles
as well. One triangle that Dan has this irrational fear of is Pascal's
Triangle. It looks something like this:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
etc. etc. etc. etc. etc. etc.
The relationship between elements in the triangle and thier position is that
each element is the sum of the two numbers above. Take the third row, for
example: 1 2 1. The ones on the edge come from the ones in the second row
being added to nothing, and the two comes from the two ones being added
together. Try drawing out a few on paper if you're still not clear.> (pascal-element-at 1 1) 1 > (pascal-element-at 3 2) 2 > (pascal-element-at 6 4) 10
Problem 16
20 points
Kurt likes to collect little bits of trivia, and one of the more trivial
bits of math that he knows is a little trick for determining if a large
number is divisible by 37. A number is divisible by 37 if the sum of the
sets of three digits is divisible by 37. If the sum is less than 1000, then
you divide and check to see if the remainder is zero. If it's
greater than 1000, then you sum the digits and repeat.
Examples:
153,217 ==> 153 + 217 = 370, and 370 is divisible by 37, so 153,217 is
divisible by 37.
57,387 ==> 57 + 387 = 444, and 444 is divisible by 37, so 57,387 is
divisible by 37.
4,616,897 ==> 4 + 616 + 897 = 1517.
Now, since 1517 is greater than 1000,
we can check to see if it's divisible by 37 just like any other number:
1 + 517 = 518, and 518 is divisible by 37, so 4,616,897 is divisible by 37.
Write a function called divis-by-37 which takes in exactly one
parameter, an integer, and returns #t if the number is divisible by 37 and
#f if it is not. NOTE:You may not use remainder to directly
determine divisibility. You must use the algorithm as described above.
If there's anything Kurt likes its a bunch of lists. You'll have plenty of practice with them next time, but for now let's have a few simple list problems to get you warmed up.
Problem 17
20 points
One of Kurt's favorite things is playing with lists. He wants to make sure
that you understand how they work so that you can do neat things with them
later. So explain what the following function calls return and why they
return it
a) (cons 'X 'X) b) (cons 'W ()) c) (cons (cons 'a '(a))) d) (cdr (cons 'a '(b))) e) (cdr (cons 'a 'b))
Problem 18
10 points
Write a function called my-nth that is passed a
number n and a list, and returns the (n+1)th element of the list. You
may assume
the value of n will be valid(in other words, n will always be less
than the number of elements in th list) For example:
> (my-nth 1 '(a b c)) b