Research Ideas - Northwestern University



EECS110 Homework 1, Spring 2009

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

Submission: submit your solutions at the submissions server

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



You should do the first two problems for Lab1.

Problems:

Problem 1: Data (hw1pr1.py) [25 points; individual or pair]

Week 1, Problem 1: Data!

[25 points; individual or pair]

Part 0: Logging in and running Python and IDLE

An easy way to start Python and IDLE is by clicking on the IDLE icon in the "dock" at the bottom of the screen. It's the one with the stylized yellow and blue pythons on it. If you can’t find it, click the Windows start button shown below:

[pic]

and click on IDLE for Python. After that, open a new file and add a suitable comment at the top—for example:

# Homework 1, Problem 1 (Lab)

# 04/07/09

Save your file as hw1pr1.py - perhaps on the desktop (easy to find) or in a new folder (better organized).

Part 1: working at the Python interpreter (or shell)

Arithmetic with numbers, lists, strings, and booleans.

To get started, try a few arithmetic, string, and list expressions in the Python interpreter, e.g.,

>>> 40 + 2

42

>>> 40 ** 2

1600

>>> 40 % 2

0

>>> 'hi there!'

hi there!   (notice Python's politeness!)

>>> 'who are you?'

who are you?   (though sometimes it's a bit touchy.)

>>> L = [0,1,2,3]   You can label data (here, a list) with a name (here, the name L)

(no response from Python)

>>> L

[0,1,2,3]   You can see the data (here, a list) referred to by a name (here, L)

>>> L[1:]

[1,2,3]   You can slice lists (here, using the name L)

>>> L[::-1]

[3,2,1,0]   You can reverse lists (or strings!) using "skip"-slicing with a -1 as the amount to skip.

>>> [0,1,2,3][1:]

[1,2,3]   You can slice lists using the raw list instead of the name (Not that this would be very useful, admittedly!)

>>> 100*L + [42]*100

(a list with 500 elements that I'm too lazy to type here)

>>> L = 42   You can reassign the name L to another value, even of a different type- now, L names the integer 42, instead of the list it used to represent.

(no response from Python)

>>> L == 42   Two equals are different than 1! This tests for equality.

True

>>> L != 42   This tests for "not equal."

False

Errors or Exceptions

If you didn't type things in perfectly, Python will reply with an error or an exception, as it is often called. See if you can make Python create the following exceptions, but don't spend more than a minute or so in total!

SyntaxError  

TypeError  (try slicing an integer for example!)

ZeroDivisionError  

IndexError  (try an out-of-bounds index)

OverflowError  (remember that integers will crash the machine before overflowing)

Part 2: Lists of integers

This problem will exercise your slicing-and-indexing skills. First, you should copy (or type) into your hw1pr1.py file the following lines:

# starting lists for part 2

pi = [3,1,4,1,5,9]

e = [2,7,1]

When you hit F5 (or click Run and then click Run Module F5), these two lists will be recognized by the Python shell.

The challenge is to create several lists using only the list labeled pi, the list labeled e, and the four list operations here --

list indexing pi[0]

list slicing e[1:]

list concatenation, + pi[:1] + e[1:]     (don't use + to add values numerically)

the list-making operator, [ , ] [ e[2], e[0] ]

For each one, place your answer into an appropriate variable in your hw1pr1.py file (see example below). Include a comment on the line above, as well. Though not mandatory, you might try to use as few operations as possible, to keep your answers elegant and efficient. For example,

Example problem Use pi and/or e to create the list [2,5,9]. Store this list in the variable answer0.

Answer to the example problem

# Creating the list [2,5,9]

answer0 = [e[0]] + pi[-2:]

Please leave a blank line or two between your answers (to keep the graders happy)!

Remember that you can use the python interpreter to try things out!

Here are the problems:

Use pi and/or e to create the list [7,1]. Store this list in the variable answer1.

Use pi and/or e to create the list [9,1,1]. Store this list in the variable answer2.

Use pi and/or e to create the list [1,4,1,5,9]. Store this list in the variable answer3.

Use pi and/or e to create the list [1,2,3,4,5]. Store this list in the variable answer4.

Part 3: Strings

This problem continues in the style of the last one, but uses strings rather than lists. So, it asks you to create specified strings that result from using only the following three string literals, which you should type into your hw1pr1.py file at this point:

n = 'northwestern'

u = 'university'

c = 'class_eecs_110_python'

You may use any combination of these four string operations:

String indexing, e.g., n[0]

String slicing, e.g., u[1:]

String concatenation, +, e.g., c + n

Repetition, *, e.g., 42*c (using integers is OK here)

Again, less is more: the number of operations in our shortest answers are in parentheses- you might find even more efficient ones! However, any answer is OK - there's no requirement to use fewer operations.

Example problem: Use n and c to create 'nano'. Store this string in the variable answer42.

Answer to example

# Creating the string 'nano'

answer42 = n[0] + c[2] + n[0] + c[-2]

Create northeasternuniversity Store this string in the variable answer5.

Create west_east_university Store this string in the variable answer6.

Create nirvana Store this string in the variable answer7.

Create easterparty_110110 Store this string in the variable answer8.

Create python_110_eecs_class Store this string in the variable answer9.

If you have gotten to this point, you have completed the first problem from Lab 1! You should submit your hw1pr1.py file at the Submission Site.

Problem 2: Functioning smoothly (hw1pr2.py) [25 points; individual or pair]

Week 1, Problem 2: Functioning smoothly!

[25 points; individual or pair]

Part 0: Create a new file

To hold your answers and work from this portion of the lab, use IDLE to create a new file (or save the current one with the new name). Be sure to name the file for this part of the lab (and homework) hw1pr2.py.

Part 1: Using built-in functions

To begin, simply use the interactive Python window to try out some of the built-in functions:

>>> range(0,100)

[0,1,2,...,99]  range returns a list of integers

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

5050  sum sums a list of numbers, and range creates a list of integers. Note that when you use range, as with almost everything in python, the right endpoint is omitted!

>>> sum([40,2])

42   a roundabout way of adding 40+2

>>> help(sum)

(an explanation of sum)   help is a good thing—ask for it by name!

>>> dir(__builtins__)

(a huge list of built-in functions, all possible errors, etc.)   dir is also useful, listing everything from a particular file (or module); the special __builtins__ module is, well, built-in!

How to type__builtins__? There are two underscores both before and after the lowercase letters: the underscore, _, is shift-hyphen on most computer keyboards (between the right parenthesis and the plus sign).

If you look carefully in the big list of stuff returned from dir, you will find the sum function you used above. You will not, however, find some other important functions, for example, sin or cos or sqrt. All of these functions (and many more) are in the math module. By the same token, there are many, many more modules (files) of functions available for you to use….

Part 2: importing other code (or "modules")

To access functions that are not built-in by default, you need to load them from their modules. There are a couple of ways to do this:

(1)  You can import the module and then access its functions with the module name:

>>> import math

(no response from Python)

>>> math.sqrt(9)

3.0  Note that sqrt returns a float even if its input is an int.

>>> math.cos(3.14159)

-0.999...  Note that cos et al. take radians as input and 3.14159 != math.pi, that is to say it's only an approximation. Try math.cos(math.pi), as well.

(2)  Tired of typing math. in front of things? You can avoid this with

>>> from math import *

(no response from Python)  The asterisk * here means "everything." This will bring all of the functions and constants from the math module into your current python environment, and you can use them without prefacing them by math.

>>> cos(pi)

-1.0

This would have had to be math.cos(math.pi) before the new "from math import *" import statement.

Part 3. Creating your own functions in a file

Python has lots of functions, the building blocks of computation. What distinguishes Python from other computing environments is the ease and power of creating your own functions.

Here, we will create a few in your hw1pr2.py file. In that file, below any comments you may have at the very top, type (or paste!) the following function definition:

def dbl(x):

""" dbl returns twice its input

input x: a number (int or float)

"""

return 2*x

Next, load this dbl function into the interpreter by hitting the F5 key.

Then, try it out at the interpreter:

>>> dbl(21)

42

The above code creates a function named dbl that outputs twice what it gets as input. The string inside triple quotes """ is called the docstring (documentation string)—this should describe what the function outputs (here in the first line) and what the function inputs (here in the second line). It becomes part of Python's built-in help system. Finally, in the function's last line its work is done and the result is returned.

We will ask you to include a docstring in all of your functions (even simple ones such as these, in order to feed the habit). This self-documenting feature in Python is especially important for making your functions understandable, both to others and to yourself!

Using help to access docstrings

It's worth noting that Python's help command simply prints a function's docstring. As a result, when imported, your dbl function is already a fully-integrated part of the Python language and help system. Try typing help(dbl) at the interpreter prompt:

>>> help(dbl)

Help on function dbl in module __main__:

dbl(x)

dbl returns twice its input

input x: a number (int or float)

Part 4: Try it out! 6 functions to write…

To begin, you may want to include the line

from math import *

or the line

import math

near the top of your hw1pr2.py file. That way, you'll be able to use any functions from the math module as needed in your solutions.

Include a docstring that describes what your function does and what its inputs are for each function.

Example: Write the function tpl(x), which takes in a numeric input and outputs three times that input.

Answer to example: might be something like this, in hw1pr2.py:

def tpl(x):

""" tpl returns thrice its input

input x: a number (int or float)

"""

return 3*x

The functions to write:

1. Write sq(x), which takes in a (floating-point) number named x as input. Then, sq should output the square of its input.

2. interp(low,hi,fraction) takes in three numbers, low, hi, and fraction, and should return a floating-point value that linearly interpolates between low and hi as far as fraction specifies. That is, if fraction is zero, low will be returned. If fraction is one, hi will be returned, and values of fraction between 0 and 1 lead to results between low and hi. See the examples below for additional detail.

Your function should also work if fraction is less than zero or greater than one. In this case, it will be linearly extrapolating, rather than interpolating. But we'll stick with the name interp anyway.

From the above description, it might be tempting to divide this function into several cases and use if, elif, and the like. However, it is possible to write this function without using any conditional (if) constructions at all. Some examples:

>>> interp(1.0, 3.0, 0.25) # a quarter of the way from 1.0 to 3.0

1.5

>>> interp(0, 10, 0.42) # 42% of the way from 0 to 10

4.2

Actually, you might get 4.2000000000000002 or something similar, depending on your implementation. This is OK, it simply reflects the finite precision (in binary) available to the computer.

>>> interp(24, 42, 0) # 0% of the way from 24 to 42

24.0

>>> interp(102, 117, -4.0) # -400% of the way from 102 to 117

42.0

3. Write a function checkends(s), which takes in a string s and returns True if the first character in s is the same as the last character in s. It returns False otherwise. The checkends function does not have to work on the empty string (the string '').

Examples:

>>> checkends('no match')

False

>>> checkends('hah! a match')

True

>>> help(checkends)

This function sees if the first and last characters of its input are the same.

Input: a string, s

Of course, your docstring may be different—or, feel free to just paste this one….

4. Write a function flipside(s), which takes in a string s and returns a string whose first half is s's second half and whose second half is s's first half. If len(s) (the length of s) is odd, the first half of the input string should have one fewer character than the second half. (Accordingly, the second half of the output string will be one shorter than the first half in these cases.)

Here you may want to use the built-in function len(s), which returns the length of the input string, s.

Examples:

>>> flipside('homework')

workhome

>>> flipside('carpets')

petscar

These last two functions combine string and arithmetic processing.

5. Write convertFromSeconds(s), which takes in a nonnegative integer number of seconds s and returns a list in the same format as above. In this case, you should be sure that

0 ≤ seconds < 60

0 ≤ minutes < 60

0 ≤ hours < 24

There are no limits on the number of days.

For instance,

>>> convertFromSeconds(610)

[0, 0, 10, 10]

>>> convertFromSeconds(100000)

[1, 3, 46, 40]

6. Finally, write readSeconds(s), a function that takes in a number of seconds, s, and returns a string that expresses that span of time in terms of days, hours, minutes, and seconds - with the same constraints as in problem 9, above. Your function should handle plurals and singulars correctly, as well (see examples).

Keep in mind that readSeconds should return a string, it should not use the print command at all! Also, you'll likely want to call convertFromSeconds as you write readSeconds. Here are a few examples:

>>> readSeconds(80)

0 days, 0 hours, 1 minute, 20 seconds

>>> readseconds(100000)

1 day, 3 hours, 46 minutes, 40 seconds

Submitting your file

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

This is the end of Lab1.

Below is the rest of Homework 1.

Problem 3: Rock-paper-scissors (part 2) (hw1pr3.py) [20 points; individual]

Week 1, Problem 3: The Road Not Taken: Choosing Code Paths

[20 points; individual]

This problem asks you to write three Python functions that test the use of the if elif and else constructs in python. Be sure to test your functions carefully. Also, be sure to include a docstring under the signature line of each function. The docstring should indicate what the function computes (outputs) and what its inputs are or what they mean.

Please put all of your functions for this problem in a single file named hw1pr3.py. Thus, all of the parts of this problem will be submitted in a single file. Please name your functions exactly as specified (including upper/lower case) -- it will help keep the graders happy -- which is always a good thing!

(#1) Building from last week's rock-paper-scissors game (which did not have to be fair), for this week, write a function rps() that plays a game of rock-paper-scissors fairly.

That is, it should first choose randomly from the three choices, though it should not reveal that choice! Then, the function should ask the user for her choice. Afterwards, it should print its original choice, the user's choice, and then declare the winner.

In addition, your rps function should print a warning if the user does not input one of 'rock', 'paper', or 'scissors'.

Choosing items at random from a sequence

To generate a random element from a list, model your code from the following example:

from random import *

s = choice( [ 'thread', 'yarn', 'twine' ])

print 'I chose', s

The above code will print a potentially different string each time it is run.

Print vs. return

Note that rps() takes no inputs and it has no return value -- it's a function that interacts with the user only via print and raw_input statements. Thus, rps does not need to return anything. It is a good example of a function in which print is the desired means of interaction.

Playing again with while

Optionally, your function could use a while loop, in which it asks the user to play again and then continue (or not), based on their answer. This is not required, but if you'd like to do so, the following example shows how a while loop works:

answer = 'no'

while answer == 'no':

[body of the program]

answer = raw_input('Would you like to stop? ')

Examples

Here are two separate example runs with the user's input in blue -- feel free to adjust the dialog for the sake of yourself (or the graders):

>>> rps( )

Welcome to RPS! I have made my choice.

Choose your poison: scissors

You chose scissors.

I chose rock.

I win!

And I didn't even cheat this time!

>>> rps( )

Welcome to RPS! I have made my choice.

Choose your poison: paper

You chose paper.

I chose rock.

You win!

I may have to reconsider my strategy in this game...

Submitting your file

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

Problem 4: Function Frenzy (hw1pr4.py) [30 points; individual or pair]

Week 1, Problem 4: Fun with Functions

[30 points; individual or pair]

This problem asks you to write the following Python functions using recursion. Be sure to test these functions carefully. Be sure to include a docstring under the signature line of each function. The docstring should indicate what the function computes (outputs) and what its inputs are or what they mean.

Please put all of your functions for this problem in a single hw1pr4.py file. Thus, all of the parts of this problem will be submitted in a single file. Be sure to name your functions exactly as specified.

Also, the mult, dot, ind, and scrabbleScore functions should all be done using recursion. Compare them to the power, mysum, mylen, and sajak functions we did in class this week.

1. mult( n, m ) should output the product of the two integers n and m. Since this would be a bit too easy if the multiplication operator * were used, for this function, you are limited to using addition/subtraction/negation operators, along with recursion. (Use the power function we did in class as a guide.) Some examples:

>>> mult( 6, 7 )

42

>>> mult( 6, -3 )

-18

2. dot( L, K ) should output the dot product of the lists L and K. If these two input lists are not of equal length, dot should output 0.0. If these two lists are both empty, dot also should output 0.0. You should assume that the input lists contain only numeric values. (Compare this with the mysum example we did in class, but be sure to use both lists...!) Recall that the dot product of two vectors or lists is the sum of the products of the elements in the same position in the two vectors. for example, the first result is 5*6 plus 3*4, which is 42.0 (if we use a float).

>>> dot( [5,3], [6,4] )

42.0

>>> dot( [1,2,3,4], [10,100,1000,10000] )

43210.0

>>> dot( [5,3], [6] )

0.0

3. Write ind(e, L), which takes in a sequence L and an element e. L might be a string or, more generally, a list. Your function ind should return the index at which e is first found in L. Counting begins at 0, as is usual with lists. If e is NOT an element of L, then ind(e, L) should return any integer larger than or equal to len(L). It can be len(L) exactly, as shown below in these examples:

>>> ind(42, [ 55, 77, 42, 12, 42, 100 ])

2

>>> ind(42, range(0,100))

42

>>> ind('hi', [ 'hello', 42, True ])

3

>>> ind('hi', [ 'well', 'hi', 'there' ])

1

>>> ind('i', 'team')

4

>>> ind(' ', 'outer exploration')

5

4. letterScore( let ) should take as input a single-character string and produce as output the value of that character as a scrabble tile. If the input is not one of the letters from 'a' to 'z', the function should return 0.

To write this function you will need to use this mapping of letters to scores

[pic]

What!? Do I have to write 25 or 26 if elif or else statements? No! Instead, use the in keyword:

>>> 'a' in 'this is a string including a'

True

>>> 'q' in 'this string does not have the the letter before r'

False

Phew!

This problem does not require recursion. But it's used in the next one... .

5. scrabbleScore( S ) should take as input a string S, which will have only lowercase letters, and should return as output the scrabble score of that string. Ignore the fact that, in reality, the availability of each letter tile is limited. Hint: use the above letterScore function and recursion. (Compare this with the the mylen example we did in class.)

Here are some examples:

>>> scrabbleScore('quetzal')

25

>>> scrabbleScore('jonquil')

23

>>> scrabbleScore('syzygy')

25

Submitting your file

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

Extra Problems:

Extra Credit Option 1: Pig Latin (hw1ec1.py) [15 points, individual or pair]

Week 1, Extra Problem 1: Pig Latin

[15 points; individual or pair]

This problem is inspired by

[pic]

Warm Up

[5 points]

Write pigLatin( s ), which will take as input a string s. s will be a single word consisting of lowercase letters. Then, pigLatin should output the translation of s to pig latin, according to these slightly altered rules:

If the input word has no letters at all (the empty string), your function should return the empty string

If the input word begins with a vowel, the pig latin output simply appends the string 'way' at the end. 'y' will be considered a consonant, and not a vowel, for this problem.

Hint: Consonant letters in the English alphabet are B, C, D, F, G, H, J, K, L, M, N, P, Q, R, S, T, V, W, X, Z, and Y.

Example

pigLatin('one') returns 'oneway'

If the input word begins with a consonant, the pig latin output is identical to the input, except that the input's initial consonant is at the end of the word instead of the beginning and it's followed by the string 'ay'.

Example

pigLatin('be') returns 'ebay'

Of course, this does not handle words beginning with multiple consonants correctly. For example, pigLatin('string') returns 'tringsay'.++

Don't worry about this. However, if you would like to tackle this more challenging problem, see the extra credit, below... .

The real pig latin challenge

[10 points]

Create a function called spamLatin( s ) that handles more than one initial consonant correctly in the translation to Pig Latin. That is, spamLatin moves all of the initial consonants to the end of the word before adding 'ay'. (You may want to write and use a helper function to do this.)

Also, spamLatin should handle an initial 'y' either as a consonant OR as a vowel, depending on whether the y is followed by a vowel or consonant, respectively. For example, 'yes' has an initial y acting as a consonant. The word 'yttrium', however -- element #39 for anyone who's as chemically challenged as I am -- has an initial y acting as a vowel. Here are some additional examples:

>>> spamLatin('string')

ingstray

>>> spamLatin('yttrium')

yttriumway

>>> spamLatin('yoohoo')

oohooyay

If you think about this problem thoroughly, you'll find that not every possible case has been accounted for - you are free to decide the appropriate course of action for those "corner cases."

Submitting your file

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

Extra Credit Option 2: Scoring papers (hw1ec2.py) [15 points, individual or pair]

Week 1, Extra Problem 2: Scrabble-scoring your files...

[15 points; individual or pair]

This problem offers the chance to interact with files in Python. In particular, it asks you to develop functions that will compute the scrabble score of the text inside arbitrary files.

The function to write... scoreFile( fileName )

For this problem you should write a function named scoreFile( fileName ) that takes in a string, which is the name of the file to be scored. Then, your function should open that file, read its contents, and compute the following:

• The total scrabble score of all of the characters in the file. Non-alphabetic characters get a score of 0. Both upper- and lower-case letters, however, should count toward this total according to their usual scrabble scores.

• The total number of alphabetic characters in the file. This includes both upper- and lower-case letters.

• The average scrabble-score-per-letter for the file.

In particular, scoreFile should return a list of these three quantities: the total score first, the number of letters second, and the average score per letter third.

For example, here are our answers using the two files named cow.txt and gburg.txt (downloadable below):

>>> scoreFile( 'gburg.txt' )

[225, 143, 1.5734265734265733]

>>> scoreFile( 'cow.txt' )

[83, 45, 1.8444444444444446]

File handling in Python

File-handling is not too bad in Python. To get started, you might want to download these two files to your desktop by right-clicking each link (control-clicking on a Mac):

cow.txt, an Ogden Nash poem

gburg.txt, the preamble to the Gettysburg Address

Here is a function that illustrates how to open and extract the contents of a file:

def printFileToScreen( fileName ):

""" simply prints the contents of the file to the screen

input: fileName, a string with the file's name

"""

f = file( fileName ) # f is the opened file

text = f.read() # text is the name of all of f's text

f.close() # this closes the file f - a good idea

print 'The file contains:' # drumroll

print # blank line

print text # ta da!

You would be able to run this, as long as you're in the folder in which the files are located, by invoking

>>> printFileToScreen( 'cow.txt' )

With any changes to the file name you'd like! Try this out, and then modify the function above to begin implementing your scoreFile function.

Although this assignment does not require creating a file, here is an example showing that it is not difficult to do:

#

# an example that creates (or overwrites) a file

#

def writeToFile( fileName ):

""" a function demonstrating how to create a new file and

write to it. If the file (named fileName) already

exists, it will be overwritten

"""

f = file( fileName, 'w' ) # f is the file, opened for writing

print >> f, "Hello there from Python!"

x = 42

print >> f, x, "is the number of tiles in a game of scrabble."

f.close() # this closes the file f - a good idea

Running writeToFile('myfile.txt') produces no visible output, but when you open the file myfile.txt, you'll see what was printed:

Hello there from Python!

42 is the number of tiles in a game of scrabble.

Handling large recursive calls

If you run scoreFile on files with more than 1,000 characters, it may use more memory than Python allocates to the recursive stack (and crash). To get around this, you can add the following lines at the top of your hw1pr5.py file:

import sys

sys.setrecursionlimit(100000)

These lines allow Python to build a stack of up to 100,000 function calls -- or until the memory your operating system has given Python runs out. Usually the latter happens first, leading to IDLE hanging or crashing or producing the rather uninformative segmentation fault error. However, you should at least be able to get well past 1,000 characters.

Testing this problem

In addition to writing the above scoreFile function -- which should be in a file named hw1ec2.py, you should also run it on something other than the two examples above: at least one additional file you wrote (perhaps a hum paper) and another file of your choosing. Don't use Microsoft Word-formatted files - they and other word-processed files have lots of formatting characters in them. Instead, use plain-text files. Microsoft Word will reluctantly allow you to save existing files to plain-text, though it will warn you with several dialog boxes of the extreme risks you take by not using a Microsoft file format!

In a comment at the top of your hw1ec2.py file, report the results from the two files you chose.

Happy scrabbling!

Submitting your file

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

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

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

Google Online Preview   Download