Chapter 6:

1. Do exercises 6.23, 6.25, and 6.26

Chapter 5:

1. Do exercises 5.2, 5.8, and 5.18

Chapter 4:

1. Do exercises 4.2.a.2 and b,  and 4.12.

 
2. Consider the following card sorting algorithm.  In order to do it, you need a source pile, a target pile, and a finished pile.  Initially, all of the cards are in the source pile, and the target and finished piles are empty.
1. Pick up the first card in the source pile with  your right hand.
2. Repeat the following steps until there are no cards in the source pile.
1.  Move the card in your right hand over to your left
2.  Pick up the top card in the source pile with  your right hand.
3.  If the card in your left hand is bigger than the one in your right hand, switch cards.
4.  Put the card in your left hand face down in the target pile.
3.  Put the card left in your right hand face up in the finished pile.
4. Turn the target pile cards over and put them in the source file.
5. Repeat all of the steps above until all of the cards are in the finished pile.
What is the time-complexity of this sorting algorithm?
 
3. Consider the following procedure for multiplying a by b; how many additions does it do? (Express your answer as a mathematical formula involving a and/or b.)

(define times
  (lambda (a b); b must be a non-negative integer
    (define loop
      (lambda (b acc);returns ab+acc
        (if (= b 0)
            acc
            (loop (- b 1) (+ a acc)))))
  (loop b 0)))
 
4. Consider the following procedure for raising c to the e power.  Suppose it is used with the definition of times given in the previous problem. How many additions does it do? (Again, express your answer as a mathematical formula involving c and/or e.)

(define power
  (lambda (c e)
    (if (= e 0)
        1
        (times (power c (- e 1)) c))))

Chapter 3:

1. Do exercises 3.2, 3.4, 3.5, and 3.15  in the text
2. Write an iterative  procedure that will find the average of the digits in a non-negative integer.  For example,

(digit-average 1123456789) ==> 4.6

Chapter 2:

1.    Do exercises 2.2, 2.8, and 2.21  in the text
2.   Write a procedure that will find the average of the digits in a non-negative integer.  For example,

(digit-average 1123456789) ==> 4.6

Chapter 1:

1. Do exercises 1.4 and 1.16 in the text
2. Write a Scheme procedure that will find the largest of three numbers.
3. The first-graders I used to work with liked to find the ``middle'' number of two numbers.  For example, the middle number of 3 and 9 is 6,  while the middle number of 1 and 10 is 5.5.
1. Write the Scheme expression to find the middle number of 17 and 5,678,200.
2. Write a Scheme expression, called middle, that finds the middle number of any two numbers.
3. What does the following procedure do?  Try to describe this as succinctly as you can.

(define mystery
  (lambda (x y z w)
      (middle (middle x y)
              (middle z w))))