6.001, Spring Semester, 2007—Quiz I 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsSpring Semester, 2007Quiz IClosed Book – one sheet 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 202 223 184 225 18Total 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 I 2Part 1: (20 points)For each of the following expressions, state the value returned as the result of evaluating the finalexpression in each set, after evaluating any previous expressions in the set; or indicate that theevaluation results in an error. If the result is an error, state in general terms what kind of error (e.g.you might write “error: wrong type of argument to procedure”). If the evaluation returns a built-inprocedure, write primitive procedure. If the evaluation returns a user-created procedure, writecompound procedure.For each question, we also ask you to identify the “type” of the returned expression, using thenotation introduced in lecture (assuming that the expression does not result in an error).You may assume that evaluation of each sequence takes place in a newly initialized Scheme system.Question 1:((lambda (a b)(- (/ a b)(+ a b)))8 4)Value: Type:Question 2:((lambda (a + b)(+ a b))3 * 4)Value: Type:Question 3:((lambda (x)(lambda (y)(expt x y)))3)Value: Type:6.001, Spring Semester, 2007—Quiz I 3Question 4:(lambda (a b) (* 2 a))Value: Type:Question 5:(define x 3)(define y 4)((lambda (x) (* x y)) 2)Value: Type:6.001, Spring Semester, 2007—Quiz I 4In the rest of this quiz, we are going to help Ben Bitdiddle plan his entry for his dorm’s NCAA“March Madness” betting pool. If you are not a basketball fan, don’t worry – you don’t need toknow about basketball to answer the questions.While the questions all follow a common theme and build on one another, they are all independent:Even if you get a question wrong, or leave it blank, you can still go on to the rest of the questionsand answer them. In those later questions you can use the names of the functions you were askedto write in earlier questions, whether or not you got that previous question correct.Some quick background. Every March, the NCAA hosts a tournament to select the national colle-giate basketball champion. Seedings for this tournament (that is, where a selected team is placed)are very important, since they determine what competition each team will face. Tournaments arerun as a single elimination event, that is, once you lose you are done. In the NCAA tournament,for example, there are four brackets, each with 16 teams, and the tournament is set up to favorteams with better (lower) seeds. In a bracket with 16 teams, the team seeded 1 would first play theteam seeded 16, 2 would play 15, and so on. The winner of the 1 versus 16 game would then facethe winner of the 8 versus 9 game, and so on. An example tournament seeding is shown below,with the winner of each game moving on to the next round.To select the seedings, the selection committee looks at many factors, one of which is a “powerrating” that measures how well a team performed during the regular season. Listed below is anexample bracket for the tournament, where each “entry” includes the team name (as a string),their seeding, and their power ranking. Notice that the ordering of this bracket is set up so thateach pair of teams defines a first round game, and the winners of each adjacent pair defines thenext round game, and so on.6.001, Spring Semester, 2007—Quiz I 5(define test-bracket(list (make-entry "UCLA" 1 2)(make-entry "Kansas" 16 5)(make-entry "Tennessee" 8 21)(make-entry "Kentucky" 9 17)(make-entry "Southern Illinois" 5 13)(make-entry "UNLV" 12 25)(make-entry "Pittsburgh" 4 10)(make-entry "Duke" 13 16)(make-entry "Arizona" 14 18)(make-entry "UNC" 3 3)(make-entry "Maryland" 11 11)(make-entry "Wisconsin" 6 4)(make-entry "Florida" 10 6)(make-entry "Memphis" 7 7)(make-entry "Texas AM" 15 8)(make-entry "Ohio State" 2 1)))Ben is interested in trying to predict the winner of the tournament (and as a consequence thewinner of each game), and we are going to help him out.Part 2: (22 points)First, the elements of a bracket are a list of entries, created using:(define (make-entry team seed ranking)(list team seed ranking))Question 6: Write an implementation for the accessors to complete this data abstraction, specif-icallyentry-teamentry-seedentry-ranking6.001, Spring Semester, 2007—Quiz I 6Ben’s goal is to predict winners of each game. For now, he assumes that there will be some procedureto predict the winner for any pair of teams. With that assumption, the following procedure willtake a bracket, and select the winner for each game, returning a new bracket with half as manyteams (just the winners). The assumption is that the procedure to which probable-winner isbound will return one of its two arguments, based on some logic that we will get to. Note that abracket is represented as a list.(define (run-a-round bracket probable-winner);; okay to assume that there are an even number of elements in bracket(if (null? bracket)bracket(cons (probable-winner (car bracket) (cadr bracket))(run-a-round (cddr bracket) probable-winner))))For example, applying run-a-round to test-bracket together with an appropriate argument forprobable-winner might return(("UCLA" 1 2)("Tennessee" 8 21)("Southern Illinois" 5 13)("Pittsburgh" 4 10)("Arizona" 14 18)("Maryland" 11 11)("Florida" 10 6)("Ohio State" 2 1))Question 7:Rewrite run-a-round in iterative form. Be sure that the result preserves the order that you sawwith the recursive version (you may want to use reverse, which is a builtin Scheme procedure thatreverses the elements of a list).6.001, Spring Semester, 2007—Quiz I 7Question 8:To complete the evaluation of a
View Full Document
Unlocking...