search

AkronCodeClub / sicp-study-group

A study group to work through Structure and Interpretation of Computer Programs (SICP)
6 stars 3 forks source link

Problem Set 2: Procedures, procedures, procedures! #8

Open jdantonio opened 9 years ago

jdantonio commented 9 years ago

Part 2.1: If, cond, procedure definitions

Lec.3.2.1: Substitution model

Assume that we have evaluated the following definitions:

(define max (lambda ( a b) (if (> a b) a b)))
(define max-sum (lambda (a b) (max (+ a b) (- a b))))

Each of the following questions corresponds to a step of the substitution model of evaluation of the expression (max-sum 2 -3), but with one subexpression left blank. (Note that we are following the rule of first substituting for the formal parameters in an expression, then simplifying all subexpressions at the same time, then substituting). Indicate the subexpression that should go in each blank.

  1. (max (+ 2 -3) __________ )
  2. (max __________ 5)
  3. (if __________ -1 5)
  4. (if __________ -1 5)

  5. Lec.3.2.2: More substitution model

Assume that we have evaluated the following definition:

(define fizz (lambda (a b) (* (/ a b) (/ b a))))

Now, we would like to evaluate the expression (fizz (+ 1 -1) 1). Indicate the first three steps of the substitution model. (Again assume that we follow the rule of substituting for the formal parameters, then simplifying any appropriate subexpressions, then substituting.) Type "error" if there is an error on this or a previous step. Assume for the purposes of this question that we are using applicative order evaluation.

  1. Step 1: __
  2. Step 2: __
  3. Step 3: __

    Lec.3.2.3: I'm tired of the substitution model

Assume that we have evaluated the following definition:

(define fuzz (lambda (a b) (if (= b 0) a (/ 1 b))))

Now, we would like to evaluate the expression (fuzz -1 0). Indicate the first three steps of the substitution model. Type "error" if there is an error on this or a previous step.

  1. Step 1: __
  2. Step 2: __
  3. Step 3: __

    Lec.3.3.1: Deconstructing a recursive procedure

Consider the following definition:

(define foo
  (lambda (x y)
    (if (= x y)
        0
        (+ x (foo (+ x 1) y)))))
  1. What is the test expression? (write the actual expression, not its value)
  2. What is the base case?
  3. What is the recursive case?

    Lec.3.4.1: How to recognize an iterative procedure

Which of the following properties is a requirement for a procedure to be iterative? (Check all that apply)

  1. It uses a helper procedure.
  2. There are no pending operations.
  3. It makes a call to another procedure with an additional argument.

    Lec.3.4.2: Alternative ifact

Here is an alternative implementation of ifact, the iterative factorial procedure.

(define ifacta (lambda (n)
  (ifacta-helper 1 n)))

(define ifacta-helper (lambda (partial-answer n)
  (if (= n 0)
    partial-answer
    (ifacta-helper (* n partial-answer) (- n 1)))))

Part 1: Parts of an iterative procedure

  1. What is the final value returned by ifacta-helper? (Write the expression, not its value)
  2. What is the iterative case of ifacta-helper?

    Part 2: Substitution model

If you do a substitution-model expansion of (ifacta 3), every few steps you'll get an expression of the form (ifacta-helper a b). Indicate those expressions, in order, below, where the subexpressions are reduced to simplest terms.

  1. Step 1: __
  2. Step 2: __
  3. Step 3: __
  4. Step 4: __

    PS.2.1.1: Using cond instead of if

Rewrite the following code fragment to use cond:

(if (< x -2)
    (* x -2)
    (if (< x 2)
        (* x x)
        (* x 2)))

PS.2.1.2: If procedure

Which of the following is another description of the operation computed on a and b in the expression:

((if (> b 0) + -) a b)
  1. b - |a|
  2. |a + b|
  3. a + |b|
  4. a - |b|

    PS.2.1.3: How does recursion recurse?

Consider the following definition:

(define foo
  (lambda (x y)
    (if (= x y)
        0
        (+ x (foo (+ x 1) y)))))

Assume that x and y are give integer values. Under which of the following conditions on the arguments will an invocation of the procedure certainly run forever (select all that apply)?

  1. x < y
  2. x > y
  3. x = y
  4. x < 0
  5. y < 0

    PS.2.1.4: Writing recursive procedures

Suppose we want to implement multiplication, but only have the operations of addition, subtraction, and simple predicates available to us. Write a recursive scheme procedure that takes two arguments, a and b, both of which you may assume are positive integers, and returns the product of a and b, using only these operations.

(define slow-mul (lambda (a b) your_code_here))

PS.2.1.5: Peano Addition

To do basic arithmetic on non-negative integers, all you really need to be able to do is increment and decrement, and test to see if a number is 0. Using the scheme procedures inc (which adds 1 to its argument), dec (which subtracts 1 from its argument), and zero?, as well our old friend if, implement plus as an iterative procedure. Don't use a helper procedure.

(define plus (lambda (a b) your_code_here))

Part 2.2: Recursive and Iterative Procedures, and Orders of Growth

Lec.4.1.1: Orders of growth

What is simplest expression for the order of growth of running time of procedure bar?

(define bar (lambda (n)
  (cond ((= n 0) 5)
    ((= n 1) 7)
    (else (* n (bar (- n 2)))))))
  1. Theta(1)
  2. Theta(2n)
  3. Theta(n)
  4. Theta(n/2)

    Lec.4.2.1: Orders of growth in time

What is simplest expression for the order of growth of running time of procedure baz?

(define baz (lambda (n)
  (cond ((= n 0) 5)
    ((= n 1) 7)
    (else (* (baz (- n 1)) (baz (- n 2)))))))
  1. Theta(1)
  2. Theta(n)
  3. Theta(n^2)
  4. Theta(2^n)

    Lec.4.4.1: Simple log

    Part 1: Simple log code

Write a recursive procedure (simple-log x) that takes a positive power of two as an argument and returns the log of value. Your procedure be written so that is gives rise to a recursive proces. So, for example,

(simple-log 1) => 0
(simple-log 2) => 1
(simple-log 4) => 2
(simple-log 8) => 3

Your procedure should only use basic arithmetic operations, like +, *, -, /.

(define simple-log (lambda (n) your_code_here))

Part 2: Order of growth in time

What is the order of growth of running time of procedure simple-log? (This is assuming that you correctly wrote it to have a recursive behavior!)

  1. Theta(1)
  2. Theta(log(n))
  3. Theta(n)

    Part 3: Order of growth in space

What is the order of growth of space of procedure simple-log? (This is assuming that you correctly wrote it to have a recursive behavior!)

  1. Theta(1)
  2. Theta(log(n))
  3. Theta(n)

    Lec.4.4.2: Ranking Orders of Growth

Rank the list of orders of growth below, in increasing order. Your answers should be integers with 1 being the slowest growth. If two or more items have the same order of growth, list them with the same ranking.

  1. Theta(1)
  2. Theta(2^n)
  3. Theta(n^2)
  4. Theta(2n)
  5. Theta(log n)
  6. Theta(n)

    PS.2.2.1: Iterative odd?

Write an iterative procedure, (odd? x), that returns #t if its non-negative integer argument x is odd and #f otherwise. Do not use quotient, remainder, /, etc. Do use if or cond.

(define (odd? x) your_code_here)

PS.2.2.2: Writing recursive procedures

You have seen how to implement exponentiation using only the operations of multiplication, addition, subtraction, and simple predicates. You should be able to do the same thing for multiplication, using only the operations of addition, subtraction and simple predicates. Write a recursive procedure that takes two arguments, a and b, both of which you may assume are positive integers, and returns the product of a and b, using only these operations.

(define slow-mul-recurse
  (lambda (a b) your_code_here))

PS.2.2.3: Writing iterative procedures

You have seen how to implement exponentiation using only the operations of multiplication, addition, subtraction, and simple predicates. You should be able to do the same thing for multiplication, using only the operations of addition, subtraction and simple predicates. Write an iterative procedure that takes two arguments, a and b, both of which you may assume are positive integers, and returns the product of a and b, using only these operations.

Note that you can write multiple define statements in the space provided. 

(define slow-mul-iter
  (lambda (a b) your_code_here))

PS.2.2.4: Writing fast procedures

Using the ideas shown in Lecture for cutting the size of a problem in half, write a procedure that takes two arguments, a and b, both of which you may assume are positive integers, and returns the product of a and b, using only the operations of addition, subtraction, multiplication by 2 (called double), and division by 2 (called halve). These latter two operations are in fact things that can be computed very fast. Your procedure should work in logarithmic time. You may assume that the procedure even? exists.

(define fast-mul (lambda (a b) your_code_here))

### PS.2.2.5: Constant-time Sum

Write a procedure (quick-sum n) that computes the sum of the integers from 1 to n in constant time. ```

```scheme
(define quick-sum (lambda (n) your_code_here))

PS.2.2.6: Fast expi

Write a purely iterative version of the fast-exp procedure from Lecture. Note that you can type multiple defines into the code box below.

(define fast-expi (lambda (a b) your_code_here))

Optional Problems

PS.2.3.1: If as a special form

Consider the following short Scheme program fragment:

(if (= a 0)
    (really-big-hairy-slow-procedure 3)
    (really-big-hairy-slow-procedure 4))

If the form if were not special, then really-big-hairy-slow-procedure would have to be applied twice, once to 3 and once to 4. There are other reasons as well for if to be a special form, but in this particular case, the objection (inefficiently applying a big procedure twice, only to throw one result away) can be resolved by rewriting the code above. Write it below (without using and, or or cond) and using only one if. (While the straightforward answer does not involve an explicit use of a lambda, if you chose to use an explicit lambda, please use b as the parameter for the lambda.)

PS.2.3.2: Iterative odd? using and, or, not

An iterative version of odd? for non-negative integer arguments can be written using and, or, and not. To do so, you have to take advantage of the fact that and and or are special forms that evaluate their arguments in order from left to right, exiting as soon as the value is determined. Write (boolean-odd? x) without using if or cond, but using and, or, not (boolean) instead. You may use + and -, but do not use quotient, remainder, /, etc.

(define (boolean-odd? x) your_code_here)

PS.2.3.3: Summing, by halves

One way to sum the integers from a up to b is to divide the interval in half, recursively sum the two halves, and then add the two sums together. If the interval has an odd number of integers, divide as nearly in half as possible. You can use the floor function to return the largest integer that is smaller than some real value.

Part 1: Code

Write a procedure implementing this idea.

(define sum-by-halves
  (lambda (a b) your_code_here))

Part 2: Order of Growth

If n is the number of integers in the range from a up to b, what is the order of growth of time of the sum-by-halves procedure?

  1. Theta(1)
  2. Theta(log(n))
  3. Theta(n)
  4. Theta(2^n)

    PS.2.3.4: Mystery

Write a recursive version of the following procedure:

(define mystery 
  (lambda (a b)
    (mystery-meat 0 a b)))

(define mystery-meat 
  (lambda (c a b)
    (if (> a b)
    c
    (mystery-meat (+ c a) (+ a 1) b))))
(define clarity (lambda (a b) your_code_here))
jdantonio commented 9 years ago

Required Exercises