6.001 Spring 98: Quiz 1 Grading

Problem 1

The correct answer is that the Marketing Director's claim is probably nonsense. The security of ElGamal encryption is based on the difficulty of computing discrete logarithms, and the best-known algorithms for this are close to exponential in the number of digits in the prime. So all cryptographers need do is to increase the number of digits by a few, and this would make up for the millionfold speed increase of the new processor. Any real breakthrough is cracking public-key cryptosystems would have to come from an algorithmic advance, not just raw processor speed.

Although there is something called "quantum computing", which could provide an exponential speedup on certain kinds of problems. No one knows how to build a real quantum computer. If they did, it would blow away ElGamal encryption and many other problems.

Maximum grade for the problem was 11 points. The grading was broken down into three parts:

3 for saying that it was not a plausible claim, with something that seemed like a relevant explanation
5 for describing that doing modular exponentiation is exponentially easier than doing discrete logs it was important that they mention "exponentially" or some how show that relationship between the two. Also they should say that because of this, a simple speedup is insufficient.
-2 for getting the order of growth notation of the two problems wrong or leaving out something implying "exponential"
3 for explaining that that any speedup in computation can easily met by increasing the size of the prime used.

Points in each of the sections were given depending on the clarity and solidness of the expression of the idea for that section.

Problem 2

(a) The new selectors and constructors are

(define (make-bin id capacity occupants)
  (cons id (cons capacity occupants)))

(define (bin-id bin)
  (car bin))

(define (bin-capacity bin)
  (cadr bin))

(define (bin-occupants bin)
  (cddr bin))

(b) No changes to add-occupant are needed, because it is written in terms of the selectors and constructors. Indeed, this is one of the main points of data abstraction: we can change the underlying representation of a data object without changing the procedures that use the data object, since the selectors and constructors form an abstraction barrier.

The problem was worth a maximum of 15 points, with 10 points for (a) and 5 points for (b).

Problem 3

A. If the length of the input list is n, the order of growth is Theta(n), both in number of steps and in space.

B. The required expression is

(lambda (bin)
  (if (eq? (bin-id bin) (bin-id old))
      new
      bin))

C. Items (d) and (e) are true, the rest are false.

The problem was worth 14 points.

Part A: (4 points, 2 for each answer). Anything that said linear, n, or length of list, was considered correct.

Part B: (3 points) In general

3 Points for correct,
2 Points for minor/syntax error
1 Point for wrong but on the right track
0 Points for wrong track, incorrect form.

Common errors:

-1 for syntax error
-1 for each part of 'if' wrong (predicate, consequence, or else)
-1 for missing bin-id's
-3 wrong number of arguments to lambda/not a map expression

Part C: Sum of following calculation:

+1 for each correct answer
-1 for each incorrect answer
0 for each one left blank.

But any negative sum was considered a zero.

Problem 4

One possible correct answer is


(define (remaining-spaces pack-result)
  (accumulate
   +
   0
   (map (lambda (bin)
	  (- (bin-capacity bin) (length (bin-occupants bin))))
	(cadr pack-result))))

but there are lots of correct answers. A slightly better answer is


(define (remaining-spaces pack-result)
  (accumulate
   +
   0
   (map (lambda (bin)
	  (max 0 (- (bin-capacity bin) (length (bin-occupants bin)))))
	(cadr pack-result))))

since this takes account of the possibility that bins may be overcrowded.

The problem was worth 15 points. Some of the common errors were

-1 for trying to get the rooms as (cdr pack-result) rather than (cadr pack-result)
-1 for starting the accumulation using nil rather than 0
-2 for doing a redundant test that the room capacity is non-zero before adding it in. (This, of course, produces the right answer, but it seems a useless thing to do.)
5-10 points if the person had a good plan, but the code was messed up in various ways.
5 or less, if the plan for the program seemed wrong (e.g., calling remaining-spaces recursively).

Problem 5

The most straightforward answer is

(define (allow-crowding n)
  (lambda (person bin)
    (< (length (bin-occupants bin)) (+ n (bin-capacity bin)))))

We graded using a "points off" scale, from a perfect score of 15. The most common problems were:

Missing the LAMBDA needed to return a procedure: -8
Procedure returned, but wrong parameter list: -4
Wrong mathematics: -3, but simple fencepost (off-by-one) errors only -2
Wrong returned type (typically integer instead of boolean): -5
Combining with make-compatible?: -5
Missing call to length (for occupants): -2
Created a procedure but forgot to return it as value: -2

These are not truly additive, since we often took off fewer points for combinations of errors than would be indicated above. One "classic combination" was to use BOTH to construct a procedure (combining with make-compatible?), but not using a LAMBDA in the overcrowding argument. This was a total of 7 points out of 15 (by the scale above it would have been only 2 points for combining with make-compatible? and missing the LAMBDA)

Problem 6

One possible answer is

(define (keep-packing students criteria bins)
  (if (or (null? students) (null? criteria))
      (list students bins)
      (let ((result (pack students (car criteria) bins)))
	(keep-packing (car result)	;the remaining students
		      (cdr criteria)	;the remaining criteria
		      (cadr result))))) ;the partially filled bins

The problem was graded out of 15 points. If you had the right program structure, including recursive step and base case, you obtained between 10-15 points. Small errors that were still acceptable for this range of points: cadr/cdr errors, incorrect number of parens for let, slight imperfection in base case.

If you had a good idea about what needed to be done, but had serious errors in the recursive step which produced incorrect answers, you obtained between 5 and 10 points.

If you weren't able to come up with a procedure that came close to the answer, you scored between 0-5 points.

Problem 7

15 points

In grading Problem 7 of the quiz we were mainly looking for students to understand the fact that changing the number of arguments that within-capacity? takes will cause an error when we try to use it as the predicate in the pack procedure or as one of the tests in the both procedure. These predicates are assumed to take two arguments (a person and a bin) so changing the argument list of within-capacity? to only take a bin will cause a "too many arguments" error to occur.

Some students attempted to provide fixes for the "incompatibility" or arguments problems. If the fix was not correct, we took somewhere in the order of 2 to 3 points off. In some cases, we also took 2 points off for lack of clarity of the idea.

If the students seem to know that the number of arguments should not be changed, but did not demonstrate reasonably that they knew why (e.g. you can't change the procedure because that's how the other predicates look like) we took between 3 and 7 points off depending on what the answer of the student seemed to convey.

For students who explained what the person argument was useful for, but did not explained why eliminating it won't work, we took between 8 and 10 points. And for students that didn't understand what was going on we gave no credit.

Return to 6.001 Home Page