Concrete Abstractions: Chapter 3

Let’s call the number of people in the circle n and number the positions from 1 to n. We’ll assume that the killing of every third person starts with killing the person in position number 3. […]
As we saw above, if the person we care about is in position 3, that person is the one killed and hence definitely not a survivor:

Suppose we aren’t interested in the person in position number 3 but rather in some other person—let’s say J. Doe. The person in position number 3 got killed, so now we only have n – 1 people left. Of that smaller group of n – 1, there will still be two survivors, and we still want to know if J. Doe is one of them.

Exercise 3.9 How about the people who were in positions 1 and 2; what position numbers are they in after the renumbering?

Solution: In the example there were 8 persons at the start. After killing #3, the new #1 is #4, the new #2 is #5*, etc. #2 is #(n-1) and #1 is #(n-2).

*: clearly a reference to the Prisoner ;)

Exercise 3.10 Write a procedure for doing the renumbering. It should take two arguments: the old position number and the old number of people (n). (It can assume that the old position number won’t ever be 3, because that person is killed and hence doesn’t get renumbered.) It should return the new position number.

Solution:

Exercise 3.11 Finish writing the survives? procedure, and carefully test it with a number of cases that are small enough for you to check by hand but that still cover an interesting range of situations.

Solution:

I made a table for testing if the program works correctly. Each line represents a new round, i.e. somebody got killed. The killed person is labeled with X.

Exercise 3.15 Consider the following two procedures:

a. Use the substitution model to evaluate each of (f 1), (f 2), and (f 3).
b. Can you predict (f 4)? (f 5)? In general, which arguments cause f to return 0 and which cause it to return 1? (You need only consider nonnegative integers.)
c. Is the process generated by f iterative or recursive? Explain.

Solution: a. I started to define each function mathematically. $f(0) = 0, f(n) = g(n-1)$ and $g(0) = 1, g(n) = f(n-1)$. Now we can see what’s happening. $f(1) = g(0) = 1$ $f(2) = g(1) = f(0) = 0$ $f(3) = g(2) = f(1) = g(0) = 1$
b. You see that odd numbers lead to $g(0) = 1$ and even numbers lead to $f(0) = 0$.
c. I would say that f’s process iterative because you could stop at any time and just continue later with the saved parameters.

Exercise 3.16 Consider the following two procedures:

a. Use the substitution model to illustrate the evaluation of (f 2), (f 3), and (f 4).
b. Is the process generated by f iterative or recursive? Explain. c. Predict the values of (f 5) and (f 6).

Solution: a. Same trick at last time. $f(0) = 0, f(n) = 1 + g(n-1)$ and $g(0) = 1, g(n) = 1 + f(n - 1)$
Therefore: $f(2) = 1 + g(1) = 1 + (1 + f(0)) = 1 + 1 + 0 = 2$ $f(3) = 1 + g(2) = 1 + (1 + f(1)) = 1 + (1 + (1 + g(0)))$ $1 + (1 + (1 + 1) = 3$ $f(4) = 1 + g(3) = 1 + (1 + f(2)) = 1 + (1 + (1 + g(1)))$ $= 1 + (1 + (1 + (1 + f(0)))) = 3$

b. The process is recursive because you can’t just stop and continue later. This happens because of the (+ 1 f) which have to be saved on the stack.
c. The values of (f 5) and (f 6) are both 6.

Exercise 3.18 We’ve already seen how to raise a number to an integer power, provided that the exponent isn’t negative. We could extend this to allow negative exponents as well by using the following definition: $b^n = \begin{cases} 1 & \text{ if } x=0 \\ b^{n-1}*b & \text{ if } n>0 \\ b^{n+1}/b & \text{ if } n<0 \end{cases}$
a. Using this idea, write a procedure power such that (power b n) raises b to the n power for any integer n.
b. Use the substitution model to show how (power 2 -3) would be evaluated. (You can leave out steps that just determine which branch of a cond or if should be taken.) Does your procedure generate a recursive process or an iterative one?

Solution a.

b.

It’s an recursive one because you can’t determine the final solution without knowing the beginning parameters.

Exercise 3.19 Prove that, for all nonnegative integers n and numbers a, the following procedure computes the value $2^n *a$:

Solution Let’s define the function again mathematically. $f(0, a) = a, f(n, a) = f(n-1, 2a)$. The base case is correct: $f(0, a) = 2^0*a = a$.
We assume that $f(n+1, a) = 2^{n+1}*a = 2^n * 2a$ which can be written as $2^n * 2a = 2^n * b$.
With our assumption it should follow that $f(n+1, a) = f(n, b).$
If we look at the definition, we see that $f(n, a) = f(n-1, 2a)$ which implies $f(n+1, a) = f(n, 2a) = f(n, b).$

This site uses Akismet to reduce spam. Learn how your comment data is processed.

1. Olivier

Good to find someone who started reading the book and doing the exercises before me to compare my solutions… For ex. 3.16 (a), is your mathematical equivalent for g correct? I thought it would be: g(n) = f(n – 1) + 1 for n > 0 .
So f(5) = 5, f(6) = 6, … f(n) = n

• tst

Hey, yeah you are right. Fixed it. Thanks!

2. Burton

“*: clearly a reference of the Prisoner ;)”

Up the irons

• tst

Great song and great TV series!