\newcommand{\exercise}[1]{\par\vspace{0.1 in}{\bf Exercise #1}\par}
\newcommand{\problem}[1]{\par\vspace{0.1 in}{\bf Problem #1}\par}
\newcommand{\bv}{\begin{verbatim}}
\documentstyle{article}
\addtolength{\topmargin}{-0.5 in}
\addtolength{\textheight}{1.0 in}
\addtolength{\oddsidemargin}{-0.5 in}
\addtolength{\evensidemargin}{-0.5 in}
\addtolength{\textwidth}{1.0 in}
\setlength{\parindent}{0 in}
\begin{document}
\hfill\begin{tabular}{l}
Marc Horowitz \\
6.001 \\
Problem Set 2 \\
February 24, 1989 \\
\end{tabular}
\par\vspace{0.5 in}
{\large \bf Exercises}
\exercise{2.1}
\bv
(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

(define (integrate f a b n)
  (let ((h (/ (- b a) n)))
    (define (coefficient k)
      (cond ((= k 0) 1)
            ((= k n) 1)
            ((odd? k) 4)
            (else 2)))
    (define (y k)
      (f (+ a (* k h))))
    (define (term k)
      (* (coefficient k) (y k)))
    (define (next k)
      (1+ k))
    (* (/ h 3) (sum term 0 next n))))
\end{verbatim}
\exercise{2.2}
\bv
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (iter a 0))
\end{verbatim}
\exercise{2.3}
a) six times
\par
b) \( \begin{array}[t]{rcl}
        O(a) & = & \log_{3}a \\
        S(a) & = & \log_{3}a
   \end{array} \)
\exercise{2.4}
\bv
(define (repeated f n)
  (lambda (x)
    (if (= n 1)
        (f x)
        (f ((repeated f (-1+ n)) x)))))
\end{verbatim}
\vspace{0.5 in}
{\large \bf Problems}
\problem{2.1}
\bv
(define (cont-frac-r n d k)
  (define (do-cont-frac-r n d x k)
    (if (> x k)
        0
        (/ (n x)
           (+ (d x) (do-cont-frac-r n d (1+ x) k)))))
  (do-cont-frac-r n d 1 k))

(define (cont-frac-i n d k)
  (define (cont-frac-iter k result)
    (if (= k 0)
        result
        (cont-frac-iter (-1+ k) (/ (n k)
                                   (+ (d k) result)))))
  (cont-frac-iter k 0))
\end{verbatim}
\problem{2.2}
In order to make $\pi$ accurate to 2 decimal places, \verb+k+ must be 291.
\problem{2.3}
\bv
(define (estimate-e k)
  (define (en x) 1)
  (define (ed x)
    (if (= 2 (remainder x 3))
        (* 2 (/ (1+ x) 3))
        1))
  (+ 2 (cont-frac-i en ed k)))
\end{verbatim}
\par\vspace{0.2 in}
In order to make $e$ accurate to 4 decimal places, \verb+k+ must be 7.
\problem{2.5}
\bv
(define (sq x) (* x x))

(define (tan-cf x k)
  (define (tn n)
    (if (= n 1)
        x
        (- (sq x))))
  (define (td n)
    (- (* 2 n) 1))
  (cont-frac-i tn td k))
\end{verbatim}
\bv
(define pi (* 4 (atan 1 1)))
;Value: PI

(tan 0.1)
;Value: .1003346720855

(tan (/ pi 4))
;Value: 1.

(tan (- (/ pi 2) 0.1))
;Value: 9.966644423259

(tan (- (/ (* 10 pi) 2) 0.05))
;Value: -5.004170837554e-2

(tan-cf 0.1 5)
;Value: .1003346720855

(tan-cf (/ pi 4) 5)
;Value: .9999999865264

(tan-cf (- (/ pi 2) 0.1) 5)
;Value: 9.96606532781

(tan-cf (- (/ (* 10 pi) 2) 0.05) 30)
;Value: -5.004170837779e-2
\end{verbatim}
\problem{2.6}
\bv
(define (nested-acc op r term k)
  (define (nested-acc-iter k result)
    (if (= k 0)
        result
        (nested-acc-iter (-1+ k) ((op k) (term k) result))))
  (nested-acc-iter k r))
\end{verbatim}
\problem{2.7}
\bv
(define (the-ops n)
  (cond ((= n 1) /)
        ((= n 2) +)
        ((= n 3) *)
        ((= n 4) -)))

(define (the-terms n)
  n)

(define r 5)
\end{verbatim}
\bv
(nested-acc the-ops r the-terms 4)
;Value: -1
\end{verbatim}
\problem{2.8}
\bv
(define (g x k)
  (define (g-ops n)
    (lambda (a b) (sqrt (- a b))))
  (define (g-terms n) x)
  (nested-acc g-ops 0 g-terms k))
\end{verbatim}
\par\vspace{0.2 in}
\bv
(g 2 10)
;Value: .9991142250902
\end{verbatim}
\par\vspace{0.2 in}
{\bf Proof:}
\[ g(x)=\sqrt{x-\sqrt{x-\sqrt{x-\cdots}}} \]
\[ [g(x)]^{2}=x-\sqrt{x-\sqrt{x-\cdots}} \]
\[ [g(x)]^{2}=x-g(x) \]
\[ [g(x)]^{2}+g(x)-x=0 \]
\[ g(x)=\frac{-1+\sqrt{1+4x}}{2} \]
\vspace{0.1 in}
\[ g(2)=\frac{-1+\sqrt{9}}{2}=-1 \]
\problem{2.9}
\bv
(define (cont-frac-nest n d k)
  (define (cont-frac-ops x)
    (if (odd? x)
        /
        +))
  (define (cont-frac-terms x)
    (if (odd? x)
        (n x)
        (d x)))
  (nested-acc cont-frac-ops 0 cont-frac-terms k))
\end{verbatim}
\bv
(cont-frac-nest (lambda (i) 1)
                (lambda (i) 1)
                24)
;Value: .618025751073

(cont-frac-i (lambda (i) 1)
             (lambda (i) 1)
             12)
;Value: .618025751073
\end{verbatim}
\par\vspace{0.3 in}
{\bf Finally:}
\vspace{0.2 in}\par
I spent no time in the 6.001 lab because I used Athena for this problem
set.  I did spend about 4 hours writing code on Athena.  The actual write-up
took about 1 hour.
\end{document}
