CSC151.02 2010S Functional Problem Solving : Exams

Exam 3: Sophisticated Scheming

Assigned: Friday 30 April 2010

Due: Beginning of class, Friday 7 May 2010


Exam format

This is a take-home examination. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date.

There are ten problems on this exam. Correct or mostly-correct answers to nine or ten problems will earn you an A. Correct or mostly-correct answers to seven or eight problems will earn you a B. Correct or mostly-correct answers to five or six problems will earn you a C. Correct or mostly-correct answers to three or four problems will earn you a D. Correct or mostly-correct answers to fewer than three problems will earn you an F.

Read the entire exam before you begin.

We expect that someone who has mastered the material and works at a moderate rate should have little trouble completing the exam in a reasonable amount of time. In particular, this exam is likely to take you about two to three hours, depending on how well you've learned the topics and how fast you work. You should not work more than four hours on this exam. Stop at four hours, show your work on at least four problems, and write “There is more to life than CS” and you will earn at least a C+ on this exam.

I would also appreciate it if you would write down the amount of time each problem takes. Each person who does so will earn two points of extra credit. Since I worry about the amount of time my exams take, I will give two points of extra credit to the first two people who honestly report that they have completed the exam in three hours or less or have spent at least three hours on the exam. In the latter case, they should also report on what work they've completed in the three hours. After receiving such notices, I may change the exam.

Academic honesty

This examination is open book, open notes, open mind, open computer, open Web. However, it is closed person. That means you should not talk to other people about the exam. Other than as restricted by that limitation, you should feel free to use all reasonable resources available to you.

As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately. If you use code that you wrote for a previous lab or homework, cite that lab or homework and the other members of your group. If you use code that you found on the course Web site, be sure to cite that code. You need not cite the code provided in the body of the examination.

Although you may use the Web for this exam, you may not post your answers to this examination on the Web. And, in case it's not clear, you may not ask others (in person, via email, via IM, by posting a please help message, or in any other way) to put answers on the Web.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say “This is among the hardest exams I have ever taken. If you don't start it early, you will have no chance of finishing the exam.” You may also summarize these policies. You may not tell other students which problems you've finished. You may not tell other students how long you've spent on the exam.

You must include both of the following statements on the cover sheet of the examination.

  1. I have neither received nor given inappropriate assistance on this examination.
  2. I am not aware of any other students who have given or received inappropriate assistance on this examination.

Please sign and date each statement. Note that the statements must be true; if you are unable to sign either statement, please talk to me at your earliest convenience. You need not reveal the particulars of the dishonesty, simply that it happened. Note also that inappropriate assistance is assistance from (or to) anyone other than Professor Rebelsky (that's me) or Professor Weinman.

Presenting Your Work

You must present your exam to me in two forms: both physically and electronically. That is, you must write all of your answers using the computer, print them out, number the pages, put your name on the top of every page, and hand me the printed copy. You must also email me a copy of your exam. You should create the emailed version by copying the various parts of your exam and pasting them into an email message. In both cases, you should put your answers in the same order as the problems. Failure to name and number the printed pages will lead to a penalty of two points. Failure to turn in both versions may lead to a much worse penalty.

In many problems, I ask you to write code. Unless I specify otherwise in a problem, you should write working code and include examples that show that you've tested the code. Do not include images; I should be able to regenerate those.

Unless I state otherwise, you should document any procedures you write. Your documentation should use the six-P documentation style.

Just as you should be careful and precise when you write code and documentation, so should you be careful and precise when you write prose. Please check your spelling and grammar. Since I should be equally careful, the whole class will receive one point of extra credit for each error in spelling or grammar you identify on this exam. I will limit that form of extra credit to five points.

I will give partial credit for partially correct answers. I am best able to give such partial credit if you include a clear set of work that shows how you derived your answer. You ensure the best possible grade for yourself by clearly indicating what part of your answer is work and what part is your final answer.

Getting Help

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem you have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445).

I will also reserve time at the start of each class before the exam is due to discuss any general questions you have on the exam.


Part A: Search

Problem 1: Extending assoc for Repeated Keys

Topics: Sequential search, assoc, List recursion

As you may have noted, one potential deficiency of assoc is that when multiple entries contain the same key, assoc returns only the first entry with a particular key.

Write, but do not document, a procedure, (assoc-all key lst), that makes a list of all the values in lst whose car is key.

You need not check the preconditions for this procedure.

Note that assoc-all should return the empty list if no entry contains the desired key.

For example,

(define people
  (list (list "Adams" "Amy"   "Architecture")
        (list "Jones" "Jack"  "Geography")
        (list "Jones" "Jane"  "Geology")
        (list "Smith" "Sarah" "Science")
        (list "Jones" "Jenna" "Genetics")))
> (assoc-all "Jones" people)
(("Jones" "Jack" "Geography") ("Jones" "Jane" "Geology") ("Jones" "Jenna" "Genetics"))
> (assoc-all "Smith" people)
(("Smith" "Sarah" "Science"))
> (assoc-all "Davis" people)

Problem 2: Documenting assoc-all

Topics: Documentation, Preconditions

Write the six-P documentation for assoc-all.

Problem 3: Finding the First Element

Topics: Binary search, vectors, divide-and-conquer, numeric recursion

As you've observed, when a key is repeated, binary search picks one value with that key, but not necessarily the first value with that key. Write, but do not document, a variant, binary-search-first, that uses the ideas of binary search to find the first element in the vector that contains the given key.

You should strive to make your procedure as efficient as possible.

While one strategy for implementing binary-search-first is to find some value with the given key (which binary search already does) and then to step left in the vector until you find the first value with that key, stepping through elements one-by-one is inefficient. Write your version so that it continues to “divide and conquer” in its attempt to find the first element with that key.

Part B: Computing Averages

Topics: Lists, pairs, trees, tree recursion

Finding the average of a list of numbers can be a fairly straightforward process. For example, if we have the sum procedure from the list recursion reading, we could use something like the following.

(define list-sum
  (lambda (numbers)
    (if (null? numbers)
        (+ (car numbers) (list-sum (cdr numbers))))))

(define list-length
  (lambda (lst)
    (if (null? lst)
        (+ 1 (list-length (cdr lst))))))

(define average-v1
  (lambda (numbers)
    (/ (list-sum numbers) (list-length numbers))))

However, this implicitly makes two passes over the list, once to do the sum and once to calculate the length. If we have very long lists, we might wish to compact this into a single pass by keeping track of both a sum of the elements in the list (so-far) as well as the count of the number of elements in the list (so-far). Essentially, performing the operations of both code and length at the same time. For example:

(define average-v2
  (lambda (numbers)
    (let kernel ((sum-so-far (car numbers))
                 (count-so-far 1)
                 (remaining (cdr numbers)))
      (if (null? remaining)
          (/ sum-so-far count-so-far)
          (kernel (+ sum-so-far (car remaining))
                  (+ count-so-far 1)
                  (cdr remaining))))))

Alternately, we might try something like the following.

; Given a list of numbers, simultaneously compute the sum and
; length of the list.
(define numbers-info
  (lambda (numbers)
    (if (null? numbers)
        (list 0 0) ; 0 sum, 0 length
        (let ((results (numbers-info (cdr numbers))))
          (list (+ (car numbers) (car results))
                (+ 1 (cadr results)))))))

(define average-v3
  (lambda (numbers)
    (let ((info (numbers-info numbers)))
      (/ (car info) (cadr info)))))

Problem 4: Tracing

Show the steps used in computing the average of the list (2 5 7) using average-v2 and average-v3. That is, show the key steps the Scheme interpreter goes through in figuring out this average. For example, if we were showing the steps for average-v1, we might write:

(average-v1 (2 5 6))
=> (/ (sum (2 5 6)) (length (2 5 6)))
=> (/ (+ 2 (sum 5 6)) (length (2 5 6)))
=> (/ (+ 2 (+ 5 (sum 6))) (length (2 5 6)))
=> (/ (+ 2 (+ 5 (+ 6 (sum ())))) (length (2 5 6)))
=> (/ (+ 2 (+ 5 (+ 6 0))) (length (2 5 6)))
=> (/ (+ 2 (+ 5 6)) (length (2 5 6)))
=> (/ (+ 2 11) (length (2 5 6)))
=> (/ 13 (length (2 5 6)))
=> (/ 13 (+ 1 (length (5 6))))
=> (/ 13 (+ 1 (+ 1 (length (6)))))
=> (/ 13 (+ 1 (+ 1 (+ 1 (length ())))))
=> (/ 13 (+ 1 (+ 1 (+ 1 0))))
=> (/ 13 (+ 1 (+ 1 1)))
=> (/ 13 (+ 1 2))
=> (/ 13 3)
=> 13/3

Problem 5: Garnering Info on Trees

Consider the problem of averaging the values in a number tree. In one sense, it's very easy: We might use sum-of-number-tree to sum the values and leaves-in-number-tree (or a variant thereof) to count the values. But that requires us to traverse the tree twice.

If our only criterion is conciseness of code, we might even flatten the number tree and then use one of the procedures from the previous problem. However, flattening a tree is a relatively expensive procedure due to the repeated appending within tree-flatten.

Is it possible to do both the summing and counting in trees like we did with lists? Of course! However, we must take a slightly different approach than the tail recursive average-v2. Instead of passing along results-so-far, we must use basic recursion (as in numbers-info) to compute the results from the bottom upward.

Write, but do not document, a procedure (number-tree-info ntree) that returns a list whose first item is the sum of all the numbers in the tree and whose second item is the total count of numbers in the tree.

> (number-tree-info (cons 1 (cons 2 (cons (cons 3 4) (cons 5 6)))))
(21 6)

Hint: Think carefully first about your base case. Then, how will you combine the results of the recursive calls?

Note that once we've written this procedure, computing the average is quite easy, remarkably like the average-v3 procedure above.

(define number-tree-average
  (lambda (number-tree)
    (apply / (number-tree-info number-tree))))

Problem 6: Documentation

Topics: Trees, higher-order procedures

Document number-tree-info.

Part C: Strings, Characters, and Ciphers

Topics: Characters, strings, higher-order procedures

A substitution cipher is a code that simply replaces one character with another in a one-to-one fashion. This is the kind of code that must be broken when solving the typical newspaper puzzle called a "cryptogram." A special case of this code is called a Caesar cipher, named for the Roman emperor Julius Caesar, who used it to communicate with his generals. A Caesar cipher simply shifts each character to another a certain number of places down the alphabet. In a Caesar cipher with a shift of 3, the letter A (character 0) would become D (character 3), P (character 15) would become S (character 18), and so on. Typically, Y (character 24) would wrap-around to the front of the alphabet to become B (character 27, or, actually character 1).

Problem 7: Shifting Characters

Write and document a procedure, (char-shift character amount) that shifts the given character the number of places, ignoring any wrap-around.

Problem 8: Making Encoders

Of course, Caesar ciphers are much more interesting when applied to strings, rather than to individual characters. It is also natural to think of a cipher as a function from strings to strings, rather than from numbers to strings. Hence, we'd like a procedure that builds ciphers.

Write, but do not document, a procedure (shift-encoder amount) that returns a procedure that takes a string as input and produces a string where each character is replaced by another whose collating sequence number differs from the original by amount.

You should strive to make your procedure as concise as possible.

> (define encode-1 (shift-encoder 5))
> (encode-1 "HELLO")
> (define encode-2 (shift-encoder 2))
> (encode-2 "MJQQT")
> (define decode-12 (shift-encoder -7))
> (decode-12 "OLSSV")
> ((o decode-12 encode-2 encode-1) "WORLD")

Part D: Playing with Polynomial Procedures

Topics: Higher-order procedures

Problem 9: Terms in a Polynomial

Document and write a procedure, (polynomial-term c n) that returns the function c*xn.

For example,

> (define two-x-cubed (polynomial-term 2 3))
> (two-x-cubed 1)
2 ; 2 * 1 * 1 * 1
> (two-x-cubed 3)
54 ; 2 * 3 * 3 * 3
> (two-x-cubed 5)
250 ; 2 * 5 * 5 * 5
> (define three-x-squared (polynomial-term 3 2))
> (three-x-squared 1)
3 ; 3 * 1 * 1
> (three-x-squared 3)
27 ; 3 * 3 * 3
> (three-x-squared 5)
75 ; 3 * 5 * 5
> ((polynomial-term 5 4) 2)
80 ; 5 * 2^4

Problem 10: Polynomial Functions

Write, but do not document, a procedure (polynomial coefs) that takes a list of coefficients for the terms x0, x1, x2, ... of a polynomial and produces a function that takes a single value, evaluating the polynomial given those coefficients at that value.

> (define line (polynomial (list 1 4))) ; Create the polynomial f(x) = 1*x^0 + 4*x^1 = 1 + 4*x
> (line 5) ; Evaluate f(5) = 1 + 4*5
> (define cubic (polynomial (list 1 4 3 -2))) ; Create the polynomial g(x) = 1 + 4*x + 3*x^2 - 2*x^3
> (cubic 5) ; Evaluate g(5) = 1 + 4*5 + 3*5^2 - 2*5^3

Note: You should try to make your solution as concise as possible (even at the potential cost of some efficiency).

Note: Since a polynomial normally has at least one term, you may assume that the list has at least one term. You need not check this precondition (or any precondition, for that matter).

Some questions and answers

Here we will post answers to questions of general interest. Please check here before emailing your questions!

Problem 3

Question: What parameters should binary-search-first take?
Answer: The format should be the same as given in the reading: (binary-search-first vec get-key may-precede? key)
Question: What should it return when it cannot find the key asked for?
Answer: Like the original, -1 would be fine.
Question: Can you give any hints?
Answer: In many senses, the problem boils down to “what should I do when I note that the middle value is equal?” There are two possibilities: (1) The middle value matches, and it is the leftmost of the matching values. (2) The middle value matches, and it is not the leftmost of the equal values. Think about how you might distinguish these cases, and what you should do in each case.
Question: Can I assume that the input vector is sorted?
Answer: You have to assume that input vector is sorted.

Problem 4

Question: Are you expecting us to use code to show all the steps or to write out by hand what each of the steps should be?
Answer: The latter: expand the computation as necessary and show how it eventually collapses to the final answer.

Problem 9

Question: Can we assume that the values returned by (polynomial-term c n) do not have to list the factorization, as was done in the example code? Similarly, must we produce the string "Evaluate f(5) = 1 + 4*5" etc. when calling ((polynomial (list ...)) val)? They were listed after semicolons, but that could easily be part of the output of the procedure as well.
Answer: Yes, these are intended/indicated as display comments.
Question: Can we use the procedure (expt x y) in Problems 9 and 10?
Answer: Yes.

Problem 10

Question: At the end of problem 10 there is a note to sacrifice efficiency for the sake of conciseness. Does this apply to problem 9?
Answer: Sure.
Question: Do we have to document this procedure?
Answer: No.


Here you will find errors of spelling, grammar, and design that students have noted. Remember, each error found corresponds to a point of extra credit for everyone. We usually limit such extra credit to five points. However, if we make an astoundingly large number of errors, then we will provide more extra credit.

  • (three-x-squared 3) is 27, not 18. [MS & RN, 1 point]
  • "Genetics" was missing a close quote in the example. [RN, 1 point]
  • Trace of average-v1 does not use list-length and list-sum. [IY, 1 point]
  • In the numbers-info procedure, the if statement should have null? [RN & JW, 1 point]
  • Problem 4 says to show the steps used in computing the average of the list (2 5 7) but the example uses (2 5 6) [JW, 1 point]
  • list-length should have used lst throughout. [BK & AW]
  • In a few places, you asked us to write documentation after we wrote the code. But you taught us to write documentation first. [SM] (Response: Yes, this is a flaw, but you can do the problems in any order you'd like.)
  • In Rebelsky's exam (but not Weinman's) there's the phrase “three or four or problems” which should be “three or four problems”. [DW]

Creative Commons License

Samuel A. Rebelsky,

Copyright (c) 2007-10 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)

This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.