Assignment 3. Fruitful Functions and Iteration


Fruitful Functions

Exercise 1

Write a compare function that takes two values, x and y, and returns 1 if x < y, 0 if x == y, and -1 if x > y.

Exercise 2

Use incremental development to write a function called hypotenuse that returns the length of the hypotenuse of a right triangle given the lengths of the other two legs as arguments. Record each stage of the development process as you go.

Exercise 3

Draw a stack diagram for the following program. What does the program print?


In [1]:
function b(z)
    prod = a(z, z)
    println(z, " ", prod)
    prod
end

function a(x, y)
    x = x + 1
    x * y
end

function c(x, y, z)
    total = x + y + z
    square = b(total)^2
    square
end

x = 1
y = x + 1
println(c(x, y+3, x+y))


9 90
8100

Exercise 4

A palindrome is a word that is spelled the same backward and forward, like “noon” and “redivider”. Recursively, a word is a palindrome if the first and last letters are the same and the middle is a palindrome.

The following are functions that take a string argument and return the first, last, and middle letters:


In [1]:
function first(word)
    word[1]
end

function last(word)
    word[end]
end

function middle(word)
    word[nextind(word, 1) : prevind(word, sizeof(word))]
end


Out[1]:
middle (generic function with 1 method)

We’ll see how they work in lecture 10

  1. Test theses functions out. What happens if you call middle with a string with two letters? One letter? What about the empty string, which is written "" and contains no letters?

  2. Write a function called is_palindrome that takes a string argument and returns true if it is a palindrome and false otherwise. Remember that you can use the built-in function length to check the length of a string.

Exercise 5

The Ackermann function, $A(m, n)$, is defined: $$ A(m, n) = \begin{cases} n+1& \textrm{if } m = 0 \\ A(m−1, 1)& \textrm{if } m > 0 \textrm{ and } n = 0 \\ A(m−1, A(m, n−1))& \textrm{if } m > 0 \textrm{ and } n > 0. \end{cases} $$ See http://en.wikipedia.org/wiki/Ackermann_function. Write a function named ack that evaluates the Ackermann function. Use your function to evaluate ack(3, 4), which should be 125. What happens for larger values of m and n?

Exercise 6

A number, $a$, is a power of $b$ if it is divisible by $b$ and $\frac{a}{b}$ is a power of $b$. Write a function called is_power that takes parameters a and b and returns true if a is a power of b. Note: you will have to think about the base case.

Exercise 7

The greatest common divisor (GCD) of $a$ and $b$ is the largest number that divides both of them with no remainder.

One way to find the GCD of two numbers is based on the observation that if $r$ is the remainder when $a$ is divided by $b$, then gcd(a, b) = gcd(b, r). As a base case, we can use gcd(a, 0) = a.

Write a function called gcd that takes parameters a and b and returns their greatest common divisor.

Iteration

Exercise 1

Copy the loop from the square root calculation of the lecture and encapsulate it in a function called mysqrt that takes a as a parameter, chooses a reasonable value of x, and returns an estimate of the square root of a. To test it, write a function named test_square_root that prints a table like this:

a   mysqrt(a)     sqrt(a)       diff
-   ---------     -------       ----
1.0 1.0           1.0           0.0
2.0 1.41421356237 1.41421356237 2.22044604925e-16
3.0 1.73205080757 1.73205080757 0.0
4.0 2.0           2.0           0.0
5.0 2.2360679775  2.2360679775  0.0
6.0 2.44948974278 2.44948974278 0.0
7.0 2.64575131106 2.64575131106 0.0
8.0 2.82842712475 2.82842712475 4.4408920985e-16
9.0 3.0           3.0           0.0

The first column is a number, a; the second column is the square root of a computed with mysqrt; the third column is the square root computed by sqrt; the fourth column is the absolute value of the difference between the two estimates.

Exercise 2

The built-in function parse takes a string and transforms it into an expression. This expression can be evaluated using the Julia interpreter with the function eval. For example:


In [3]:
expr = parse("1+2*3")
eval(expr)


Out[3]:
7

In [4]:
expr = parse("sqrt(π)")
eval(expr)


Out[4]:
1.7724538509055159

Write a function called eval_loop that iteratively prompts the user, takes the resulting input and evaluates it using eval, and prints the result. It should continue until the user enters "done", and then return the value of the last expression it evaluated.

Exercise 3

The mathematician Srinivasa Ramanujan found an infinite series that can be used to generate a numerical approximation of $\frac{1}{\pi}$: $$ \frac{1}{\pi}=\frac{2\sqrt2}{9801}\sum_{k=0}^\infty\frac{(4k)!(1103+26390k)}{(k!)^4 396^{4k}} $$ Write a function called estimate_pi that uses this formula to compute and return an estimate of π. It should use a while loop to compute terms of the summation until the last term is smaller than 1e-15 (which is Julia notation for 10−15). You can check the result by comparing it to pi.