6.01, Spring Semester, 2008—Assignment for Week 2, Issued: Tuesday, Feb. 12 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.01—Introduction to EECS ISpring Semester, 2008Assignment for Week 2, Issued: Tuesday, Feb. 12This week’s work gives you practice with higher-order procedures, i.e., procedures that manipulateother procedures. Tuesday’s lecture, the software lab, and the on-line tutor problems all explorePython’s support for functional programming as a means of capturing commons patterns. Thedesign lab extends your work from last week, by applying higher-order procedures to the design ofrobot behaviors.Overview of this week’s work. . . to do i n software lab You’ve seen in homework how to represent sets as lists. In softwarelab, you’ll look at a different representation of sets that uses higher-order procedures, and alsopractice the material on higher-order procedures that was presented in lecture.. . . homework to do before the start of your design lab on Feb 14 or 15• Read the class notes and review the lecture handout.• Do the first half of the on-line tutor problems for week 1 (the part that is due before designlab).• Read the entire description of the design lab, so that you will be ready to work on it whenyou get to lab.. . . to do in design lab Just as last week, the design lab will begin with a nanoquiz. The quizmay include material from the class notes, from the on-line tutor problems due that day, or fromthe design lab desc ription. The quiz w ill be given in the first 15 minutes of lab, and if you miss it,we will not give you time to make it up before starting the lab, so please don’t be late.After the quiz, you should work with your sam e partner from last week. (We’ll change partnersin about two weeks.) This week’s lab will extend the work on behaviors that you did last week tocover non-deterministic behaviors and using the PCAP framework to design behaviors.. . . homework due at the beginning of your next design lab on Feb 21 or 22• Additional problems to do using the on-line tutor.• Lab writeup to hand in.In general, written homework should be handed in at the beginning of the following week’s softwarelab. But next Tuesday, February 19, is an MIT virtual Monday, so there will be no lecture. So fornext week, homework should be handed in at the beginning of the design lab.6.01, Spring Sem es ter, 2008—Ass ignment for Week 2, Issued: Tuesday, Feb. 12 2Software Lab for Week 2Reminder:On lab laptops or Athena terminals, you should start by executingathrun 6.01 updatein a Unix terminal window. This creates the Desktop/6.01/lab2 directory that will containthe code files mentioned in this handout.If you are running from an Athena terminal, you should also executeadd -f 6.01to get the appropriate versions of Idle and Python.If you are using your own laptop, you should download the lab code files from the courseWeb site, linked from the Calendar page. Today’s code file is ps2-software-lab.pyLecture review on higher-order procedur esThe code file for today’s lab contains several of the higher-order procedures shown in lecture,including summation, deriv, and newtonsMethod. Here’s what’s in the file, so you can have it infront of you as you work on these exercises today.def summ ation ( low , high ,f, next ):s =0x= lowwhile x <= high :s = s + f(x)x = next( x )return sdef fixed Point (f, f irstGue ss ):def close ( g1 , g2 ):return abs(g1 - g2 ) <.0001guess = firstGuessnext = f ( guess )while not close ( guess , next ):guess = nextnext = f ( guess )return nextdef deriv ( f ):dx =0.0001def df(x ):return (f(x+ dx )- f ( x ))/ dxreturn dfdef newtonTr a nsform ( f ):def g(x ):return x - f(x )/ deriv (f )( x)return gdef newtonTr a nsform ( f ):return lambda x: x - f ( x )/ deriv (f )( x)6.01, Spring Sem es ter, 2008—Ass ignment for Week 2, Issued: Tuesday, Feb. 12 3def newtons Method (f , first Guess ):return fixe dPoint ( n ewtonTransf o rm (f), firs tGuess )## c omputi ng square roots by Newton ’s methoddef newto nSqrt (x ):return newton s Method (lambda y: y**2 - x ,1.0)Question 1: Define a simple procedure called inc that takes a number as input and returnsthat numb e r plus 1, and a simple procedure square that takes a numeric input and returnsthe square. What will Python print at each step when you evaluate the following sequence:>> inc (7)How about if you evaluate>> incWhat if you e valuatedef com pose (f , g ):return lambda x: f ( g (x ))>> co mpose ( inc , inc )Then>> co mpose ( inc , inc )(3)And finally>> a = compose ( inc ,inc )>> a (4)>> b = compose ( inc , square )>> b (5)>> c = compose ( square ,inc )>> c (5)Predict what the result will be at the end of each line, and then try it and see if you werecorrect. Check with a staff member if the results are puzzling.Question 2: Show how to use the summation procedure from lecture to compute• 13+ 23+ 33+ · · · + 1003• 14+ 34+ 54+ · · · + 994Question 3: Show how to use the newtonsMethod procedure from lecture to solve the equationy4+ 2y2= xfor y, with x = 1. Try it for other pos itive values of x. (Hint: Compare the use ofnewtonsMethod in lecture for computing square roots.)6.01, Spring Sem es ter, 2008—Ass ignment for Week 2, Issued: Tuesday, Feb. 12 4Representing sets as proceduresIn homework last week, you explored representing sets using Python lists. Another way to representa set is as a procedure that takes a value as input and returns True if the value is in the set, andFalse otherwise. For example,def s1(x ):return x in [ ’ this ’, ’ is ’ , ’my ’, ’ set ’, ’ of ’, ’strings ’]would represent the set of six strings. That may seem hardly different from the list representationyou worked with for homework, but notice that we could also have something like:def s2(x ):return x > 99and this would represe nt the set of all numbers greater than 99 (an infinite set).Question 4: Define some sets (both finite and infinite). How can you test your definitions?Question 5: For homework last week, you implemented the setUnion and setIntersectionoperations in terms of lists. In terms of the PCAP framework, these are means of combina-tion for sets.Define setUnion and setIntersection for sets represe nted as procedures and create sometests to show that they work. They take two sets as input and return a set.Hint 1 (caveat): Rememb e r that the results of these operations must be sets, in the
View Full Document
Unlocking...