6.001, Fall Semester, 2006—Quiz II 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsFall Semester, 2006Quiz 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 spaces 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:Recitation Section Time: TA’s Name:PART Value Grade Grader12345Total 100For your reference, the TAs are:• Vikki Chou• Tom Lasko• Alex Vandiver6.001, Fall Semester, 2006—Quiz II 2Part 1. (** points)We are going to create a new data structure, called a circlist or circular list. This is an orderedsequence of elements, much like a list. The difference is that this data structure is circular, i.e.,there is no explicit end to the list, as shown in the attached diagram.Once we have a circlist, we can examine the element at the current pointer to the list:>(define circlist (create-circlist ’(1 2 3 4 5)))>(head circlist)1We can also rotate the circular list, moving either to the right or the left around the circle:>(head (go-right circlist))2>(head (go-left circlist))5Question 1: We are going to create a circlist out of a traditional list, by mutating the list.Here is a template for what we need:(define (last-cons lst)(cond ((null? lst) (error "not a list"))((null? (cdr lst)) lst)(else (last-cons (cdr lst)))))(define (create-circlist lst)(cond ((null? lst) (error "not a list"))(else ANSWER1)))What expression(s) should be used for ANSWER1?6.001, Fall Semester, 2006—Quiz II 3Question 2: Suppose we want to find the “length” of a circlist, that is, how many elements are inthe circular list. We can do this by walking around the circlist, counting as we go, until we reachour initial starting point. Write the procedure length-circlist:6.001, Fall Semester, 2006—Quiz II 4Question 3: To examine an element in the circlist or to change our location in the circlist, wehave the following:(define head car)(define go-right cdr)Note that go-right takes a circlist and returns a circlist with its head one element to the right ofthe original circlist.Write a procedure called go-left, which returns a circlist with its head one element to the left ofthe original circlist.Briefly describe your go-left algorithm in English.Provide your definition.6.001, Fall Semester, 2006—Quiz II 5Part 2. (** points)We have used lists as a very convenient data structure many times during the term. Our traditionallists are based on using cons cells to glue things together. In this part, we are going to create adoubly-linked list. This means that each element in the list points to both the next element in thelist and the previous element. Thus, we can easily move in either direction along the list.To do this, we are going to implement such a list using objects with state. Here is the procedureto create an element of such a double-linked list:(define (create-node value)(let ((right #f)(left #f))(lambda (msg)(cond ((eq? msg ’value) value)((eq? msg ’right) right)((eq? msg ’left) left)((eq? msg ’set-right!)(lambda (new)(set! right new)))((eq? msg ’set-left!)(lambda (new)(set! left new)))(else (error "don’t know message" msg))))))Thus, for example:>(define test (create-node 1))>(test ’value)1>(test ’right)#fWe now want to take a traditional list as input, and create a double-linked list, composed of thesemessage-passing nodes.(define (create-double-list lst)(let ((set-of-nodes (map create-node lst)))(connect set-of-nodes ’right)(connect set-of-nodes ’left)(car set-of-nodes)))To do this, we need to write the procedure connect.6.001, Fall Semester, 2006—Quiz II 6(define (connect set dir)(cond ((null? (cdr set)) ’done)((eq? dir ’right)ANSWER4)((eq? dir ’left)ANSWER5)(else (error "unknown direction"))))Question 4: What expression(s) should be used for ANSWER4?Describe your answer briefly in EnglishProvide your codeQuestion 5: What expression(s) should be used for ANSWER5?Describe your answer briefly in EnglishProvide your code6.001, Fall Semester, 2006—Quiz II 7Question 6: Suppose we have evaluated the following:(define dlist (create-double-list ’(1 2 3 4 5)))and we want to use such a list in a manner similar to normal lists, i.e., we can look at the dcar (orthe “car” of a double-list) or the dcdr (or the “cdr” of a double-list), or we could look at the dcurwhich would be the same as a dcdr but moving in the opposition direction, i.e. toward the frontof the double-linked list.>(dcar dlist)1>(dcar (dcdr dlist))2>(dcadr dlist)2>(dcar (dcur (dcdr dlist)))1Write definitions for dcar, dcdr, dcur and dcadr.dcardcdrdcurdcadr6.001, Fall Semester, 2006—Quiz II 8Question 7:Given the ability to traverse a list in either direction, write a mapdouble function that works likemap, but on doubly-linked lists, and takes three arguments: (mapdouble fn lst dir),wherethelast argument indicates the direction in which to traverse lst, applying fn to each element of lstand producing a d¯oubly-linked list of the results. Note that if the initial value for lst points toan element midway along a double list, the result of mapdouble should include only instances ofelements from that point to the end of the list in the specified direction, and should point to thecorresponding list element in the new list. For example, if we do(define db1 (create-double-list ’(1 2 3 4))then(mapdouble square (dcdr (dcdr db1)) ’left)should return a node whose value is 9, whose left node has the value 4, etc. (rather than returningthe same doubly-linked list by pointing to the node whose value is 1).You may find the following procedures useful, and you may also find it useful to use reverse whichreverses a normal list.(define (get-last lst dir)(if (not (lst dir))lst(get-last (lst dir) dir)))(define (get-values lst dir)(if (not lst)’()(cons (dcar lst)(get-values (lst dir) dir))))Write the procedure mapdouble6.001, Fall Semester, 2006—Quiz II 9Part 3. (** points)Consider the following sequence of expressions:(define (monitor proc)(let ((args
View Full Document