Research Ideas - Northwestern University



EECS110 Homework 2, Spring 2009

Due: 11:59pm on Sunday April 19, 2009

Submission: submit your solutions at the submissions server

If you are working on lab problems, please go to:



You should do the first problem for Lab1.

Problems:

Problem 1: Integration! (hw2pr1.py) [35 points; individual or pair]

Week 2, Problem 1: Numeric Integration

[35 points; individual or pair]

Note: There is a lot of explanation and text in this lab. All the functions that you have to write in your hw2pr1.py file are labeled with PN. (where N is the problem number, e.g., 1, 2, 3, etc) and set off with a horizontal line like this:

[pic]

P0. This indicates a function to write in your hw2pr1.py file.

The goal of this lab is to build a program in Python that can do numerical integration of functions. The lab is designed to exercise the following skills:

• using Python to write functions

• composing functions, i.e., extending or adapting old one to meet new requirements

• applying functions to lists of inputs, i.e., list comprehensions or "map"

• breaking down a large problem (numerical integration) into several smaller problems

Before you begin, you need to set up your new file. Please create a new file in the IDLE editor called hw2pr1.py and at the top of that file insert a header of comments that includes your name, the date, and the name of the file. For example:

# April 14,2009

# John Smith

# hw2pr1.py -- done in lab

Overview

Integration is often described as finding the area between a mathematical function and the horizontal axis. This area is a single-value summary of the magnitude of the function across its independent variable. First, we present below a simple example of estimating an integral. Then, you will write an "integrator" function that works in general.

Recall the dbl function that we discussed last week:

def dbl(x):

""" input: a number x (int or float)

output: twice the input

"""

return 2*x

Suppose you wanted to estimate the integral of the dbl function, between 0.0 and 10.0. You could do the following.

[pic]

1. Divide the interval into 4 parts. Then the list [0, 2.5, 5, 7.5] represents the x value of the left-hand endpoint of each part of the interval.

2. Find the y-values from dbl(x) for each possible x in the list of left-hand endpoints above. These will be Y = [0, 5, 10, 15].

3. Add up the areas of the rectangles whose upper-left-hand corner is at these Y values. Each rectangle extends down to the x-axis.

4. Since there are four equal-width rectangles spanning a total of 10 units of width, each rectangle's individual width is 2.5. We find the rectangles' areas in the usual way. Their heights are contained in the list Y and their widths are 2.5, so the total area is

    0*2.5 + 5*2.5 + 10*2.5 + 15*2.5

or

    (0 + 5 + 10 + 15)*2.5

which is (30)*2.5, or 75.

Although this is quite a rough approximation for the integral, as the width of the rectangles gets smaller and smaller, it approximates the true integral more and more closely. Furthermore, the simple example above suggests a general way we can divide the problem of general numeric integration into pieces that we know how to write programs to solve. That is:

1. Divide the interval in question into N equal parts and create a list with the corresponding x values.

2. Find the y values of the function for each value of x calculated in step 1

3. Calculate the area of each rectangle under the curve (bounded by the two x values on either side and the y value of the leftmost x value)

4. Sum the areas and return the value

The rest of this lab involves writing functions to compute each of the four steps above (and optionally, to make the integral approximation slightly better) and then answering some questions about the results your integration approximation produces.

Step 1: Calculating the x values to be evaluated

Our goal here is to write the function steps(low,hi,N), which takes in two numbers low and hi and a nonnegative integer N and returns a regularly-spaced list of N floats starting at low and going up to, but not including, hi itself. This list will give us our x values (an number we want) within a given range (whatever range we want).

At first you might think that a good way to approach this problem is to use the range function directly (recall that range(low, hi, step) returns a list of integers starting at low, up to but not including hi, step apart from each other.) Unfortunately, range returns a list of integers and we need a list of floats, so a single call to range will not suffice. Instead, we will again break up this problem into two pieces:

1. generate a list of N evenly spaced floating-point numbers starting at 0.0 and going up to but not including 1.0

2. adjust this list so that it spans the correct low, hi range.

[pic]

P1. To solve step 1 above, in your hw2pr1.py file, write fracSteps(N), which should output a list of N evenly spaced floating-point values starting at 0.0 and going up to, but not including 1.0. N will be a positive integer.

Here are some examples:

>>> fracSteps(4)

[0.0, 0.25, 0.5, 0.75]

>>> fracSteps(8)

[0.0, 0.125, 0.25, 0.375, 0.5, 0.625, 0.75, 0.875]

>>> fracSteps(256)

(lots of floating-point numbers!)

NOTE: You should NOT use recursion to implement this function. A good strategy here is to use a list comprehension and the range command we looked at in class. For example:

[ float(x)/2 for x in range(5) ]

will produce the list

[0.0, 0.5, 1.0, 1.5, 2.0]

Recall that what's happening here is that range(5) is producing the list [0, 1, 2, 3, 4] and each of those values gets passed in as x to the function float(x) / 2, resulting in the list [0.0, 0.5, 1.0, 1.5, 2.0]. If we change either the list that gets produced, or the function that operates on the elements of the list, we will get a different result.

WARNING: Compare the above result to:

[ x / 2 for x in range(5) ]

which produces

[0, 0, 1, 1, 2]

Make sure you understand why.

Your list comprehension for this problem will look something like:

[                for x in range(N)]

If you want a step-by-step introduction to list comprehesions, check out the ListComprehension page.

[pic]

P2. Now write steps(low,hi,N), which should take in two numbers low and hi and a nonnegative integer N. Then, steps should return a regularly-spaced list of N floats, starting at low and going up to, but not including, hi itself.

Hint: You will want to incorporate low into TWO places in your code. What is the importance of hi-low ?

We would suggest getting rid of range at this point. Try writing your return statement to include a list comprehension that looks like the following (you'll need to fill in the missing portion (marked by ___), of course!)

[_______________for x in fracSteps(N) ]

In essence, steps is basically a floating-point version of the built-in function, range. Here are some examples of how your steps function should work:

>>> steps(0,10,4)

[0.0, 2.5, 5.0, 7.5]

>>> steps(41,43,8)

[41.0, 41.25, 41.5, 41.75, 42.0, 42.25, 42.5, 42.75]

Step 2: Calculating the y values

Now that we have our x values, we need calculate the y value of the function at each of these x positions. We'll again use list comprehensions to make this process simple and fast! Although our goal is to handle arbitrary functions, we'll start with a concrete function and build up.

[pic]

P3. Write a function dbl_steps(low,hi,N) that will double each of the values in the list that your steps function creates. Again, try to use a list comprehension that takes advantage of your steps function. That is, consider how you could use [ ... for x in steps(low,hi,N)] in writing dbl_steps. This may turn out to be less difficult than it seems at first glance.

Here is an example:

>>> dbl_steps(0,1,4)

[0.0, 0.5, 1.0, 1.5]

[pic]

P4. Write fsteps(f,low,hi,N), which should do the same thing as dbl_steps, but with an arbitrary function f that is passed in as the first input. You might be best off copying dbl_steps and changing it. Here are some examples:

>>> fsteps(dbl,0,1,4)

[0.0, 0.5, 1.0, 1.5]

>>> import math

>>> fsteps(math.sin,0,math.pi,6)

[0.0, 0.5, 0.87, 1.0, 0.87, 0.5]

(note: the above values are rounded versions of what actually gets displayed!)

>>> fsteps(math.exp,0,3,3)

[1.0, 2.7182818284590451, 7.3890560989306504]

# run dir(math) for the math functions (after "import math")

# run help(math.sin) for a bit more description of any f'n

>>> fsteps(dbl,-10,10,500)

[-20.0, ... 499 more list elements ...]

You might note that if you wrote fsteps first, then you wouldn't need to write dbl_steps -- you could just use fsteps with dbl as the initial input.

This kind of generality is sometimes a good thing... . However, some people find that they like to write a couple of specific examples before generalizing.

Visualizing your functions

Now that you can generate x and y values for your functions, it would be nice to see them plotted graphically. Please follow the link below that describes how to plot your functions in python. There's nothing to submit in this part, but throughout the rest of the lab it will be nice to have the ability to visualize your functions and your integration approximations. When you understand how to plot functions, please return to this page and continue the lab.

Click here to go the EECS 110 Plot Page

Steps 3+4: Calculate the area of the rectangles under the curve and putting it all together

Now that you can calculate the x values and the corresponding y values for functions of 1 input, you are ready to do the last two steps--use these values to calculate the area of the rectangles they form, and then sum these areas to compute the integral approximation.

[pic]

P5. Write the function finteg (described in more detail below). Its behavior just generalizes the step-by-step integration example depicted and described above. You will want to use built-in functions and functions that you've already written in previous parts of this lab! Feel free to simply copy this function signature and docstring as-is and then fill in the return statement:

def finteg(f,low,hi,N):

""" finteg returns an estimate of the definite integral of the function f (the first input) with lower limit low (the second input) and upper limit hi (the third input) where N steps are taken (the fourth input) finteg simply returns the sum of the areas of rectangles under f, drawn at the left endpoint of the N steps taken from low to hi

"""

Hints: This function will be VERY short, but it can be a little tricky to write. Go very carefully through the example at the start of this lab, matching the concrete numbers in that example with the inputs to finteg . What corresponds to what?

Also, don't rewrite your fsteps function from the previous part of this lab - simply use it. If you use fsteps , the finteg function does not need list comprehensions or map or recursion at all...but sum will be useful.

Here is how sum works:

>>> sum( [10, 4, 1] )

15

>>> sum( range(0,101) )

5050

Here are some examples to check.

>>> finteg(dbl,0,10,4)

75.0

Help - I get 60 instead of 75!! You may be dividing an int by an int with a resulting rounding error... Multiply low by 1.0 to create a float value, for example.

>>> import math

>>> finteg(math.sin, 0, math.pi, 1000)

1.9999983550656628 # pretty good - should be 2.0

>>> finteg(sq,0,3,1000000) # a million steps will give it pause

8.9999865000044963 # close! - should be 9.0

Questions to answer in your hw2pr1.py file

The last required part of the lab (and HW problem 1) involves using your finteg function to answer a number of questions. You should put your answers either within comments or within triple-quoted strings in your hw2pr1.py file. Strings are easier because you don't need to preface multiple lines with the comment character, #. The first problem is done in a string as an example:

[pic]

Q0. Explain why the true value of the last example should be 9.

The answer in the hw2pr1.py file would look like:

""" Q0. The "true value" of finteg(sq,0,3,1000000) -- that is, the integral of sq(x) from a low limit of 0 to a high limit of 3 -- equals

x**3 / 3.0, evaluated at 3.0 MINUS

x**3 / 3.0, evaluated at 0.0

These evaluate to 27.0/3.0 - 0.0, which equals 9.0

"""

[pic]

Q1. The following function, c, traces the upper arc of a semicircle from -2 to 2 :

def c(x):

return (4 - x**2)**0.5

Place this function into your hw2pr1.py file and confirm the values of

>>> finteg(c,0,2,2)

3.7320508075688772

>>> finteg(c,0,2,20)

3.2284648797549815

Next, find the values of finteg(c,0,2,200) and finteg(c,0,2,2000) .

As N goes to infinity, what does the value of this integral become?

[pic]

Q2. Sometimes, integrals without closed-form solutions are so important that we simply define a function to be their solution! The natural log, sometimes written ln(x) is one such example. It is defined as

[pic]

This function is a built-in part of the math library under the name math.log(x).

Write a Python function ln(x,N) that uses your finteg to compute the natural log of x using N steps. How accurate are ln(4.2,100) and ln(4.2,10000) in comparison with the real value of math.log(4.2)?

Note: You should include ln(x, N) in your hw2pr1.py file, but what we are really interested in is the answer to the above question. (You just need to write this function to answer the question.)

[pic]

Q3. Using finteg as a guide, write a new function, finteg_tr, that uses a trapezoid for each small interval, instead of rectangles.

[pic]

Submission

You should submit your hw2pr1.py file at the Submission Site.

This is the end of Lab1.

The rest of the problems are the part of Homework 2, also accessible here:



Problem 2: The Sleepwalking Student (hw2pr2.py) [35 points; individual or pair]

Week 2, Problem 2: The sleepwalking student

[35 points; individual or pair] filename: hw2pr2.py

For this problem, you will write functions to simulate and investigate the behavior of a sleepwalking student (more formally known as a "random walk"). You should place these functions in a file named hw2pr2.py.

Part 1. First function (just to copy) rs()

Near the top of your file, be sure to have the following:

import random # this can go anywhere at the top of the file

def rs():

""" rs chooses a random step to make and returns it

notice that rs() requires parentheses, but takes

no inputs at all!

"""

return random.choice([-1,1])

You will thus be able to call on this rs() function whenever you want to obtain a new, random step. A big advantage of this is that it will be extremely easy to change what is meant by random step in the future. As long as all the rest of your code uses rs, you will be able to change the one line in rs in order to take much bigger or smaller random steps.

An alternative is to use the line

from random import *

If you use this line instead of the one above, you will not need to include the random. in front of calls to choice or other functions within the random module.

For this problem, string multiplication is very useful here. Here is an example to remind you how this works. The example with the 10 spaces shows how you can position text further to the right on the screen.

>>> 'spam'*3

spamspamspam

>>> 'start' + ' '*10 + 'end'

start end

Similar to this last example, you will want to multiply the string ' ' (consisting of one space) by different values for some of the functions below.

Part 2. Second function (to write) rwPos

Write a function named rwPos( start, nsteps ) which takes two inputs: an integer start, representing the starting position of our sleepwalker, and a nonnegative integer nsteps, representing the number of random steps to take from this starting position. The name, rwPos is meant to suggest that this function returns the position of a random walker. Be sure that your rwPos does return the position of the sleepwalker after nsteps random steps, where each step moves either plus 1 or minus 1 from the previous position.

Printing/debugging code to include:

As part of your rwPos function, include a line of debugging code that prints what s is each time the function is called. See the examples below for what this might look like.

Examples:

>>> rwPos( 40, 4 )

start is 40

start is 41

start is 42

start is 41

start is 42

42

>>> rwPos( 40, 4 ) # won't be the same each time...

start is 40

start is 39

start is 38

start is 37

start is 36

36

Even if you are comfortable using while or for loops, you should use recursion to implement rwPos for this problem. This is because this assignment ultimately exercises the functional and recursive style of computational problem-solving. There will be plenty of loops later in the term... .

Part 3. Third function to write rwSteps

Write rwSteps( start, low, hi ) which takes three inputs: an integer start, representing the starting position of our sleepwalker, an integer low, which will always be nonnegative, representing the smallest value our sleepwalker will be allowed to wander to, and an integer hi, representing the highest value our sleepwalker will be allowed to wander to. You may assume that hi ≥ start ≥ low . As soon as the sleepwalker reaches at or beyond the low or hi value, the random walk should stop. When it does stop, rwSteps should return the number of steps (hence the "Steps" in its name) that the sleepwalker took in order to finally reach the lower or upper bound.

Printing/debugging code:

As part of your rwSteps function, you should include a line of debugging code that prints a visual representation of your sleepwalker's position while wandering. Feel free to be more creative than the simple 'S' in the example below. For example, consider 0->-< (a true sleepwalker!)

Examples:

>>> rwSteps( 10, 5, 15 )

S

S

S

S

S

S

S

S

S

S

9 # here is the return value!

>>> rwSteps( 10, 7, 20 )

S

S

S

S

S

S

S

S

S

S

S

S

11

Again, you should use recursion to implement rwSteps for this problem. Hint: this problem is tricky because you are adding a random step and adding to the ongoing count of the total number of steps. One suggestion for the recursion is to use the call rwSteps( newstart, low, hi ) as the recursive call, with an appropriate assignment to newstart on the line above it... .

Need more time or space?

You can get more memory for recursion by adding this to the top of your file:

import sys

sys.setrecursionlimit(50000)

This provides 50000 function calls in the recursive stack. You can also slow down the simulation by adding this line to the top of your file:

import time

Then, in your rwSteps or rwPos functions, you can include the line

time.sleep(0.1)

which pauses for 0.1 second. Adjust as you see fit!

Part 4. Analysis of random walks

With these three functions working, you have the computational raw materials to start investigating these two (closely related) questions:

• What is the average final signed-displacement for a random walker after making N random steps? The "signed-displacement" is the signed (positive or negative) distance from the initial starting point. This is just the output of rwPos. Do not use abs.

• What is the average square of the final signed-displacement for a random walker after making N random steps, in terms of N? Be sure you square before you average the values.

You should adapt the random-walk functions you wrote to investigate these two questions. In particular, you should

• Write versions of rwPos and rwSteps that do not print any debugging or explanatory information. Rather, they should just return the final position or number of steps, respectively. Call these new versions rwPosPlain and rwStepsPlain . Be careful! the recursive calls will need to change, too... .

• Come up with a plan for how you will answer these questions. This plan should include writing at least one additional python function other than those written above. For example, you might consider writing a function that collects a lot of data and then presents a useful summary of that data -- perhaps using map or a list comprehension.

• Implement and test your additional function(s) to help your investigation.

• Report the answers you find from these computational tests. To do this, place your answers inside your python program file by either making them comments (using the # symbol) OR, even easier, including them in triple-quoted strings (since they can include newlines). For example,

"""

In order to compute the average signed displacement for a random walker after N random steps, I ...

(briefly explain what you did and your results)

(1-2 sentences for each question is OK)

"""

Thus, your file should include (1) answers to these two questions and how you approached them and (2) your python functions including whatever additional function(s) you wrote to help answer these questions. Make sure to include explanatory docstrings and comments for every function that you write!

Please include any references you might have used - you're welcome to read all about random walks online, if you like. However, you should also feel free not to bother - whether your answers are correct or not will have no effect on grading this problem. It will be graded on whether your functions work as they should, whether they would be helpful in answering those questions, and in the clarity and effectiveness of your write-up.

Submission

You should submit your hw2pr2.py file at the Submission Site.

Problem 3: Recursive Rendering (hw2pr3.py) [30 points (+ 15 extra points); individual or pair]

Week 2, Problem 3: Python Bonsai

[30 points + 15 points (extra); individual or pair] filename: hw2pr3.py

This problem asks you to create two classic kinds of recursive images: a spiral and a tree made of line segments (and optionally the Koch Snowflake). If you are so inclined, you can make your tree more realistic than just a stick tree and get extra credit.

On a typical computer, the turtle drawing module is installed and ready to use. (If for some reason your computer doesn't have turtle installed, then you can use the csturtle module instead. To learn more about how to get csturtle, go here.)

To learn how to use turtle and to see all of it's commands, click here.

Note: When you run a program with turtle commands, a special window will open where the drawing will take place (This window may "hide," appearing BEHIND the other windows). If you run the program again, that same window will be used again. However, when you want to finally close that drawing window, you must first type done() at the IDLE prompt. Then you can close the window (for example, by clicking on the red circle at the top left of the window on a Mac).

To simplify grading, please be sure to name your functions as specified in these problems... . The graders thank you!!

Part 1

Write a function

spiral( initialLength, angle, multiplier )

that uses the csturtle drawing functions to create a spiral that has its first segment of length initialLength and whose neighboring segments form angles of angle degrees. The multiplier will be a float that will indicate how each segment changes in size from the previous one. For example, with a multiplier of 0.5 each side in the spiral should be half the length of the previous side.

The spiral should stop drawing when it has reached a side length of less than 1 pixel or greater than 1000 pixels... .

Part 2

"The fallen tree" the idea here is to create a function that draws the side-view of a tree:

svTree( trunkLength, levels )

Here is an example of the output from my function when svTree( 128, 6 ) is run:

[pic]

and another example of the output when svTree( 50, 2 ) is run:

[pic]

Note that these are really side view! Of course, calling left(90) before the call to svTree will yield a more traditional pose... .

The key thing to notice about both of these pictures is that the pen is back at the start (root) of the tree at the end of the function call! This is the key to all happiness when specifying recursive images!

One thing not to worry about is the number of branches (anything greater than 1 is OK), the exact angle of branching, the reduction of the trunkLength in sub-branches, etc. Design your own tree by making aesthetic choices for each of these.

Submission

You should submit your hw2pr3.py file at the Submission Site.

Not enough? Extra credit options...

Choice 1: Your own recursive designs...

[15 points, individual or pair]

For extra credit of up to 5 points, feel free to design and implement your own recursive artwork. One starting point might be "sprucing up" your svTree function further by adding other cool features. We're "pining" for some interesting variants. If you do add extra features to your tree -- or create any other work -- make sure to "fir"nish us with a comment at the very top of your code indicating what you did and how to invoke your function.

Consider using the fill and color settings or changing the theme away from trees completely. The CS turtle reference page provides documentation for the functions available from the turtle module. See the description of a function name on that page.

Choice 2: The Koch curve

[15 points, individual or pair]

A more focused task for an additional possible 5 points extra credit is to create a function named

snowflake(sideLength, levels)

The idea is that snowflake will draw levels recursive levels of the Koch Snowflake, a fractal curve that is described here, among other places on the web. Basically, a Koch snowflake of level 0 is simply an equilateral triangle with side length equal to sideLength. Each increment of level replaces the middle third of all of the snowflake's sides with a "bump" that is, itself, a smaller equilateral triangle.

One hint that may or may not be helpful to you is that in our solution, we write a helper function called snowflakeSide( sideLength, levels ) that draws just one side of the underlying equilateral triangle. Then, the snowflake function was quite similar to the tri() example from class. The key recursion occurs in snowflakeSide. This division of labor is not required, however - there are a number of alternative ways to organize it.

Here are four steps of the Koch curve's progression:

[pic]

Submission

You should submit your hw2pr3.py file at the Submission Site.

Overall Instructions

Each of these questions asks you to write several short Python functions and/or an English response. Please place all of your answers for problems 2 and 3 into a Python plain-text file named hw2pr2.py , hw2pr3.py (changing the problem number as appropriate). Please use the function names suggested by the problems - this will help us grade things!

Docstrings and Comments

Every function that you write must have a docstring. The docstring should explain how many inputs the function takes, what these inputs are supposed to be, and what the function returns. The doctring is intended for the user of your function. In contrast, comments in your code are used to explain details that are important to a programmer who might be reading your code (that "programmer" could be you - it's easy to forget what you had in mind when you wrote your code!). Any function that is doing anything even modestly complex or non-obvious deserves some explanatory comments. We'll look for your docstrings and comments, so be sure to include them.

A Note on using Recursion

This assignment exercises the facility to write functions recursively. If you have some programming experience, you may be familiar with other, non-recursive strategies for solving these problems. Even if you do know such non-recursive strategies, however, we ask that you use recursion to solve the problems on this assignment. After all, our primary goal here is to practice an important problem-solving concept and technique, not simply to solve these particular problems... .

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download