Your name: 	

	1



	1


CS 3 (Clancy)	Final exam
December 10, 1991

THIS COPY HAS ANSWERS DISPLAYED.
Read and fill in this page now.
Do NOT turn the page until you are told to do so.
Your name:		
	(please printÑlast name, first name)
Name of the person sitting to your left:		
Name of the person sitting to your right:		
Problem 0			Total:  	/60
Problem 1					Problem 5		
Problem 2					Problem 6				
Problem 3					Problem 7		
Problem 4					Problem 8						
This is an open-book test. You have approximately three hours to 
complete it; time estimates accompanying each problem suggest a pace to 
finish in three hours. You may consult any books, notes, or other 
inanimate objects available to you. To avoid confusion, read the problems 
carefully. If you find it hard to understand a problem, ask us to explain it. 
If you have a question during the test, please come to the front or the side of 
the room to ask it.
This exam comprises 30% of the points on which your final grade 
will be based. Partial credit will be given for wrong answers. 
You are not to use setf within functions. Any other Lisp construct 
described in Touretzky chapters 1-8, any of the case studies, or any of the 
CSÊ3 handouts is ok, though. In particular, either recursion or applicative 
operators is allowed in a solution unless otherwise specified.
Anywhere you are directed to write a function, your solution may 
include auxiliary functions. You need not rewrite a function that appears 
in Touretzky, in any of the case studies, or in any of the CS 3 handouts; 
merely cite the page in Touretzky, the case study and page number or 
appendix, or the handout in which the function appears.
Your exam should contain 9 problems (numbered 0 through 8) on 14 
pages. Please write your answers in the spaces provided in the test; in 
particular, we will not grade anything on the back of an exam page unless 
we are clearly told on the front of the page to look there. 
RelaxÑthis exam is not worth having heart failure about.

Problem 0 (3 points)
You earn the points for this problem if you have done the following:
¥	you have put your name on each page of this exam, and provided the 
information requested on the first page;
¥	you have completed and handed in both the survey at the beginning of 
the semester and the end-of-semester survey (copies of the latter are 
available from Mike Clancy or the t.a.s);
¥	you have completed an interview.
Check with Mike Clancy or the t.a.s to make sure your survey submissions 
and your interview have been recorded.
Problem 1 (6 points, 20 minutes)
Write a function gpa that, given as input a list representing a 
studentÕs transcript, returns the corresponding grade-point average. Each 
element of the transcript list contains three elements: a letter grade, the 
number of grade points for that grade, and how many of that grade the 
student earned. Some examples:
expression	value returned
(gpa '((A- 3.7 3) (B+ 3.3 3)))	3.5
(gpa '((A 4.0 1) (B 3.0 1) (C 2.0 1) (D 1.0 1)))	2.5
Write your function in the space below. Your solution may include 
auxiliary functions.
(defun gpa (transcript)
	(/
		(reduce #'+
			(mapcar 
				#'(lambda (triple)
					(* (second triple) (third triple)) )
				transcript ) )
		(reduce #'+
			(mapcar #'third transcript) ) )

Point allocation is 1 for the division, 3 for 
computing the total grade points, and 2 for 
computing the number of courses.

This probably works out to -1 per bug.

An example: the solution
	(/
		(reduce #'+ (mapcar #'second transcript) )
		(length transcript) )
should earn 3 out of 6.  It loses 2 in the grade 
point computation and 1 in the course count.
)

Problem 2 (10 points, 30 minutes)
Consider a data base represented by an unordered list of records for 
recently-hired employees. Each record is represented by a list of two 
elements, the first containing an employeeÕs name, the second containing 
the date in 1991 when the employee was hired. 
Write two versions of a function name-of-first-hire that takes a 
data base as input, and returns the name of the employee with the earliest 
hiring date. Assume that the data base is nonempty, that dates are 
represented as in the ÒDifference Between DatesÓ case study, and that the 
employees in the data base were all hired on different days. Examples:
expression	name returned
(name-of-first-hire
  '(((clancy mike) (may 20))
    ((grillmeyer oliver) (january 1))
    ((wang randy) (june 15))
    ((krishnamurthy arvind) (december 12)) ) )	(grillmeyer oliver)
(name-of-first-hire
  '(((krishnamurthy arvind) (june 1))
    ((grillmeyer oliver) (december 12))
    ((wang randy) (june 15)) ) )	(krishnamurthy arvind)
(name-of-first-hire
  '(((clancy mike) (december 20))
    ((krishnamurthy arvind) (december 12))
    ((grillmeyer oliver) (december 16))
    ((wang randy) (december 9)) ) )	(wang randy)
Part a
In the space below, write a version of name-of-first-hire that uses 
applicative operators but not recursion. Your solution may include 
auxiliary functions.
(defun name-of-first-hire (data-base)

	(defun earlier? (d1 d2)
		(> (days-between d1 d2) 0) )

	(defun first-hired-emp (e1 e2)
		(if (earlier? (second e1) (second e2)) e1 e2) )

	(first (reduce #'first-hired-emp data-base)) )

This is worth 5 points: 4 for finding the correct 
employee record and 1 for returning the correspond-
ing name. Of the 4 points, 2 should be for correct 
comparison of employee hiring dates (access + 
comparison) and 2 for accumulating the earliest 
hiring date.

This probably works out to -1 per bug.
)

Part b
In the space below, write a version of name-of-first-hire that uses 
recursion but not applicative operators. Your solution may include 
auxiliary functions.
(defun name-of-first-hire (data-base)

	(first
		(helper (rest data-base) (first data-base)) ) )

(defun helper (data-base so-far)
	(cond
		((null data-base) so-far)
		((earlier?
			(second (first data-base))
			(second so-far))
		 (helper (rest data-base) (first data-base)) )
		( T (helper (rest data-base) so-far)) ) )

This is worth 5 points: 4 for finding the correct 
employee record and 1 for returning the correspond-
ing name. Of the 4 points, 2 should be for correct 
comparison of employee hiring dates (access + 
comparison) and 2 for accumulating the earliest 
hiring date.

This probably works out to -1 per bug.
)

Problem 3 (5 points, 20 minutes)
Recall the functions matching-x-count from homework assignment 
10 and correct-p-matches from the Mastermind case study:
(defun matching-x-count (L1 L2)
	(cond
		((null L1) 0)
		((and (equal (first L1) 'x) (equal (first L2) 'x))
			(+ 1 (matching-x-count (rest L1) (rest L2))) )
		( T (matching-x-count (rest L1) (rest L2))) ) )
(defun correct-p-matches (L1 L2)
	(cond
		((null L1) 0)
		((equal (first L1) (first L2))
			(+ 1 (correct-p-matches (rest L1) (rest L2))) )
		( T (correct-p-matches (rest L1) (rest L2))) ) )
Both functions assume that their inputs are the same length.
Part a
These two functions can be generalized by a function compare-count 
that takes two lists and a 2-input predicate as inputs, returning the number 
of corresponding elements in the list that satisfy the predicate. Complete 
the framework for compare-count given below.
(defun compare-count (L1 L2 compare-pred)
	(cond
		((null L1) 0)
		( 	
			(+ 1 (compare-count (rest L1) (rest L2) compare-pred)) )
		( T (compare-count (rest L1) (rest L2) compare-pred)) ) )

(funcall compare-pred L1 L2)
or
(funcall compare-pred (first L1) (first L2))

This is worth 1 point.  If part b is correct but 
disagrees with part a, deduct part a's points.
Part b
Complete the definitions of matching-x-count and correct-p-
matches below by providing the appropriate inputs to compare-count. You 
may provide auxiliary functions if you wish.
(defun matching-x-count (L1 L2)
	(compare-count L1 L2
			 ) )
(defun correct-p-matches (L1 L2)
	(compare-count L1 L2
			 ) )

if the function operates on L1 and L2
matching-x-count:
#'(lambda (L1 L2)
	(and (equal (first L1) 'x) (equal (first L2) 'x)) )
correct-p-matches:
#'(lambda (L1 L2)
	(equal (first L1) (first L2)) )

if the function operates on (first L1) and (first L2)
matching-x-count:
#'(lambda (x y)
	(and (equal x 'x) (equal y 'x)) )
correct-p-matches:
#'equal

These are worth 2 points each.

Problem 4 (4 points, 20 minutes)
Recall the function remove-adj-duplsÑyou encountered a buggy 
version in lab assignment 9Ñthat is supposed to return the result of 
removing any duplicate adjacent elements from its input. For example,
(remove-adj-dupls '(A (B C) (B C) E F F F R))
is supposed to return (AÊ(BÊC)ÊEÊFÊR). 
Part a
Given below is another buggy version of remove-adj-dupls, that 
returns (AÊEÊFÊR) when called as just described.
(defun remove-adj-dupls (L)
	(cond
		((or (null L) (null (rest L))) L)
		((equal (first L) (second L))
			(remove-adj-dupls (rest (rest L))) )
		( T (cons (first L) (remove-adj-dupls (rest L)))) ) )
Describe, as completely as possible, the set of inputs for which the version 
above performs as desired. 

Those lists in which every sequence of adjacent 
duplicates is odd in length.

2 points for getting it right, 1 point for 
mentioning "odd" somewhere without a correct 
description.
Part b
Fix the bug, making as few changes to the existing code as possible. 
HereÕs the code again; please be very clear about what youÕre deleting, and 
what youÕre adding and where youÕre adding it.
(defun remove-adj-dupls (L)
	(cond
		((or (null L) (null (rest L))) L)
		((equal (first L) (second L))
			(remove-adj-dupls (rest (rest L))) )
		( T (cons (first L) (remove-adj-dupls (rest L)))) ) )

(defun remove-adj-dupls (L)
	(cond
		((or (null L) (null (rest L))) L)
		((equal (first L) (second L))
			(remove-adj-dupls (rest L)) )
		( T (cons (first L) 
				(remove-adj-dupls (rest L)) )) ) )

I.e. delete one of the calls to "rest".
This is worth 2 points.  It's probably all or none.

Problem 5 (6 points, 15 minutes)
Write a function insertion-mistake? that could be used in a 
program to check spelling of a document. It will take two nonempty lists of 
single-letter atoms as inputs, the first representing a word from a 
document, the second representing a word from a dictionary, and will 
return true exactly when the document word is the result of inserting a 
single letter into the dictionary word. Examples:
expression	value returned
(insertion-mistake? '(H E A T) '(H A T))	T
(insertion-mistake? '(T H A T) '(H A T)) 	T
(insertion-mistake? '(H A T E) '(H A T))	T
(insertion-mistake? '(A B B C) '(A B C))	T
(insertion-mistake? '(A T) '(H A T))	nil
(insertion-mistake? '(H A T) '(H A T))	nil
(insertion-mistake? '(H A T E D) '(H A T))	nil
(insertion-mistake? '(C H E A T) '(H A T))	nil
Write your function in the space below. Your solution may include 
auxiliary functions.
(defun insertion-mistake? (doc-word dict-word)

	(cond
		((null doc-word) nil)
		((null dict-word) (null (rest doc-word)))
		((equal (first doc-word) (first dict-word))
			(insertion-mistake? 
				(rest doc-word) (rest dict-word)))
		( T (equal (rest doc-word) dict-word)) ) )

The above cases should be worth 1, 2, 1, and 2.

Failing when the inserted letter is at the end 
should lose 2 points.
)

Problem 6 (8 points, 25 minutes)
We mentioned in class that it is sometimes useful, in a rule-based 
environment, to collect a history of the sequence of rule applications. Given 
below is a modified monitor that collects such a history:
(defun monitor (rules data-base history)
	(let ((applicable-rules (applicable rules data-base)))
		(if (not (null applicable-rules))
			(monitor
				rules
				(apply-rule (choose applicable-rules history)) data-base)
				(cons (choose applicable-rules history)) history) ) ) ) )
The applicable function returns a list of rules (in no particular order). The 
history is also a list of rules, in which rules are ordered from most-recently-
applied to least-recently-applied.
Part a
Describe a method of choosing from a list of applicable rules that will 
not work with the monitor code above, and briefly explain why it wonÕt 
work.

This is worth 2 points, 1 for the answer and 1 for 
the explanation.
Two possible answers:
	Random choice wonÕt work because the first call 
to choose might return a different rule from the 
second call.
	Choice by asking the user might not work because 
the user might give different answers when asked to 
choose a rule in the two calls to choose.

Part b
Suppose that the following strategy is decided on to choose among a 
list of applicable rules: if there are applicable rules that have been applied 
already, then choose the rule that was applied most recently; otherwise 
choose the first rule in the list. Here are some examples; assume that r1, 
r2, etc. stand for rules.
applicable list	history	rule chosen
(r1 r3 r5 r22)	(r7 r3 r7 r22 r14)	r3
(r1 r3 r5 r22)	(r5 r3 r7 r5 r22 r14)	r5
(r1 r3 r5 r22)	(r14 r15 r2 r22)	r22
(r1 r3 r5 r22)	nil	r1
(r1 r3 r5 r22)	(r14 r15 r2 r2 r10)	r1
In the space below, write the choose function to implement this 
strategy. Your solution may include auxiliary functions.
(defun choose (rule-list history)

	(cond
		((find-if
			#'(lambda (hist-rule)
				(find-if 
					#'(lambda (r) (equal r hist-rule))
					rule-list ) )
			history ))
		( T (first rule-list)) ) )

HereÕs a recursive version:
	(cond
		((null history) (first rule-list))
		((find-if
			#'(lambda (r) (equal (first history) r))
			rule-list))
		( T (choose rule-list (rest history))) ) )

This is worth 6 points. 
For the recursive version, points should be awarded 
1 for the base case, 3 for the find-if, and 2 for 
the other case.
For the applicative version, the nested find-if 
should be worth 5 somehow but I'm not quite sure 
how to award it.

Using (first (intersection rule-list history) won't 
work because there might be duplicates in the 
history.  This should lose 3 points.

If the find-ifs are applied to the lists in the 
wrong order, deduct 2 points.

If (member hist-rule rule-list) is used instead of 
the inner find-if, deduct 2 points.
)

Problem 7 (5 points, 15 minutes)
Recall the pattern matching code from lab assignment 12. (It appears 
on the last page of this exam.) How many calls to match-with-*-list are 
made as a result of evaluating the expression 
(matchÊ'(AÊ*ÊC)Ê'(AÊBÊC))? For full credit, make it clear how you got 
your answer.

Five calls are made.

(match '(A * C) '(A B C)) makes a call
	(match-with-*-list '(A * C) '(A B C) nil)

which, in the (symbol? (first pattern)) clause, 
makes the call
	(match-with-*-list '(* C) '(B C) nil)

which, in the (arb-sequence? (first pattern)) 
clause, first makes the call
	(match-with-*-list '(C) '(B C) '(1 nil))

which checks the (symbol? (first pattern)) 
clause, but returns without calling match-with-
*-list

and then makes the call
	(extend-match '(* C) '(C) '(1 (B)))
which makes the call
	(match-with-*-list '(C) '(C) '(1 (B)))

which, in the (symbol? (first pattern)) clause, 
makes the call
	(match-with-*-list nil nil '(1 (B)))

which returns T in the (null pattern) clause.

One way to grade this is to allot 1 point per call. 
Another is to allot 2 points for dealing with the 
attempt to match the * with nil, 2 points for 
dealing with the call to extend-match, and 1 point 
for the rest.

Problem 8 (13 points, 35 minutes)
Suppose that a new pattern element is to be handled by the pattern 
matching code:
(?Êatom)
matches 0 or 1 occurrence of the given atom in the object.
Examples:
pattern	object	result
(A B (? C))	(A B C)	match
(A B (? C))	(A B)	match
(A B (? C))	(A B C C)	no match
(A B (? C))	(A B D)	no match
(A B (? C))	(A B C D)	no match
((? A) B C)	(B C)	match
((? A) B C)	(A B C)	match
((? A) B C)	(A A B C)	no match
((? A) B C)	(A C)	no match
((? A) * B C)	(B C)	match
((? A) * B C)	(A B C)	match
((? A) * B C)	(A A B C)	match
((? A) * B C)	(A Q X B C)	match
((? A) * B C)	(Q X B C)	match
((? A) B * C)	(B X C)	match
((? A) B * C)	(A B Q X C)	match
((? A) B * C)	(A A B C)	no match
This problem continues on subsequent pages.

Part a
Write a function optional? that, given a pattern element, returns 
true exactly when the pattern element has the form (?Êatom). Assume that 
the cond clause ((optional?Ê(firstÊpattern))ÊÉ) will be inserted in 
match-with-*-list as the next-to-last clause, i.e. immediately before the 
(TÊ'INVALID-PATTERN). 
Write your function in the space below.
(defun optional? (pattern-elem)
	(and
		(listp pattern-elem)
		(= 2 (length pattern-elem))
		(equal (first pattern-elem) '?)
		(atom (second pattern-elem)) ) )

This is worth 2 points.
Deduct 1 for each missing condition, except it's ok 
if they omit checking for a list.
)
Part b
In the space below, write the rest of the cond clause that handles the 
optional pattern element.
((optional? (first pattern))

	(or
		(match-with-*-list (rest pattern) object *-list)
		(and
			((equal (second (first pattern)) (first object))
			(match-with-*-list
				(rest pattern) (rest object) *-list ) ) ) )

This is worth 6 points: 2 for each recursive call, 
1 for the or, and 1 for the comparison.  This 
probably works out to -1 per bug.
)

Part c
Besides the code you wrote for parts a and b, at least one other change 
must be made to match-with-*-list in order to handle the new pattern 
element correctly. Describe what other changes must be made to the 
match-with-*-list code to handle the new pattern element. Your 
description should include detail sufficient to allow a fellow CS 3 student to 
easily implement the changes.

The (null object) clause must be changed to make a 
check for (optional? (first pattern)) as well as 
for (arb-sequence? (first pattern)); in particular, 
the clause should be rewritten as
	((null object)
		(or
			(and 
				(arb-sequence? (first pattern))
				(match-with-*-list 
					(rest pattern) 
					object
					(add-*-entry *-list nil) ) )
			(and 
				(optional? (first pattern))
				(match-with-*-list 
					(rest pattern) 
					object
					*-list ) ) ) )

Award 1 point for modifying the (null object) 
clause, 1 point for the or, 1 point for the second 
and, and 1 point each for the parts of the and.

Deduct 1 point total for each extraneous 
modification that screws up the function, up to a 
total of 2.

Pattern matching code from lab assignment 12

(defun match (pattern object)
  (match-with-*-list pattern object nil) )

(defun match-with-*-list (pattern object *-list)
  (cond
   ((null pattern) (null object))
   ((prev-ref? (first pattern))
    (match-with-*-list
     (append (matched-value (first pattern) *-list) (rest pattern))
     object *-list ) )
   ((null object)
    (and (arb-sequence? (first pattern))
         (match-with-*-list (rest pattern) object 
                            (add-*-entry *-list nil) ) ) )
   ((arb-sequence? (first pattern))
    (or
     (match-with-*-list (rest pattern) object (add-*-entry *-list nil))
     (extend-match pattern (rest object)
       (add-*-entry *-list (first object)) ) ) )
   ((symbol? (first pattern))
    (and (equal (first pattern) (first object))
         (match-with-*-list (rest pattern) (rest object) *-list) ) )
   ( T 'INVALID-PATTERN ) ) )

(defun extend-match (pattern object *-list)
  (cond
   ((match-with-*-list (rest pattern) object *-list))
   ((null object) nil)
   ( T (extend-match pattern (rest object)
                     (extend-*-entry *-list (first object)) )) ) )

(defun arb-sequence? (pattern-elem)
  (equal pattern-elem '*) )

(defun symbol? (pattern-elem)
  (and (atom pattern-elem)
       (not (arb-sequence? pattern-elem))
       (not (prev-ref? pattern-elem)) ) )

(defun prev-ref? (pattern-elem)
  (numberp pattern-elem) )