MASSACHVSETTS INSTITVTE OF TECHNOLOGY epartment of Electrical Engineering and Computer Se lence 001--Structure and Interpretation of Computer Programs Spring Semester, 2005 Quiz I- Sample Solutions Closed book - one sheet of notes Throughout this quiz, we have set aside space in which you should write your answers. Please try to put all of your answers in the designated spaces, as we will look only in this spaces when gradin Note that any procedures or code fragments that you write will be judged not only on correct function, but also on clarity and good programming practice Section Numb Tutor's name: PART Value grade grader Total 100
✁✂✄✄✂☎✆✝✄✞✟✟✄ ✠✡✄✟✠✟✝✟✞ ☛☞ ✟✞☎✆✡☛✌☛✍✎ ✏✑✒✓✔✕✖✑✗✕ ✘✙ ✞✚✑✛✕✔✜✛✓✚ ✞✗✢✜✗✑✑✔✜✗✢ ✓✗✣ ☎✘✖✒✤✕✑✔ ✄✛✜✑✗✛✑ ✥✦✧✧★✄✕✔✤✛✕✤✔✑ ✓✗✣ ✠✗✕✑✔✒✔✑✕✓✕✜✘✗ ✘✙ ☎✘✖✒✤✕✑✔ ✩✔✘✢✔✓✖✪ ✄✒✔✜✗✢ ✄✑✖✑✪✕✑✔ ✫ ✬✧✧✭ ✮✯✰✱ ✲ ✳ ✴✵✶✷✸✹ ✴✺✸✯✻✰✺✼✽ ✾✸✺✽✹✿ ❀✺✺❁ ✳ ✺✼✹ ✽❂✹✹✻ ✺❃ ✼✺✻✹✽ ✟❄✔✘✤✢❄✘✤✕ ✕❄✜✪ ❅✤✜❆✫ ❇✑ ❄✓❈✑ ✪✑✕ ✓✪✜✣✑ ✪✒✓✛✑ ✜✗ ❇❄✜✛❄ ❉✘✤ ✪❄✘✤✚✣ ❇✔✜✕✑ ❉✘✤✔ ✓✗✪❇✑✔✪✦ ✩✚✑✓✪✑ ✕✔❉ ✕✘ ✒✤✕ ✓✚✚ ✘✙ ❉✘✤✔ ✓✗✪❇✑✔✪ ✜✗ ✕❄✑ ✣✑✪✜✢✗✓✕✑✣ ✪✒✓✛✑✪✫ ✓✪ ❇✑ ❇✜✚✚ ✚✘✘❊ ✘✗✚❉ ✜✗ ✕❄✜✪ ✪✒✓✛✑✪ ❇❄✑✗ ✢✔✓✣✜✗✢✦ ✡✘✕✑ ✕❄✓✕ ✓✗❉ ✒✔✘✛✑✣✤✔✑✪ ✘✔ ✛✘✣✑ ✙✔✓✢✖✑✗✕✪ ✕❄✓✕ ❉✘✤ ❇✔✜✕✑ ❇✜✚✚ ❋✑ ●✤✣✢✑✣ ✗✘✕ ✘✗✚❉ ✘✗ ✛✘✔✔✑✛✕ ✙✤✗✛✕✜✘✗✫ ❋✤✕ ✓✚✪✘ ✘✗ ✛✚✓✔✜✕❉ ✓✗✣ ✢✘✘✣ ✒✔✘✢✔✓✖✖✜✗✢ ✒✔✓✛✕✜✛✑✦ ✡✂✁✞❍ ✄✑✛✕✜✘✗ ✡✤✖❋✑✔❍ ✟✤✕✘✔ ■✪ ✡✓✖✑❍ ✩✂❏✟ ✝✓✚✤✑ ✍✔✓✣✑ ✍✔✓✣✑✔ ✬✧ ✬ ❑ ▲ ✬✧ ▼ ✬ ✭ ✭ ✥ ✥ ✟✘✕✓✚ ✧✧
6.001, Spring Semester, 2005-Quiz I- Sample Solutions Part 1:(20 points) For each of the following expressions or sequences of expressions, state the value returned as the result of evaluating the final expression in each set, or indicate that the evaluation results in an error. If the result is an error, state in general terms what kind of error(e.g. you might write ng type of arg to procedure"). If the evaluation reti built-in proced write primitive procedure. If the evaluation returns a user-created procedure, write compound procedure If the expression does not result in an error, also state the "type"of the returned expression, using You may assume that evaluation of each sequence takes place in a newly initialized Scheme system Question 1 primitive procedure: number, number -, boolean Q Question 3. amova a )) 2: number
✁✂✂✄☎ ✆✝✞✟✠✡ ✆☛☞☛ ✌✍☛✞ ☎ ✎ ✂✂✏✑✒✓✟✔ ✕ ✖ ✆✗☞✝✘☛ ✆✙✘✓✍✟✙✠✌ ✬ ✚✵✛✻ ✜✢ ✣✤✥ ✷✺✰✼✻✽✦ ☞✘✔ ✑✓✛❄ ✘✙ ✕❄✑ ✙✘✚✚✘❇✜✗✢ ✑✧✒✔✑✪✪✜✘✗✪ ✘✔ ✪✑❅✤✑✗✛✑✪ ✘✙ ✑✧✒✔✑✪✪✜✘✗✪✫ ✪✕✓✕✑ ✕❄✑ ❈✓✚✤✑ ✔✑✕✤✔✗✑✣ ✓✪ ✕❄✑ ✔✑✪✤✚✕ ✘✙ ✑❈✓✚✤✓✕✜✗✢ ✕❄✑ ★✗✓✚ ✑✧✒✔✑✪✪✜✘✗ ✜✗ ✑✓✛❄ ✪✑✕ ✫ ✘✔ ✜✗✣✜✛✓✕✑ ✕❄✓✕ ✕❄✑ ✑❈✓✚✤✓✕✜✘✗ ✔✑✪✤✚✕✪ ✜✗ ✓✗ ✑✔✔✘✔✦ ✠ ✙ ✕❄✑ ✔✑✪✤✚✕ ✜✪ ✓✗ ✑✔✔✘✔ ✫ ✪✕✓✕✑ ✜✗ ✢✑✗✑✔✓✚ ✕✑✔✖✪ ❇❄✓✕ ❊✜✗✣ ✘✙ ✑✔✔✘✔ ✩✑✦✢✦ ❉✘✤ ✖✜✢❄✕ ❇✔✜✕✑ ✪✑✔✔✘✔❍ ❇✔✘✗✢ ✕❉✒✑ ✘✙ ✓✔✢✤✖✑✗✕ ✕✘ ✒✔✘✛✑✣✤✔✑✫✬✦ ✠ ✙ ✕❄✑ ✑❈✓✚✤✓✕✜✘✗ ✔✑✕✤✔✗✪ ✓ ❋✤✜ ✚✕◆✜✗ ✒✔✘✛✑✣✤✔✑✫ ❇✔✜✕✑ ✭✮✯✰✯✱✯✲✳ ✭✮✴✵✳✶✷✮✳✦ ✠ ✙ ✕❄✑ ✑❈✓✚✤✓✕✜✘✗ ✔✑✕✤✔✗✪ ✓ ✤✪✑✔◆✛✔✑✓✕✑✣ ✒✔✘✛✑✣✤✔✑✫ ❇✔✜✕✑ ✵✴✰✭✴✷✸✶ ✭✮✴✵✳✶✷✮✳✦ ✠ ✙ ✕❄✑ ✑✧✒✔✑✪✪✜✘✗ ✣✘✑✪ ✗✘✕ ✔✑✪✤✚✕ ✜✗ ✓✗ ✑✔✔✘✔ ✫ ✓✚✪✘ ✪✕✓✕✑ ✕❄✑ ✪ ✕❉✒✑✫ ✘✙ ✕❄✑ ✔✑✕✤✔✗✑✣ ✑✧✒✔✑✪✪✜✘✗✫ ✤✪✜✗✢ ✕❄✑ ✗✘✕✓✕✜✘✗ ✜✗✕✔✘✣✤✛✑✣ ✜✗ ✚✑✛✕✤✔✑✦ ✎✘✤ ✖✓❉ ✓✪✪✤✖✑ ✕❄✓✕ ✑❈✓✚✤✓✕✜✘✗ ✘✙ ✑✓✛❄ ✪✑❅✤✑✗✛✑ ✕✓❊✑✪ ✒✚✓✛✑ ✜✗ ✓ ✗✑❇✚❉ ✜✗✜✕✜✓✚ ✜❆✑✣ ✄✛❄✑✖✑ ✪❉✪✕✑✖✦ ✮✯✹✽✻✰✺✼ ✜ ✹ ✺ ✷✛✰✶✰✻✰✻✹ ✷✛✺✼✹✿✯✛✹✢ ✼✯✶✽✹✛✾ ✼✯✶✽✹✛ ✿❀ ✽✺✺✸✹✵✼ ✮✯✹✽✻✰✺✼ ✤ ✹ ❁❂❃❄❅❆❃ ❇ ❈❉ ❁❂❃❄❅❆❃ ❊ ❋❉ ❁❇ ●❍ ❁❊ ■ ❍❉❉ ❏✢ ✼✯✶✽✹✛ ✮✯✹✽✻✰✺✼ ❏ ✹ ❁❁❑▲▼◆❂▲ ❁▲ ❊ ◆❉ ❁❊ ◆ ▲❉❉ ❍ ❋ ❖❉ ✤✢ ✼✯✶✽✹✛
6.001, Spring Semester, 2005-Quiz I- Sample Solutions Question 6 ((lambda (a) (lambda (b) (+(.O1a)(.0b)) compound procedure: number number Question P. (define aur s, (define li al-air g) (define (lin air (1e((1im1-a1r2) air lial-air))) (1 2):rist numbert
✁✂✂✄☎ ✆✝✞✟✠✡ ✆☛☞☛ ✌✍☛✞ ☎ ✎ ✂✂✏✑✒✓✟✔ ✕ ✖ ✆✗☞✝✘☛ ✆✙✘✓✍✟✙✠✌ ▲ ✮✯✹✽✻✰✺✼ ✹ ❁❁❑▲▼◆❂▲ ❁ ▲❉ ❁❑▲▼◆❂▲ ❁◆❉ ❁❊ ❁✁✂✄☎ ▲❉ ❁✁✂✄☎ ◆❉❉❉❉ ✆❉ ✼✺✶✷✺✯✼✿ ✷✛✺✼✹✿✯✛✹✢ ✼✯✶✽✹✛ ✿❀ ✼✯✶✽✹✛ ✮✯✹✽✻✰✺✼ ✝ ✹ ❁❂❃❄❅❆❃ ▲✄✞ ✆❉ ❁❂❃❄❅❆❃ ❑✟✠▲❑❋▲✄✞ ✡❉ ❁❂❃❄❅❆❃ ❁☛✄✟✠ ▲✄✞❉ ❁❑❃☎ ❁❁❑✟✠▲❑❋▲✄✞ ❍❉❉ ❁❑❅✁☎ ▲✄✞ ❑✟✠▲❑❋▲✄✞❉❉❉ ❁☛✄✟✠ ●❉ ✣✜ ✤✦✢ ☞✰✽✻ ✌✼✯✶✽✹✛✍
6.001, Spring Semester, 2005-Quiz I- Sample Solutions Consider the following simple database of personnel information. The entire database is represented as a list of entries. Each entry is made using the following constructor (define (make-entry person salary position) (list per son salary position)) The person part of an entry is created using the con define make-person list) Note that values for names and positions are represented using strings, while salaries are represented using numbers. Here is an example database (list (make-entry (make-person smiths johns henrys 30000 presidents (make-entry (make-person sioness sannes maries heathers 60000 (make-entry (make-person smiths sf (make-entry (make-person soes sjanes elizabeths 38000 assistants make-entry (make-person groes maries SvIce-presidents)) ote that the family" name is always the first element of the person abstraction, but there can be arbitrarily many” glven” names. Part 2:(17 points) Question F: Draw a box-and-pointer diagram for the structure corresponding to test, where define test (make-entry (make-per son smiths johns henrys 30000 presidents))
✁✂✂✄☎ ✆✝✞✟✠✡ ✆☛☞☛ ✌✍☛✞ ☎ ✎ ✂✂✏✑✒✓✟✔ ✕ ✖ ✆✗☞✝✘☛ ✆✙✘✓✍✟✙✠✌ ▼ ☎✘✗✪✜✣✑✔ ✕❄✑ ✙✘✚✚✘❇✜✗✢ ✪✜✖✒✚✑ ✣✓✕✓❋✓✪✑ ✘✙ ✒✑✔✪✘✗✗✑✚ ✜✗✙✘✔✖✓✕✜✘✗✦ ✟❄✑ ✑✗✕✜✔✑ ✣✓✕✓❋✓✪✑ ✜✪ ✔✑✒✔✑✪✑✗✕✑✣ ✓✪ ✓ ✸✰✽✻ ✘✙ ✑✗✕✔✜✑✪✦ ✞✓✛❄ ✑✗✕✔❉ ✜✪ ✖✓✣✑ ✤✪✜✗✢ ✕❄✑ ✙✘✚✚✘❇✜✗✢ ✛✘✗✪✕✔✤✛✕✘✔❍ ❁❂❃❄❅❆❃ ❁▼▲❃❋❃❆☎✄✁ ☛❃✄✁✟❆ ✁▲❑▲✄✁ ☛✟✁❅☎❅✟❆❉ ❁❑❅✁☎ ☛❃✄✁✟❆ ✁▲❑▲✄✁ ☛✟✁❅☎❅✟❆❉❉ ✟❄✑ ✭✳✮✂✴✸ ✒✓✔✕ ✘✙ ✓✗ ✑✗✕✔❉ ✜✪ ✛✔✑✓✕✑✣ ✤✪✜✗✢ ✕❄✑ ✛✘✗✪✕✔✤✛✕✘✔❍ ❁❂❃❄❅❆❃ ▼▲❃❋☛❃✄✁✟❆ ❑❅✁☎❉ ✡✘✕✑ ✕❄✓✕ ❈✓✚✤✑✪ ✙✘✔ ✗✓✖✑✪ ✓✗✣ ✒✘✪✜✕✜✘✗✪ ✓✔✑ ✔✑✒✔✑✪✑✗✕✑✣ ✤✪✜✗✢ ✪✕✔✜✗✢✪✫ ❇❄✜ ✚✑ ✪✓✚✓✔✜✑✪ ✓✔✑ ✔✑✒✔✑✪✑✗✕✑✣ ✤✪✜✗✢ ✗✤✖❋✑✔✪✦ ✆✑✔✑ ✜✪ ✓✗ ✑✧✓✖✒✚✑ ✣✓✕✓❋✓✪✑❍ ❁❂❃❄❅❆❃ ✁▲▼☛❑❃❂▲☎▲ ❁❑❅✁☎ ❁▼▲❃❋❃❆☎✄✁ ❁▼▲❃❋☛❃✄✁✟❆ ✄✁▼ ❅☎☎ ✄ ✄✆✟☎❆ ✄ ✄☎❃❆✄✁✄❉ ✡✝✝✝✝ ✄☛✄❃✁❅❂❃❆☎✄❉ ❁▼▲❃❋❃❆☎✄✁ ❁▼▲❃❋☛❃✄✁✟❆ ✄✆✟❆❃✁✄ ✄▲❆❆❃✄ ✄▼▲✄❅❃✄ ✄☎❃▲☎☎❃✄✄❉ ■✝✝✝✝ ✄☎▲✠❃✄✄❉ ❁▼▲❃❋❃❆☎✄✁ ❁▼▲❃❋☛❃✄✁✟❆ ✄✁▼ ❅☎☎ ✄ ✄❄✄❃❂✄❉ ✆✆✝✝✝ ✄☎▲✠❃✄✄❉ ❁▼▲❃❋❃❆☎✄✁ ❁▼▲❃❋☛❃✄✁✟❆ ✄❂✟❃✄ ✄✆▲❆❃✄ ✄❃❑❅✞▲◆❃☎☎ ✄❉ ✡✟✝✝✝ ✄▲✁✁❅✁☎▲❆☎✄❉ ❁▼▲❃❋❃❆☎✄✁ ❁▼▲❃❋☛❃✄✁✟❆ ✄✄✟❃✄ ✄▼▲✄❅❃✄ ✄✆▲❆❃✄❉ ❍✠✝✝✝ ✄✡❅✠❃❋☛✄❃✁❅❂❃❆☎✄❉❉❉ ✡✘✕✑ ✕❄✓✕ ✕❄✑ ✫✙✓✖✜✚❉✫ ✗✓✖✑ ✜✪ ✓✚❇✓❉✪ ✕❄✑ ★✔✪✕ ✑✚✑✖✑✗✕ ✘✙ ✕❄✑ ✒✑✔✪✘✗ ✓❋✪✕✔✓✛✕✜✘✗✫ ❋✤✕ ✕❄✑✔✑ ✛✓✗ ❋✑ ✓✔❋✜✕✔✓✔✜✚❉ ✖✓✗❉ ✫✢✜❈✑✗✫ ✗✓✖✑✪✦ ✚✵✛✻ ✤✢ ✣✜☛ ✷✺✰✼✻✽✦ ✮✯✹✽✻✰✺✼ ☞✢ ✏✔✓❇ ✓ ❋✘✧◆✓✗✣◆✒✘✜✗✕✑✔ ✣✜✓✢✔✓✖ ✙✘✔ ✕❄✑ ✪✕✔✤✛✕✤✔✑ ✛✘✔✔✑✪✒✘✗✣✜✗✢ ✕✘ ✱✳✂✱✫ ❇❄✑✔✑ ❁❂❃❄❅❆❃ ☎❃✁☎ ❁▼▲❃❋❃❆☎✄✁ ❁▼▲❃❋☛❃✄✁✟❆ ✄✁▼ ❅☎☎ ✄ ✄✆✟☎❆ ✄ ✄☎❃❆✄✁✄❉ ✡✝✝✝✝ ✄☛✄❃✁❅❂❃❆☎✄❉❉
6.001, Spring Semester, 2005--Quiz I- Sample Solutions Question 7: Complete the entry abstraction by providing selectors for per son, for salary and for position. For example (person test) henry) solution (define per son car (define salary cadr) (define posit Question 8: Complete the per son abstraction by providing selectors for family-name and given-name s, Value: ("anne""marie""heather") (family-name (make-person "jones""anne ""marie""heather")) Value: Jones Thus the family name is always the first name in the entry, the given names are any names after solution: define family-name car) (define given-names cdr
✁✂✂✄☎ ✆✝✞✟✠✡ ✆☛☞☛ ✌✍☛✞ ☎ ✎ ✂✂✏✑✒✓✟✔ ✕ ✖ ✆✗☞✝✘☛ ✆✙✘✓✍✟✙✠✌ ✭ ✮✯✹✽✻✰✺✼ ☛✢ ☎✘✖✒✚✑✕✑ ✕❄✑ ✳✸✱✮ ✓❋✪✕✔✓✛✕✜✘✗ ❋❉ ✒✔✘❈✜✣✜✗✢ ✪✑✚✑✛✕✘✔✪ ✙✘✔ ✭✳✮✂✴✸✫ ✙✘✔ ✂✁✂✁✮ ✓✗✣ ✙✘✔ ✭✴✂✯✱✯✴✸✦ ☞✘✔ ✑✧✓✖✒✚✑❍ ❁☛❃✄✁✟❆ ☎❃✁☎❉ ✄☎▲❑✆❃ ✝ ❁✄✁▼ ❅☎☎ ✄ ✄✆✟☎❆ ✄ ✄☎❃❆✄✁✄❉ ✽✺✸✯✻✰✺✼✢ ❁❂❃❄❅❆❃ ☛❃✄✁✟❆ ✠▲✄❉ ❁❂❃❄❅❆❃ ✁▲❑▲✄✁ ✠▲❂✄❉ ❁❂❃❄❅❆❃ ☛✟✁❅☎❅✟❆ ✠▲❂❂✄❉ ✮✯✹✽✻✰✺✼ ✞✢ ☎✘✖✒✚✑✕✑ ✕❄✑ ✭✳✮✂✴✸ ✓❋✪✕✔✓✛✕✜✘✗ ❋❉ ✒✔✘❈✜✣✜✗✢ ✪✑✚✑✛✕✘✔✪ ✙✘✔ ✟✁✰✯✂✠✸✁✰✳ ✓✗✣ ✡✯✲✳✸✠✸✁✰✳✂✫ ✑✦✢✦ ❁✞❅✡❃❆❋❆▲▼❃✁ ❁▼▲❃❋☛❃✄✁✟❆ ✄✆✟❆❃✁✄ ✄▲❆❆❃✄ ✄▼▲✄❅❃✄ ✄☎❃▲☎☎❃✄✄❉❉ ✄☎▲❑✆❃ ✝ ❁✄▲❆❆❃✄ ✄▼▲✄❅❃✄ ✄☎❃▲☎☎❃✄✄❉ ❁❄▲▼ ❅❑✁❋❆▲▼❃ ❁▼▲❃❋☛❃✄✁✟❆ ✄✆✟❆❃✁✄ ✄▲❆❆❃✄ ✄▼▲✄❅❃✄ ✄☎❃▲☎☎❃✄✄❉❉ ✄☎▲❑✆❃ ✝ ✄✆✟❆❃✁✄ ✟❄✤✪ ✕❄✑ ✙✓✖✜✚❉ ✗✓✖✑ ✜✪ ✓✚❇✓❉✪ ✕❄✑ ★✔✪✕ ✗✓✖✑ ✜✗ ✕❄✑ ✑✗✕✔❉✫ ✕❄✑ ✢✜❈✑✗ ✗✓✖✑✪ ✓✔✑ ✓✗❉ ✗✓✖✑✪ ✓✙✕✑✔ ✕❄✜✪✦ ✽✺✸✯✻✰✺✼✢ ❁❂❃❄❅❆❃ ❄▲▼ ❅❑✁❋❆▲▼❃ ✠▲✄❉ ❁❂❃❄❅❆❃ ✞❅✡❃❆❋❆▲▼❃✁ ✠❂✄❉
6.001, Spring Semester, 2005-Quiz I- Sample Solutions Part 3:(20 points) Now suppose that we want to retrieve entries from the database that satisfy certain constraints For example, we might want to get all the entries of people with the position of hacker", or we might want to get the entries of people whose first name is"Jane, or all the entries of people with alaries between 25000 and 50000. Remember our procedure (define (filter pred lst) (cond ((nulls lst) nil) ((pred (car lst))(cons (car lst)(filter pred (cdr lst)))) Else (filter Question 9: We want a way of getting entries from the database with a particular first name (where by first name, we mean the first of the "given"names, not the family name). You may assume that every entry in the database has at least one given name. You may also find the procedure stringrt, which compares two strings, to be usefu Complete the following code so that, for example, filter (called-by jane") sampledata Value:(((doe"jane"elizabetH) 3T000 "assistant") (define (called-by nam solution (lambda (x)(string=s name (car (given-names (names x)))) Question 10: Suppose we want to find all the people who have salaries at least as large as a specified amount, and who hold a particular position (filter (salary-and-position 60000"Cacker") sampledat 1ue:((("j nne""marie""Cbatcer")60000 "Hacker ") Complete the following code fragment (define(salary-and-position minimum posn) solution (lambda (entry) (and (>=(salary entry minimum (string=s (position entry) position)))
✁✂✂✄☎ ✆✝✞✟✠✡ ✆☛☞☛ ✌✍☛✞ ☎ ✎ ✂✂✏✑✒✓✟✔ ✕ ✖ ✆✗☞✝✘☛ ✆✙✘✓✍✟✙✠✌ ✥ ✚✵✛✻ ❏✢ ✣✤✥ ✷✺✰✼✻✽✦ ✡✘❇ ✪✤✒✒✘✪✑ ✕❄✓✕ ❇✑ ❇✓✗✕ ✕✘ ✔✑✕✔✜✑❈✑ ✑✗✕✔✜✑✪ ✙✔✘✖ ✕❄✑ ✣✓✕✓❋✓✪✑ ✕❄✓✕ ✪✓✕✜✪✙❉ ✛✑✔✕✓✜✗ ✛✘✗✪✕✔✓✜✗✕✪✦ ☞✘✔ ✑✧✓✖✒✚✑✫ ❇✑ ✖✜✢❄✕ ❇✓✗✕ ✕✘ ✢✑✕ ✓✚✚ ✕❄✑ ✑✗✕✔✜✑✪ ✘✙ ✒✑✘✒✚✑ ❇✜✕❄ ✕❄✑ ✒✘✪✜✕✜✘✗ ✘✙ ✫❄✓✛❊✑✔✫✫ ✘✔ ❇✑ ✖✜✢❄✕ ❇✓✗✕ ✕✘ ✢✑✕ ✕❄✑ ✑✗✕✔✜✑✪ ✘✙ ✒✑✘✒✚✑ ❇❄✘✪✑ ★✔✪✕ ✗✓✖✑ ✜✪ ✫✓✗✑✫✫ ✘✔ ✓✚✚ ✕❄✑ ✑✗✕✔✜✑✪ ✘✙ ✒✑✘✒✚✑ ❇✜✕❄ ✪✓✚✓✔✜✑✪ ❋✑✕❇✑✑✗ ✬✭✧✧✧ ✓✗✣ ✭✧✧✧✧✦ ❏✑✖✑✖❋✑✔ ✘✤✔ ✒✔✘✛✑✣✤✔✑❍ ❁❂❃❄❅❆❃ ❁❄❅❑☎❃✄ ☛✄❃❂ ❑✁☎❉ ❁ ✠✟❆❂ ❁❁❆✆❑❑✁ ❑✁☎❉ ❆❅❑❉ ❁❁☛✄❃❂ ❁ ✠▲✄ ❑✁☎❉❉ ❁ ✠✟❆✁ ❁ ✠▲✄ ❑✁☎❉ ❁❄❅❑☎❃✄ ☛✄❃❂ ❁ ✠❂✄ ❑✁☎❉❉❉❉ ❁❃❑✁❃ ❁❄❅❑☎❃✄ ☛✄❃❂ ❁✠❂✄ ❑✁☎❉❉❉❉❉ ✮✯✹✽✻✰✺✼ ✂✢ ◗✑ ❇✓✗✕ ✓ ❇✓❉ ✘✙ ✢✑✕✕✜✗✢ ✑✗✕✔✜✑✪ ✙✔✘✖ ✕❄✑ ✣✓✕✓❋✓✪✑ ❇✜✕❄ ✓ ✒✓✔✕✜✛✤✚✓✔ ★✔✪✕ ✗✓✖✑ ✩❇❄✑✔✑ ❋❉ ★✔✪✕ ✗✓✖✑✫ ❇✑ ✖✑✓✗ ✕❄✑ ★✔✪✕ ✘✙ ✕❄✑ ✫✢✜❈✑✗✫ ✗✓✖✑✪✫ ✗✘✕ ✕❄✑ ✙✓✖✜✚❉ ✗✓✖✑✬✦ ✎✘✤ ✖✓❉ ✓✪✪✤✖✑ ✕❄✓✕ ✑❈✑✔❉ ✑✗✕✔❉ ✜✗ ✕❄✑ ✣✓✕✓❋✓✪✑ ❄✓✪ ✓✕ ✚✑✓✪✕ ✘✗✑ ✢✜❈✑✗ ✗✓✖✑✦ ✎✘✤ ✖✓❉ ✓✚✪✘ ★✗✣ ✕❄✑ ✒✔✘✛✑✣✤✔✑ ✂✱✮✯✸✡✄☎✫ ❇❄✜✛❄ ✛✘✖✒✓✔✑✪ ✕❇✘ ✪✕✔✜✗✢✪✫ ✕✘ ❋✑ ✤✪✑✙✤✚✦ ☎✘✖✒✚✑✕✑ ✕❄✑ ✙✘✚✚✘❇✜✗✢ ✛✘✣✑ ✪✘ ✕❄✓✕ ✫ ✙✘✔ ✑✧✓✖✒✚✑✫ ❁❄❅❑☎❃✄ ❁✠▲❑❑❃❂❋◆✁ ✄✆▲❆❃✄❉ ✁▲▼☛❑❃❂▲☎▲❉ ✄☎▲❑✆❃ ✝ ❁❁❁✄❂✟❃✄ ✄✆▲❆❃✄ ✄❃❑❅✞▲◆❃☎☎ ✄❉ ✡✟✝✝✝ ✄▲✁✁❅✁☎▲❆☎✄❉❉ ❁❂❃❄❅❆❃ ❁ ✠▲❑❑❃❂❋◆✁ ❆▲▼❃❉ ✽✺✸✯✻✰✺✼✢ ❁❑▲▼◆❂▲ ❁ ✆❉ ❁ ✁☎✄❅❆✞✝✁ ❆▲▼❃ ❁ ✠▲✄ ❁ ✞❅✡❃❆❋❆▲▼❃✁ ❁ ❆▲▼❃✁ ✆❉❉❉❉❉ ✮✯✹✽✻✰✺✼ ✜✥✢ ✄✤✒✒✘✪✑ ❇✑ ❇✓✗✕ ✕✘ ★✗✣ ✓✚✚ ✕❄✑ ✒✑✘✒✚✑ ❇❄✘ ❄✓❈✑ ✪✓✚✓✔✜✑✪ ✓✕ ✚✑✓✪✕ ✓✪ ✚✓✔✢✑ ✓✪ ✓ ✪✒✑✛✜★✑✣ ✓✖✘✤✗✕ ✫ ✓✗✣ ❇❄✘ ❄✘✚✣ ✓ ✒✓✔✕✜✛✤✚✓✔ ✒✘✪✜✕✜✘✗✦ ❁❄❅❑☎❃✄ ❁ ✁▲❑▲✄✁❋▲❆❂❋☛✟✁❅☎❅✟❆ ■✝✝✝✝ ✄☎▲✠❃✄✄❉ ✁▲▼☛❑❃❂▲☎▲❉ ✄☎▲❑✆❃ ✝ ❁❁❁✄✆✟❆❃✁✄ ✄▲❆❆❃✄ ✄▼▲✄❅❃✄ ✄☎❃▲☎☎❃✄✄❉ ■✝✝✝✝ ✄☎▲✠❃✄✄❉❉ ☎✘✖✒✚✑✕✑ ✕❄✑ ✙✘✚✚✘❇✜✗✢ ✛✘✣✑ ✙✔✓✢✖✑✗✕❍ ❁❂❃❄❅❆❃ ❁ ✁▲❑▲✄✁❋▲❆❂❋☛✟✁❅☎❅✟❆ ▼ ❅❆❅▼✆▼ ☛✟✁❆❉ ✽✺✸✯✻✰✺✼✢ ❁❑▲▼◆❂▲ ❁❃❆☎✄✁❉ ❁▲❆❂ ❁✺✝ ❁✁▲❑▲✄✁ ❃❆☎✄✁❉ ▼ ❅❆❅▼✆▼ ❉ ❁ ✁☎✄❅❆✞✝✁ ❁ ☛✟✁❅☎❅✟❆ ❃❆☎✄✁❉ ☛✟✁❅☎❅✟❆❉❉❉
6.001, Spring Semester, 2005--Quiz I- Sample Solutions Question 11: Assume that the procedure one -of has the following behavior. It takes two argt ments, an element and a list. It successively tests for equality of the element to entries in the list sing string=?, until it either reaches the end of the list(in which case it returns false)or until it finds an element of the list that matches(in which case it returns true). Using this, supply an expression for INSERT1 in the expression below (define (has-name name) INSERT 1) (filter (has-nan sampleddata) arie""heather")60000 hacker (("roe""marie""jane")29000"vice-president")) olution lambda one-of name (given-names (names x))) Question 12: Recall the procedure (define (map proc lst) (if (null? lst) (cons (proc (car lst))(map proc (cdr lst))))) Provide an expression for INSERT2 so that evaluating(map INSERT2 sampledata)would return a list of the number of names(both family and given names) for each entry, e.g Value:(34233) You may assume that length is a procedure that returns the number of elements (or length) of a solution (lambda (x)(length (names x)))
✁✂✂✄☎ ✆✝✞✟✠✡ ✆☛☞☛ ✌✍☛✞ ☎ ✎ ✂✂✏✑✒✓✟✔ ✕ ✖ ✆✗☞✝✘☛ ✆✙✘✓✍✟✙✠✌ ❑ ✮✯✹✽✻✰✺✼ ✜✜✢ ✂✪✪✤✖✑ ✕❄✓✕ ✕❄✑ ✒✔✘✛✑✣✤✔✑ ✴✸✳✠✴✟ ❄✓✪ ✕❄✑ ✙✘✚✚✘❇✜✗✢ ❋✑❄✓❈✜✘✔✦ ✠✕ ✕✓❊✑✪ ✕❇✘ ✓✔✢✤◆ ✖✑✗✕✪✫ ✓✗ ✑✚✑✖✑✗✕ ✓✗✣ ✓ ✚ ✜✪✕✦ ✠✕ ✪✤✛✛✑✪✪✜❈✑✚❉ ✕✑✪✕✪ ✙✘✔ ✑❅✤✓✚ ✜✕❉ ✘✙ ✕❄✑ ✑✚✑✖✑✗✕ ✕✘ ✑✗✕✔✜✑✪ ✜✗ ✕❄✑ ✚ ✜✪✕ ✫ ✤✪✜✗✢ ✂✱✮✯✸✡✄☎✫ ✤✗✕✜✚ ✜✕ ✑✜✕❄✑✔ ✔✑✓✛❄✑✪ ✕❄✑ ✑✗✣ ✘✙ ✕❄✑ ✚ ✜✪✕ ✩✜✗ ❇❄✜✛❄ ✛✓✪✑ ✜✕ ✔✑✕✤✔✗✪ ✙✓✚✪✑✬ ✘✔ ✤✗✕✜✚ ✜✕ ★✗✣✪ ✓✗ ✑✚✑✖✑✗✕ ✘✙ ✕❄✑ ✚ ✜✪✕ ✕❄✓✕ ✖✓✕✛❄✑✪ ✩✜✗ ❇❄✜✛❄ ✛✓✪✑ ✜✕ ✔✑✕✤✔✗✪ ✕✔✤✑✬✦ ✪✜✗✢ ✕❄✜✪✫ ✪✤✒✒✚❉ ✓✗ ✑✧✒✔✑✪✪✜✘✗ ✙✘✔ ✁✂✄☎✆✝✞ ✜✗ ✕❄✑ ✑✧✒✔✑✪✪✜✘✗ ❋✑✚✘❇✦ ❁❂❃❄❅❆❃ ❁☎▲✁❋❆▲▼❃ ❆▲▼❃❉ ✟✠✡☛☞✌●❉ ❁❄❅❑☎❃✄ ❁☎▲✁❋❆▲▼❃ ✄▼▲✄❅❃✄❉ ✁▲▼☛❑❃❂▲☎▲❉ ✄☎▲❑✆❃ ✝ ❁❁❁✄✆✟❆❃✁✄ ✄▲❆❆❃✄ ✄▼▲✄❅❃✄ ✄☎❃▲☎☎❃✄✄❉ ■✝✝✝✝ ✄☎▲✠❃✄✄❉ ❁❁✄✄✟❃✄ ✄▼▲✄❅❃✄ ✄✆▲❆❃✄❉ ❍✠✝✝✝ ✄✡❅✠❃❋☛✄❃✁❅❂❃❆☎✄❉❉ ✽✺✸✯✻✰✺✼✢ ❁❑▲▼◆❂▲ ❁✆❉ ❁✟❆❃❋✟❄ ❆▲▼❃ ❁✞❅✡❃❆❋❆▲▼❃✁ ❁❆▲▼❃✁ ✆❉❉❉❉ ✮✯✹✽✻✰✺✼ ✜✤✢ ❏✑✛✓✚✚ ✕❄✑ ✒✔✘✛✑✣✤✔✑❍ ❁❂❃❄❅❆❃ ❁▼▲☛ ☛✄✟✠ ❑✁☎❉ ❁❅❄ ❁❆✆❑❑✁ ❑✁☎❉ ❆❅❑ ❁✠✟❆✁ ❁☛✄✟✠ ❁✠▲✄ ❑✁☎❉❉ ❁▼▲☛ ☛✄✟✠ ❁✠❂✄ ❑✁☎❉❉❉❉❉ ✩✔✘❈✜✣✑ ✓✗ ✑✧✒✔✑✪✪✜✘✗ ✙✘✔ ✁✂✄☎✆✝✍ ✪✘ ✕❄✓✕ ✑❈✓✚✤✓✕✜✗✢ ✎✰✁✭ ✁✂✄☎✆✝✍ ✂✁✰✭✂✳✶✁✱✁✏ ❇✘✤✚✣ ✔✑✕✤✔✗ ✓ ✚ ✜✪✕ ✘✙ ✕❄✑ ✗✤✖❋✑✔ ✘✙ ✗✓✖✑✪ ✩❋✘✕❄ ✙✓✖✜✚❉ ✓✗✣ ✢✜❈✑✗ ✗✓✖✑✪✬ ✙✘✔ ✑✓✛❄ ✑✗✕✔❉✫ ✑✦✢✦ ❁▼▲☛ ✟✠✡☛☞✌❍ ✁▲▼☛❑❃❂▲☎▲❉ ✄☎▲❑✆❃ ✝ ❁✡ ❖ ❍ ✡ ✡❉ ✎✘✤ ✖✓❉ ✓✪✪✤✖✑ ✕❄✓✕ ✂✳✸✡✱✑ ✜✪ ✓ ✒✔✘✛✑✣✤✔✑ ✕❄✓✕ ✔✑✕✤✔✗✪ ✕❄✑ ✗✤✖❋✑✔ ✘✙ ✑✚✑✖✑✗✕✪ ✩✘✔ ✚✑✗✢✕❄✬ ✘✙ ✓ ✚ ✜✪✕✦ ✽✺✸✯✻✰✺✼✢ ❁❑▲▼◆❂▲ ❁✆❉ ❁❑❃❆✞☎☎ ❁❆▲▼❃✁ ✆❉❉❉
6.001, Spring Semester, 2005--Quiz I- Sample Solutions Part 4(12 points)Given our little data base of personnel files, we might want to be able to sort the entries, for example by increasing salary. Here is a procedure for sorting (define (find-best best rest compare extractor) (if (null? rest) (if (compare (extractor (car rest)) find-best best (cdr rest) compare extractor))) (define (remove elt rest same) (if (null? rest) (if (same elt (car rest) (cons (car rest) (remove elt (cdr rest) same))))) (define (sort data compare extractor same (let ((trial (find-best (car data) (cdr data) compare extractor))) let ((rest (remove trial data same))) (if (null? rest) rial (cons trial (sort rest compare extractor same))))) For example, to sort our data by increasing salary, we would evaluate (sort sample data< salary We are going to measure the order of growth in time(as measured by the number of primitive operations in the computation) and in space(as measured by the maximum number of deferred operations-do not count in space the intermediate data structures constructed by the algorithm) measured as a function of the size of data, denoted by n. Assume that the procedures used for compare, extractor and same use constant time and space or each of the following questions, choose the description from these options that best describes the order of growth of the process. If you select "something else", please state why C: exponential D: quadra E: logarith somet hing else
✁✂✂✄☎ ✆✝✞✟✠✡ ✆☛☞☛ ✌✍☛✞ ☎ ✎ ✂✂✏✑✒✓✟✔ ✕ ✖ ✆✗☞✝✘☛ ✆✙✘✓✍✟✙✠✌ ✚✵✛✻ ✣✜✤ ✷✺✰✼✻✽✦ ✍✜❈✑✗ ✘✤✔ ✚ ✜✕✕✚✑ ✣✓✕✓ ❋✓✪✑ ✘✙ ✒✑✔✪✘✗✗✑✚ ★✚✑✪✫ ❇✑ ✖✜✢❄✕ ❇✓✗✕ ✕✘ ❋✑ ✓❋✚✑ ✕✘ ✪✘✔✕ ✕❄✑ ✑✗✕✔✜✑✪✫ ✙✘✔ ✑✧✓✖✒✚✑ ❋❉ ✜✗✛✔✑✓✪✜✗✢ ✪✓✚✓✔❉✦ ✆✑✔✑ ✜✪ ✓ ✒✔✘✛✑✣✤✔✑ ✙✘✔ ✪✘✔✕✜✗✢❍ ❁❂❃❄❅❆❃ ❁❄❅❆❂❋◆❃✁☎ ◆❃✁☎ ✄❃✁☎ ✠✟▼☛▲✄❃ ❃✆☎✄▲✠☎✟✄❉ ❁❅❄ ❁❆✆❑❑✁ ✄❃✁☎❉ ◆❃✁☎ ❁❅❄ ❁✠✟▼☛▲✄❃ ❁❃✆☎✄▲✠☎✟✄ ❁✠▲✄ ✄❃✁☎❉❉ ❁❃✆☎✄▲✠☎✟✄ ◆❃✁☎❉❉ ❁❄❅❆❂❋◆❃✁☎ ❁✠▲✄ ✄❃✁☎❉ ❁✠❂✄ ✄❃✁☎❉ ✠✟▼☛▲✄❃ ❃✆☎✄▲✠☎✟✄❉ ❁❄❅❆❂❋◆❃✁☎ ◆❃✁☎ ❁✠❂✄ ✄❃✁☎❉ ✠✟▼☛▲✄❃ ❃✆☎✄▲✠☎✟✄❉❉❉❉ ❁❂❃❄❅❆❃ ❁ ✄❃▼✟✡❃ ❃❑☎ ✄❃✁☎ ✁▲▼❃❉ ❁❅❄ ❁❆✆❑❑✁ ✄❃✁☎❉ ❆❅❑ ❁❅❄ ❁✁▲▼❃ ❃❑☎ ❁✠▲✄ ✄❃✁☎❉❉ ❁✠❂✄ ✄❃✁☎❉ ❁✠✟❆✁ ❁✠▲✄ ✄❃✁☎❉ ❁✄❃▼✟✡❃ ❃❑☎ ❁✠❂✄ ✄❃✁☎❉ ✁▲▼❃❉❉❉❉❉ ❁❂❃❄❅❆❃ ❁ ✁✟✄☎ ❂▲☎▲ ✠✟▼☛▲✄❃ ❃✆☎✄▲✠☎✟✄ ✁▲▼❃❉ ❁❑❃☎ ❁❁☎✄❅▲❑ ❁❄❅❆❂❋◆❃✁☎ ❁ ✠▲✄ ❂▲☎▲❉ ❁ ✠❂✄ ❂▲☎▲❉ ✠✟▼☛▲✄❃ ❃✆☎✄▲✠☎✟✄❉❉❉ ❁❑❃☎ ❁❁✄❃✁☎ ❁ ✄❃▼✟✡❃ ☎✄❅▲❑ ❂▲☎▲ ✁▲▼❃❉❉❉ ❁❅❄ ❁ ❆✆❑❑✁ ✄❃✁☎❉ ❁❑❅✁☎ ☎✄❅▲❑❉ ❁ ✠✟❆✁ ☎✄❅▲❑ ❁ ✁✟✄☎ ✄❃✁☎ ✠✟▼☛▲✄❃ ❃✆☎✄▲✠☎✟✄ ✁▲▼❃❉❉❉❉❉❉ ☞✘✔ ✑✧✓✖✒✚✑✫ ✕✘ ✪✘✔✕ ✘✤✔ ✣✓✕✓ ❋❉ ✜✗✛✔✑✓✪✜✗✢ ✪✓✚✓✔❉✫ ❇✑ ❇✘✤✚✣ ✑❈✓✚✤✓✕✑❍ ❁ ✁✟✄☎ ✁▲▼☛❑❃❂▲☎▲ ✁ ✁▲❑▲✄✁ ✝❉ ◗✑ ✓✔✑ ✢✘✜✗✢ ✕✘ ✖✑✓✪✤✔✑ ✕❄✑ ✘✔✣✑✔ ✘✙ ✢✔✘❇✕❄ ✜✗ ✕✜✖✑ ✩✓✪ ✖✑✓✪✤✔✑✣ ❋❉ ✕❄✑ ✗✤✖❋✑✔ ✘✙ ✒✔✜✖✜✕✜❈✑ ✘✒✑✔✓✕✜✘✗✪ ✜✗ ✕❄✑ ✛✘✖✒✤✕✓✕✜✘✗✬ ✓✗✣ ✜✗ ✪✒✓✛✑ ✩✓✪ ✖✑✓✪✤✔✑✣ ❋❉ ✕❄✑ ✖✓✧✜✖✤✖ ✗✤✖❋✑✔ ✘✙ ✣✑✙✑✔✔✑✣ ✘✒✑✔✓✕✜✘✗✪ ✂ ✣✘ ✗✘✕ ✛✘✤✗✕ ✜✗ ✪✒✓✛✑ ✕❄✑ ✜✗✕✑✔✖✑✣✜✓✕✑ ✣✓✕✓ ✪✕✔✤✛✕✤✔✑✪ ✛✘✗✪✕✔✤✛✕✑✣ ❋❉ ✕❄✑ ✓✚✢✘✔✜✕❄✖✬✫ ✖✑✓✪✤✔✑✣ ✓✪ ✓ ✙✤✗✛✕✜✘✗ ✘✙ ✕❄✑ ✪✜❆✑ ✘✙ ✣✓✕✓✫ ✣✑✗✘✕✑✣ ❋❉ ✸✦ ✂✪✪✤✖✑ ✕❄✓✕ ✕❄✑ ✒✔✘✛✑✣✤✔✑✪ ✤✪✑✣ ✙✘✔ ✵✴✰✭✁✮✳ ✄ ✳☎✱✮✁✵✱✴✮ ✓✗✣ ✂✁✰✳ ✤✪✑ ✛✘✗✪✕✓✗✕ ✕✜✖✑ ✓✗✣ ✪✒✓✛✑✦ ☞✘✔ ✑✓✛❄ ✘✙ ✕❄✑ ✙✘✚✚✘❇✜✗✢ ❅✤✑✪✕✜✘✗✪✫ ✛❄✘✘✪✑ ✕❄✑ ✣✑✪✛✔✜✒✕✜✘✗ ✙✔✘✖ ✕❄✑✪✑ ✘✒✕✜✘✗✪ ✕❄✓✕ ❋✑✪✕ ✣✑✪✛✔✜❋✑✪ ✕❄✑ ✘✔✣✑✔ ✘✙ ✢✔✘❇✕❄ ✘✙ ✕❄✑ ✒✔✘✛✑✪✪✦ ✠ ✙ ❉✘✤ ✪✑✚✑✛✕ ✪ ✪✘✖✑✕❄✜✗✢ ✑✚✪✑✫✫ ✒✚✑✓✪✑ ✪✕✓✕✑ ❇❄❉✦ ✂❍ ✛✘✗✪✕✓✗✕ P❍ ✚ ✜✗✑✓✔ ☎❍ ✑✧✒✘✗✑✗✕✜✓✚ ✏❍ ❅✤✓✣✔✓✕✜✛ ✞❍ ✚✘✢✓✔✜✕❄✖✜✛ ☞❍ ✪✘✖✑✕❄✜✗✢ ✑✚✪✑
6001, x=ring x emester, 2005--Quiz I-x amF le xolutions Question 13: What is the order of growth in time of the procedure findi yeats Question 14: What is the order of growth in space of the procedure findI yeats Question 15: What is the order of growth in time of the procedure remove s B Question 1m What is the order of growth in space of the procedure removes B Question 1: What is the order of growth in time of the procedure ports Remember to include the effect of findi yeot and remove Question 1E What is the order of growth in space of the procedure ports Remember to include the effect of findI yeot and remove
✁✂✂✄☎ ✆✝✞✟✠✡ ✆☛☞☛ ✌✍☛✞ ☎ ✎ ✂✂✏✑✒✓✟✔ ✕ ✖ ✆✗☞✝✘☛ ✆✙✘✓✍✟✙✠✌ ✮✯✹✽✻✰✺✼ ✜❏❍ ◗❄✓✕ ✜✪ ✕❄✑ ✘✔✣✑✔ ✘✙ ✢✔✘❇✕❄ ✜✗ ✕✜✖✑ ✘✙ ✕❄✑ ✒✔✘✛✑✣✤✔✑ ✟✯✸✶✠✁✳✂✱✂ ❀ ✮✯✹✽✻✰✺✼ ✜❍ ◗❄✓✕ ✜✪ ✕❄✑ ✘✔✣✑✔ ✘✙ ✢✔✘❇✕❄ ✜✗ ✪✒✓✛✑ ✘✙ ✕❄✑ ✒✔✘✛✑✣✤✔✑ ✟✯✸✶✠✁✳✂✱✂ ✄ ✮✯✹✽✻✰✺✼ ✜✝❍ ◗❄✓✕ ✜✪ ✕❄✑ ✘✔✣✑✔ ✘✙ ✢✔✘❇✕❄ ✜✗ ✕✜✖✑ ✘✙ ✕❄✑ ✒✔✘✛✑✣✤✔✑ ✮✳✰✴✲✳✂ ❀ ✮✯✹✽✻✰✺✼ ✜☞❍ ◗❄✓✕ ✜✪ ✕❄✑ ✘✔✣✑✔ ✘✙ ✢✔✘❇✕❄ ✜✗ ✪✒✓✛✑ ✘✙ ✕❄✑ ✒✔✘✛✑✣✤✔✑ ✮✳✰✴✲✳✂ ❀ ✮✯✹✽✻✰✺✼ ✜☛❍ ◗❄✓✕ ✜✪ ✕❄✑ ✘✔✣✑✔ ✘✙ ✢✔✘❇✕❄ ✜✗ ✕✜✖✑ ✘✙ ✕❄✑ ✒✔✘✛✑✣✤✔✑ ✂✴✮✱✂ ❏✑✖✑✖❋✑✔ ✕✘ ✜✗✛✚✤✣✑ ✕❄✑ ✑☎✑✛✕ ✘✙ ✟✯✸✶✠✁✳✂✱ ✓✗✣ ✮✳✰✴✲✳✦ ✆ ✮✯✹✽✻✰✺✼ ✜✞❍ ◗❄✓✕ ✜✪ ✕❄✑ ✘✔✣✑✔ ✘✙ ✢✔✘❇✕❄ ✜✗ ✪✒✓✛✑ ✘✙ ✕❄✑ ✒✔✘✛✑✣✤✔✑ ✂✴✮✱✂ ❏✑✖✑✖❋✑✔ ✕✘ ✜✗✛✚✤✣✑ ✕❄✑ ✑☎✑✛✕ ✘✙ ✟✯✸✶✠✁✳✂✱ ✓✗✣ ✮✳✰✴✲✳✦ ❀
6.001, Spring Semester, 2005-Quiz I- Sample Solutions Part 5(15 points) Here is a procedure for composing two procedures (def and here is a procedure for applying a given procedure some number of times (define (repeated f n) (if(=n1) CODE-ADDITION-HERED) You will consider some possible pieces of code to complete repeated. The expected behavior is (define (square x)(*x Value: " square -->#[compound -procedure 7 square (repeated square 4) Value: #[compound -procedure 81 ((repeated square 3)2) Value: 25 ((repeated square 4)2) Value: 65536 ((repeated square 2)3)
✁✂✂✄☎ ✆✝✞✟✠✡ ✆☛☞☛ ✌✍☛✞ ☎ ✎ ✂✂✏✑✒✓✟✔ ✕ ✖ ✆✗☞✝✘☛ ✆✙✘✓✍✟✙✠✌ ✧ ✚✵✛✻ ✝ ✣✜✝ ✷✺✰✼✻✽✦ ✆✑✔✑ ✜✪ ✓ ✒✔✘✛✑✣✤✔✑ ✙✘✔ ✛✘✖✒✘✪✜✗✢ ✕❇✘ ✒✔✘✛✑✣✤✔✑✪❍ ❁❂❃❄❅❆❃ ❁✠✟▼☛✟✁❃ ❄ ✞❉ ❁❑▲▼◆❂▲ ❁✆❉ ❁❄ ❁✞ ✆❉❉❉❉ ✓✗✣ ❄✑✔✑ ✜✪ ✓ ✒✔✘✛✑✣✤✔✑ ✙✘✔ ✓✒✒✚❉✜✗✢ ✓ ✢✜❈✑✗ ✒✔✘✛✑✣✤✔✑ ✪✘✖✑ ✗✤✖❋✑✔ ✘✙ ✕✜✖✑✪ ❁❂❃❄❅❆❃ ❁ ✄❃☛❃▲☎❃❂ ❄ ❆❉ ❁❅❄ ❁✝ ❆ ●❉ ❄ ✁✂☛❋✄✂✂✟✌✟✁✠❋☎☛☞☛❉❉ ✎✘✤ ❇✜✚✚ ✛✘✗✪✜✣✑✔ ✪✘✖✑ ✒✘✪✪✜❋✚✑ ✒✜✑✛✑✪ ✘✙ ✛✘✣✑ ✕✘ ✛✘✖✒✚✑✕✑ ✮✳✭✳✁✱✳✶✦ ✟❄✑ ✑✧✒✑✛✕✑✣ ❋✑❄✓❈✜✘✔ ✜✪❍ ❁❂❃❄❅❆❃ ❁ ✁✂✆▲✄❃ ✆❉ ❁❇ ✆ ✆❉❉ ✄☎▲❑✆❃ ✝ ✄✁✂✆▲✄❃ ❋❋✺ ✆ ✝✠✟▼☛✟✆❆❂❋☛✄✟✠❃❂✆✄❃ ✞ ✁✂✆▲✄❃✟✄ ❁✄❃☛❃▲☎❃❂ ✁✂✆▲✄❃ ❖❉ ✄☎▲❑✆❃ ✝ ✆ ✝✠✟▼☛✟✆❆❂❋☛✄✟✠❃❂✆✄❃ ✟✟ ❁❁✄❃☛❃▲☎❃❂ ✁✂✆▲✄❃ ✡❉ ❍❉ ✄☎▲❑✆❃ ✝ ❍✆■ ❁❁✄❃☛❃▲☎❃❂ ✁✂✆▲✄❃ ❖❉ ❍❉ ✄☎▲❑✆❃ ✝ ■✆✆✡■ ❁❁✄❃☛❃▲☎❃❂ ✁✂✆▲✄❃ ❍❉ ✡❉ ✄☎▲❑✆❃ ✝ ✟●