6.001, Spring Semester, 2007—Quiz II 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsSpring Semester, 2007Quiz IIClosed Book – two sheets of notesThroughout this quiz, we have set aside space in which you should write your answers. Please tryto put all of your answers in the designated spaces, as we will look only in this space when grading.Note that any procedures or code fragments that you write will be judged not only on correctfunction, but also on clarity and good programming practice. Also note that while there may be alot of reading to do on a problem, there is relatively little code to write, so please take the time toread each problem carefully.NAME:Section Time: Tutor’s Name:PART Value Grade Grader1 282 203 274 25Total 100For your reference, the TAs are:• Matt Brown• Austin Clement• Michael Craig• Stephen McCamant• Brennan Sherry• James Wnorowski• Sarah Wu6.001, Spring Semester, 2007—Quiz II 2Part 1. (28 points)Consider the following sequence of expressions:(define (make-switch initial)(let ((state initial))(lambda ()(let ((old state))(if (eq? state ’off)(set! state ’on)(set! state ’off))old))))(define wall-plate (make-switch ’off))(wall-plate)Suppose we trace out the evaluation of these expressions with an environment model. Below isa partially completed environment diagram. Note that each procedure and each frame is labeled,however these labels do not reflect the order in which these elements were generated. You areto use these labels to answer the questions below; specifically you should complete this diagram,and then use the labels on the parts of the environment diagram to answer the following questions.Remember that let is syntactic sugar for a procedure application.6.001, Spring Semester, 2007—Quiz II 3Question 1: For each of the following frames, indicate the lowest frame of the enclosing environ-ment, choosing one of GE, E1, E2, E3, E4 or none or not shown.Frame: Enclosing EnvironmentGEE1E2E3E4Question 2: For each of the following procedure objects, indicate the lowest frame of the environ-ment to which the procedure’s environment pointer points, choosing one of GE, E1, E2, E3, E4or none or not shown.Procedure: Procedure’s Environment PointerP1P2P3P4Question 3: For each of the following variable names, indicate the value to which it is bound inthe specified environment at the end of the evaluation of the expressions. Indicate the value bychoosing one of GE, E1, E2, E3, E4, E5 or P1, P2, P3, P4 or a symbol, a number, a list ofnumbers or a boolean value.Variable: Environment Valuemake-switch GEwall-plate GEinitial E2old E3state E46.001, Spring Semester, 2007—Quiz II 4Part 2: (20 points)We have seen in lecture that searching a tree structure is an important task in many applications.For this part of the quiz, we are going to search in a tree for the first node that satisfies a predicatereach-goal?. All we need to know about the tree abstraction, in addition to reach-goal?, is thatit includes a selector children, which when applied to a node in the tree returns a list of thatnode’s children.Our queue abstraction has the following properties:• the element at the head of the queue is selected using front-queue• a queue containing all remaining elements, except the head, is selected using rest-queue(this is a non-mutating procedure)• the procedure queue-to-list converts the queue into a list of its elements, preserving order• list-to-queue takes as argument a list of elements and returns a queue with the elements’order preserved• empty-queue? tests if the argument is an empty queueHere is a tree search procedure:(define (search start reach-goal? combine)(define (search1 queue)(if (empty-queue? queue)#f(let ((current (front-queue queue)))(if (reach-goal? current)current(search1 (list-to-queue(combine(children current)(queue-to-list (rest-queue queue)))))))))(search1 (list-to-queue (list start))))This search procedure uses a queue to keep track of nodes yet to be searched. It applies a procedure,reach-goal?, to determine when it has found the node for which it is looking, i.e. the goal node. Ifit has not found the goal node, it creates a new queue using the procedure, given by the argumentcombine, to combine children of the current node with nodes still in the queue to be checked. Notethat combine should take as input two lists, and return a list with its elements in appropriate orderfor constructing a queue.You may assume that sort is a procedure that applies to a list of nodes,and sorts that list suchthat nodes that are more likely to lead to the goal appear before nodes that are less likely to leadto the goal.6.001, Spring Semester, 2007—Quiz II 5Question 4: For a depth first search, what expression can be used in place of combine in theprocedure search?Question 5: For a breadth first search, what expression can be used in place of combine in theprocedure search?Question 6: For a best first search, what expression can be used in place of combine in theprocedure search?6.001, Spring Semester, 2007—Quiz II 6Now, let’s implement the queue abstraction. We will use a tagged data structure, and will use acons pair to point to the front and rear of the queue.(define (list-to-queue lst)(cons ’queue (cons lst(if (null? lst) ’() (last-pair lst)))))(define (last-pair lst)(if (null? (cdr lst))lst(last-pair (cdr lst))))Question 7:Provide definitions for each of the following procedures:front-queuerest-queue (this is a non-mutating procedure)queue-to-list6.001, Spring Semester, 2007—Quiz II 7Part 3: (27 points)We are going to build a new kind of data structure, called a doubly linked list, or a dlist. Thisis a data structure that has the property that we can in constant time reach the next element inthe structure as well as the previous element in the structure. We are going to build dlists out oflists, and an example is shown in the figure below:We define the following operations on dlists.(define empty-dlist ’())(define (empty-dlist? obj)(null? obj))(define (value dlist)(if (empty-dlist? dlist)(error "Cannot take value of an empty dlist")(caar dlist)))(define (next dlist)(if (empty-dlist? dlist)(error "Cannot take next of an empty dlist")(cdr dlist)))(define (previous dlist)(if (empty-dlist? dlist)(error "Cannot take previous of an empty dlist")(cdar dlist)))6.001, Spring Semester, 2007—Quiz II 8Question 8:
View Full Document
Unlocking...