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) )