6.01, Fall Semester, 2007—Assignment Week 5, Issued: Tuesday, Oct. 2 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.01—Introduction to EECS IFall Semester, 2007Assignment Week 5, Issued: Tuesday, Oct. 2To do this week: NOTE: TWO LECTURES, TWO SOFTWARE LABS!...in Tuesday software lab, 10/21. Start writing code and test cases for the numbered questions in the software lab. Paste allyour code, including your test cases, into the box provided in the “Software Lab” (Part 5.1)problem on the on-line Tutor. This will not be graded....before lecture on Thursday, 10/41. Nothing....in Thursday software lab, 10/41. Start writing code and test cases for the numbered questions in the software lab. Paste allyour code, including your test cases, into the box provided in the “Software Lab” (Part 5.2)problem on the on-line Tutor. This will not be graded.2. Get the handout for next Thursday’s lab....No Lecture Tuesday, 10/9...before the lab Thursday, 10/111. Do the on-line Tutor problems for week 5 that are due on Thursday (Part 5.3).2. Do the writeup for the 10/2 and 10/4 software labs (in this handout) providing writtenanswe rs (including code and test cases) for every numbered question in this handout....before lecture Tuesday, 10/161. Do the writeup for the 10/11 design lab (NOT in this handout).2. Do the nanoquiz; it will be based on the material in the lecture notes and the on-line Tutorproblems due on Thursday.6.01, Fall Semester, 2007—Assignment Week 5, Issued: Tuesday, Oct. 2 2On Athena or the lab laptops make sure you execute:athrun 6.01 updateso that you can get the Desktop/6.01/lab5 directory which has the files mentioned in thishandout.• You need the file differenceEquationWithInput.py.• You need the file soar-graph.py.During this lab, please use the lab laptop for Tuesday’s software lab. If you are using yourown laptop for Thursday’s software lab, download the files from the course Web site (onthe Calendar page).Tuesday Software Lab: Speed of differe nce equation solvingIn this lab, we will be using python’s features for timing software. Since our experience is that thetiming functions are not very portable, please work in pairs and use the lab laptops.In earlier lectures, you learned that the solution to a homogeneous difference equation can berepresente d in closed form using the equation’s natural frequencies. In to day’s lecture you learnedthat when a difference equation has an input, that is the equation is not homogeneous, the solutionis more complicated to compute and that computation is probably best accomplished using aprogram.One general form for a difference equation with input (we will se e another form just below) isy(n) = α1y(n − 1) + α2y(n − 2) + . . . αKy(n − K) + βox(n) + β1x(n − 1) + . . . βLx(n − L)where x(n) is the input and is a given sequence. To determine y(n) from the above differenceequation, it is necessary to specify the values of the coefficients α1. . . αKand βo. . . βL, the initialvalues y(0) . . . y(K − 1), and value of x(n) for all n.One way to specify the input x is use a procedure. For example, consider defining x(n) using thepython proceduredef x(n):return 1In this case x(n) = 1 for all n.In today’s lab we will be examining and modifying an implementation of a difference equation class,and will then use that class to develop a feel for orders of growth. Examine the difference equationclass defined in differenceEquationWithInput.py. You will notice that the difference class usesa different format for specifying a difference equation, one that turns out to be much more easilymanipulated when using transform techniques to be describe d in a later lecture. Specifically, thedifference equation format used in the difference equation class isKXk=0aky(n + k) =LXl=0blx(n + l).A note should be made about the order of the coe ffic ients. In the polynomial class, the c oefficientsfor a polynomial z2+ 2z + 3 would be given as a list [1, 2, 3]. In following that convention, the6.01, Fall Semester, 2007—Assignment Week 5, Issued: Tuesday, Oct. 2 3coefficients of a difference equation go from higher to lower order, so that a list of the y coefficientswould be [ak, ak−1, ..., ao]. Note that this same seemingly backward convention is true for initialconditions as well, the intial values are [y(K − 1), .., y(0)]. This may seem confusing, as the kthcoefficient of a difference equation is not the kthelement of the list. We agree, but the commonconvention is against us.Consider the Fibonacci example. In order to create an instance of the difference equation class thatcan be used to compute the Fibonacci numbers, it is necessary to c reate an instance associatedwith the difference equationy(n) = y(n − 1) + y(n − 2).Here, there is no input, and therefore x(n) = 0 for all n. Loading differenceEquationWithInput.pyand then typing the following com mand in the interpreter:>>> fib = DifferenceEquationWithInput([1, 0], [1, -1, -1], [1], lambda n: 0)will create an difference equation instance which will generate the Fibonacci numbers.Question 1. How are the αk’s and βl’s related to the ak’s and the bl’s in the above two formsof difference equations?If you examine the DifferenceEquationWithInput class, you will notice that two methods are imple-mented for computing the nthvalue of the solution to the difference equation. One method usesiteration, and the other uses recursion. To test your understanding of the class implementation,please answer the following questions.Question 2. What does the line vals = [nextVal] + vals[:-1] in the valIter function accomplish?Question 3. What does the linedotProd(self.outCoefficients[1:], [self.valRecur(n-i-1) for i in range(self.order)])in the valRecur function accomplish?A clever plotIt can often be revealing to plot the series of values a difference equation generates. Please refer tothe week 4 assignment for instructions on how to plot using SoaR (the assignment is on the coursecalendar page if you do not have it handy).Question 4. Demonstrate that you understand how the difference equation class works by usingthe class to solve and plot the solution to the difference equation y(n) = 0.5y(n−1)+x(n−1)where y(0) = 0 and x(n) = 1 for all n.Question 5. Now use the difference equation class to solve and plot the solution to the differenceequation y(n) = −0.5y(n − 1) + x(n − 1) where y(0) = 0 and x(n) = 1 for all
View Full Document
Unlocking...