CMPUT 325: Assignment 4

	Reinforcement Learning and Artificial Intelligence (RLAI)
	CMPUT 325: Assignment 4

Due: Monday, 16 October, 2006 by 23:59:59

Specs:
Do exercises 2.53, 2.54, 2.55, 2.58a, 2.62, 2.73 and 2.75 from Structure and Interpretation of Computer Programs (second edition).
Please follow the rules given below. If there is a discrepancy between the text and the rules below, follow our instructions.

Submission Instructions:
Write all your answers in a plain text file named a4. From the directory where this file is located, type in the following command:

astep -c c325 -p ex4 a4

When prompted if this is your primary submission, answer Y. You may submit as many times as you like; the last version you submit will be marked. All submissions should be primary submissions, not just the last.

Ensure that you follow the Style and Submission Guidelines exactly. Failure to do so will result in lost marks.

Rules, Guidelines and Suggestions:

The code you write for exercises 2.54, 2.58a, 2.62, 2.73b, 2.73c, and 2.75 will be tested electronically. To ensure we can test your code, please do the following:

Write your answers to all the other exercises inside comments. Comments in Scheme are delimited by the characters #| and |#
For 2.54 you should define the function equal? which takes two parameters as defined in the question
For 2.58a, include the code provided below, and alter the definitions of make-sum, make-product, sum?, addend, augend, product?, multiplier and multiplicand to work for infix notation
For 2.62, define the procedure union-set as described in the question and argue that it runs in O(n)
For 2.73b, use the definition of deriv-2 given below. Perform derivatives for infix notation, not prefix. This way, you can reuse code from 2.58a if you like. You must use the definitions of operator and operands provided below. The definitions of put and get are also given. For this question, you simply need to write the proper calls to put into your submitted file
For 2.73c, add support for exponents. Assume that exponents are written in the form (base ** exponent), and that the exponent is a positive integer. Output the resulting product in exactly the order given in 2.56 , with the first two terms nested the deepest. Ignore the possibility of simplifying products resulting from computing the derivative of an exponent. For example, (deriv-2 '((3 * x) ** 2) 'x) should return ((2 * (3 * x)) * 3). There will be more examples in the provided test cases. In addition to adding another put call into your file, you must also define the constructor make-exponentiation as specified in exercise 2.56. You need not define any other procedures, but may if you find them helpful
For 2.75 provide the definition for the contructor make-from-mag-ang as described in the question
You may write whatever additional functions you need

Use functional programming in this and all assignments from Chapters 1 and 2. To be on the safe side:

use only functions that have been mentioned in the book prior to the exercise being worked on
never use mutating operators, such as (re)assignment of variables. Define is ok

For questions which require procedures to be written, hand in syntactically correct Scheme code (which hopefully is also algorithmically correct)
We will be marking for style on some questions. Code which is cleanly written, and which performs the given task well will receive a higher mark than solutions which are poorer in terms of structure and algorithm. Put closing parenthesis on the same line as the thing they enclose, not on a new line by themselves. No orphan parenthesis!
Be certain you are using the correct edition of the text. Not all exercises are similar between the first and second editions of the text. Ditto for the online version

Code (taken from the text, except operator and operands):
Ensure that all this code is included in the file you submit for marking. Do not create new versions of the code to be altered, alter it in place.



;;exercise 2.58a

(define (deriv exp var)

  (cond ((number? exp) 0)

        ((variable? exp) (if
(same-variable? exp var) 1 0))

        ((sum? exp) (make-sum (deriv
(addend exp) var) (deriv (augend exp) var)))

        ((product? exp) (make-sum 

                        
(make-product (multiplier exp) (deriv (multiplicand exp) var))

                        
(make-product (deriv (multiplier exp) var) (multiplicand exp))))

        (else

         (error "unknown
expression type -- DERIV" exp))))



(define variable? symbol?)



(define (same-variable? v1 v2)

  (and (variable? v1) (variable? v2) (eq? v1 v2)))



(define (=number? exp num)

  (and (number? exp) (= exp num)))



;;;;alter this code

;;;;note that the definition for make-product has been corrected



(define (make-sum a1 a2)

  (cond ((=number? a1 0) a2)

       
((=number? a2 0) a1)

       
((and (number? a1) (number? a2)) (+ a1 a2))

       
(else (list '+ a1 a2))))



(define (make-product a1 a2)

  (cond ((or (=number? a1 0)
(=number? a2 0)) 0)

       
((=number? a1 1) a2)

       
((=number? a2 1) a1)

       
((and (number? a1) (number? a2)) (* a1 a2))

       
(else (list '* a1 a2))))



(define (sum? x)

  (and (pair? x) (eq? (car x)
'+)))

(define (addend s) (cadr s))

(define (augend s) (caddr s))



(define (product? x)

  (and (pair? x) (eq? (car x)
'*)))

(define (multiplier s) (cadr s))

(define (multiplicand s) (caddr s))



;;exercise 2.73



(define (make-table)

  (let ((local-table (list '*table*)))

    (define (lookup key-1 key-2)

      (let ((subtable (assoc key-1 (cdr
local-table))))

        (if subtable

            (let
((record (assoc key-2 (cdr subtable))))

             
(if record

                 
(cdr record)

                 
false))

           
false)))

    (define (insert! key-1 key-2 value)

      (let ((subtable (assoc key-1 (cdr
local-table))))

        (if subtable

            (let
((record (assoc key-2 (cdr subtable))))

             
(if record

                 
(set-cdr! record value)

                 
(set-cdr! subtable

                           
(cons (cons key-2 value)

                                 
(cdr subtable)))))

           
(set-cdr! local-table

                     
(cons (list key-1

                                 
(cons key-2 value))

                           
(cdr local-table)))))

      'ok)    

    (define (dispatch m)

      (cond ((eq? m 'lookup-proc) lookup)

           
((eq? m 'insert-proc!) insert!)

           
(else (error "Unknown operation -- TABLE" m))))

    dispatch))



(define operation-table (make-table))

(define get (operation-table 'lookup-proc))

(define put (operation-table 'insert-proc!))



(define (deriv-2 exp var)

  (cond ((number? exp) 0)

        ((variable? exp) (if
(same-variable? exp var) 1 0))

        (else ((get 'deriv (operator
exp)) (operands exp) var))))



(define operator cadr)

(define (operands x) (list (car x) (caddr x)))



;;;add three calls to put here

;;;add definition of
make-exponentiation here



;;exercise 2.75



(define (apply-generic op arg) (arg op))

Test Cases:
For this assignment, your code will be tested for you upon submission. Use astep whenever you'd like to see if your code is passing the tests we're providing for you.

Mark Breakdown:

Question	Marks
2.53	1
2.54	2
2.55	1
2.58a	3
2.62	3
2.73	8
2.75	3
Total	21
Cumulative Total	99

Back to CMPUT 325 Homepage

Extend this Page How to edit Style Subscribe Notify Suggest Help This open web page hosted at the University of Alberta. Terms of use 1396/0