MASSACHVSETTS INSTITVTE OF TECHNOLOGY Department of Electrical Engineering and Computer Science 6.001 -- Structure and Interpretation of Computer Programs Quiz 1 Spring Term 1998 Closed book except for the quiz handout and one sheet of notes. If you do not have a copy of the handout with you, please raise your hand to request one. Print your name at the top of each page of this exam. We know this is tedious, but prevents problems if the pages get separated. Please write clear and concise answers to the questions posed in the spaces provided in this booklet. You may use scratch paper if you wish, but the spaces provided for the answers are the ONLY places we will look at when grading the quiz. Your answers should be brief and clear. The staff reserves the right to ignore illegible answers. In grading problems that require programming, the staff will take into consideration the style and clarity of your code, not just whether it happens to produce the right result. Before starting, please check that this booklet has all 8 pages (not counting this cover page). Print your name here:_______________________________________________ Print your tutor's name here:_______________________________________ Recitation instructor:______________________________________________ If you have any comments about this quiz, please write them here: Please do not write below this line -- reserved for administrivia. _______________________________________________________________________________ Problem Grade Grader Prob Grade Grader Grader's Comments -------------------------------------------------- ----------------- | 0 | | || 5 | | | -------------------------------------------------- | 1 | | || 6 | | | -------------------------------------------------- | 2 | | || 7 | | | -------------------------------------------------- | 3 | | || | -------------------------------------------------- | 4 | | ||TOTAL | | | -------------------------------------------------- Page 1 of 8. Your Name:______________________________________ Problem 1: Goliath Computing, Inc., has just announced a new breakthrough product: a special-purpose processor that can solve the discrete logarithm problem a million times faster than any other known computer. At a press conference called to introduce the product, Goliath's Director of Marketing announced, "Easy availability of our new Phillistine 6000 processor to users around the world destroys the security of encryption systems that use the ElGamal method. Cryptographers will have to go back to the drawing board." In the space below, say whether or not this claim is plausible, and give a reason for your opinion. Your answer should be brief -- 100 words or fewer. Be sure to write legibly. Page 2 of 8. Your Name:______________________________________ Problem 2: For the bin-assignment system described in the quiz handout, a bin is represented as a list of three items. Suppose instead that we represent bins so that a bin with N occupants (occupant-1, ... occupant-n) will have the structure described by the following box-and-pointer diagram: --------- --------- --------- --------- --------- | | | | | | | | | | | | | | /| -->| | ---->| | ---->| | ---->| | ----> ... ----->| / | | | | | | | | | | | | | | | | | | | |/ | --|------ --|------ --|------ --|------ --|------ | | | | | V V V V V bin-id bin-capacity occupant-1 occupant-2 occupant-n (a) In the space provided below, write new definitions for the constructor MAKE-BIN and the three selectors for the bin components so that bins will now have the above structure. (b) If you make the changes in part (a), do you also need to modify ADD-OCCUPANT in order for the system to still work? If so, give the new definition. If not, explain why not. Page 3 of 8. Your Name:______________________________________ Problem 3: Consider the implementation of REPLACE-BIN in the handout. Notice that it is written in terms of the elementary list operations CONS, CAR, CDR, NULL?, EQ?. A. In terms of the length of the input list, what is the order of growth in the number of steps for the process generated by REPLACE-BIN? What is the order of growth in space (i.e., the space for holding deferred operations)? Number of steps: _____________ Space: _______________ B. Complete the following alternative definition of REPLACE-BIN by giving the missing : (define (replace-bin new old list) (map list)) is: PROBLEM CONTINUES ON NEXT PAGE Page 4 of 8. Your Name:______________________________________ Problem 3 (continued): C. Louis Reasoner has suggested using the following definition of REPLACE-BIN as an alternative to the one in the handout: (define (replace-bin new old list) (define (replace-sub remaining answer) (cond ((null? remaining) answer) ((eq? (bin-id (car remaining)) (bin-id old)) (replace-sub (cdr remaining) (cons new answer))) (else (replace-sub (cdr remaining) (cons (car remaining) answer))))) (replace-sub list '())) For each of the following statements about Louis's procedure, say whether it is true or false. (More than one statement may be true.) _____ (a) It returns the same value as the original version of the procedure. ______(b) It won't run and stops with an error, resulting from the fact that OLD is an unbound variable in REPLACE-SUB. ______(c) It replaces NEW by OLD, rather than OLD by NEW. ______(d) It returns the "correct" list of results, but in reverse order. ______(e) It generates an iterative process, while the original version generates a recursive process. ______(f) It generates a recursive process, while the original version generates an iterative process. ______(g) It generates a process whose order of growth in both time (number of steps) and space (deferred operations) is proportional to the number of elements in the LIST. Page 5 of 8. Your Name:______________________________________ Problem 4: The procedure REMAINING-SPACES takes as argument a result returned by PACK and returns the number of unassigned spaces in the bins. For example, calling REMAINING-SPACES on the example result in the handout should return 7, because there are 7 remaining spaces: 1 in D1, 2 in Q1, 2 in Q3, and 2 in Q4. In the space provided below, give a definition of REMAINING-SPACES that has the following form: (define (remaining-spaces pack-result) (accumulate ... )) Feel free to implement this as a single procedure, or to define one or more appropriate subprocedures. Page 6 of 8. Your Name:______________________________________ Problem 5: In the space below, define a new procedure called ALLOW-CROWDING, which takes an integer as argument and returns a procedure that could be used as the ACCEPTABLE? argument to PACK. The procedure returned by (ALLOW-CROWDING n) should regard it as OK to assign a new student to a bin, so long as the resulting number of students in the bin does not exceed the nominal bin capacity by more than n. For example, using (ALLOW-CROWDING 2) instead of WITHIN-CAPACITY would permit the system to assign 3 students to a single, 4 to a double, 6 to a quad, and so on. Page 7 of 8. Your Name:______________________________________ Problem 6: If a run of PACK fails to assign all the students, we'd like to try to reassign the remaining students using a looser test for acceptability. Write a procedure called KEEP-PACKING that works like PACK, except that it uses a list of acceptability tests. It tries to pack the students using the first test, then tries to pack the remaining students using the second test. If more students remain, it then tries the next test, and so on. If it runs out of tests, or if it manages to pack all the students, it returns a list of the unassigned students and the bins (as does the original PACK). For example, evaluating (keep-packing students (list (both within-capacity? (make-compatible-test? incompatibilities)) (both (allow-crowding 1) (make-compatible-test? incompatibilities)) within-capacity? (allow-crowding 1)) bins)) tries to pack the students taking into account both the room capacity and the incompatibilities. If any students are unassigned it will then allow crowding, still respecting the incompatibilities. If more students remain, it will then ignore the incompatibilities and consider just the room capacity. If students still remain, it will allow crowding (still ignoring incompatibilities). (define (keep-packing students criteria bins) ...) Define this procedure in the space below. (Note that KEEP-PACKING should call PACK.) Page 8 of 8. Your Name:______________________________________ Problem 7: Louis Reasoner has been puzzling over the definition of WITHIN-CAPACITY?, which is given in the handout as (define (within-capacity? person bin) (< (length (bin-occupants bin)) (bin-capacity bin))) Louis doesn't understand the reason for including the argument PERSON, and he suggests that the procedure be implemented as follows: (define (within-capacity? bin) (< (length (bin-occupants bin)) (bin-capacity bin))) What, in fact, is the reason for the PERSON argument? Explain why Louis's modification won't work. THIS IS THE END OF THE QUIZ