# PC204 Homework Assignments

Week 1 - Intro to Python, Functions
Assignment 1.1
Compute the volume of a sphere with a radius of 5. The formula for a sphere is 43πr3. Note: The answer is around 500, not 400.

Write a function `sphere_volume` that returns the volume of a sphere when given radius `r` as a parameter. Print the volume of a sphere with a radius of 5. Note: Your code for `sphere_volume` should not include a `print` statement. The caller should be printing the return value from `sphere_volume`.

Assignment 1.2
Write three functions that calculate the remainder of two integers by using:
• the basic operators of +, -, * and / (why is // not required?)
• the `divmod` function
• the % operator

Each function should take two parameters, `dividend` and `divisor`, and return the remainder. We should be able to use these functions interchangeably since passing the same parameters to each should result in the same answer. Assume that both parameters are integers.

Week 2 - Conditional Expressions, Recursive Functions
Assignment 2.1
Write a recursive function `print_range` that prints the range of numbers from `start` to `end`, where `start` and `end` are integer parameters to the function. Your code should work whether `start` is larger or smaller than `end`.

Write a test program that uses `raw_input` to ask the user to enter the starting and ending numbers and call `print_range` with those arguments.

Assignment 2.2
Exercise 6.8 from Think Python.

The greatest common divisor (GCD) of a and b is the largest number that divides both of them with no remainder.

One way to find the GCD of two numbers is Euclid's algorithm, which is based on the observation that if r is the remainder when a is divided by b, then gcd(a, b) = gcd(b, r). As a base case, we can use gcd(a, 0) = a.

Write a recursive function called `gcd` that takes parameters `a` and `b` and returns their greatest common divisor. You can assume that both `a` and `b` are positive integers. Make sure your code is written such that `gcd(a, b) == gcd(b, a)`. Of course also include test code that calls your gcd function to demonstrate that the results are correct. If you need help with the algorithm, see http://en.wikipedia.org/wiki/Euclidean_algorithm.

Credit: This exercise is based on an example from Abelson and Sussman's “Structure and Interpretation of Computer Programs”.

Week 3 - Iteration, Strings, File I/O
Assignment 3.1
Exercise 7.2 and 7.3 from Think Python.

Here is a loop that starts with an initial estimate of the square root of `a`, `x`, and improves it until it stops changing:

```while True:
y = (x + a / x) / 2
if abs(y - x) < epsilon:
break
x = y
```

where `epsilon` has a value like 0.0000001 that determines how close is close enough.

Encapsulate this loop in a function called `square_root` that takes `a` as a parameter, chooses a reasonable value of `x`, and returns an estimate of the square root of `a`.

To test the square root algorithm in this chapter, you could compare it with `math.sqrt`. Write a function named `test_square_root` that prints a table like this:

```1.0 1.0 1.0 0.0
2.0 1.41421356237 1.41421356237 2.22044604925e-16
3.0 1.73205080757 1.73205080757 0.0
4.0 2.0 2.0 0.0
5.0 2.2360679775 2.2360679775 0.0
6.0 2.44948974278 2.44948974278 0.0
7.0 2.64575131106 2.64575131106 0.0
8.0 2.82842712475 2.82842712475 4.4408920985e-16
9.0 3.0 3.0 0.0
```

The first column is a number, a; the second column is the square root of a computed with the [your function]; the third column is the square root computed by `math.sqrt`; the fourth column is the absolute value of the difference between the two estimates.

Assignment 3.2
Read a Protein Data Bank (PDB) file and compute the center of atoms by averaging the coordinates from all `ATOM` records. A PDB consists of lines (records) that start with the record type, such as `HEADER`, `REMARK` and `ATOM`, followed by data associated with the record. An `ATOM` record looks like:
```ATOM      4  O   ALA A   1      43.328  45.046 -13.879  1.00 54.88           O
```

If we number columns starting from 1, then the x, y and z coordinates of the atom are in columns 31-38, 39-46 and 47-54, respectively. In the example above, the coordinates are (43.328, 45.046, -13.879). Write a function `average_coord`, which takes the name of a file as its only parameter, that:

1. opens the file
2. reads through all records to compute and print the number of `ATOM` records and their average coordinates
3. (To clarify, the output should have exactly four numbers: the number of `ATOM` records processed, the average x coordinate for all `ATOM` records, the average y coordinate for all `ATOM` records, and the average z coordinate for all `ATOM` records, i.e., the output is not the average of the x, y and z coordinates for each `ATOM` record.)
4. closes the file

When retrieving the coordinate values, do not use the `split` method to split up the line because that does not work for all PDB files.

Week 4 - Data Structures: List, Dictionaries, Tuples, and Sets
Assignment 4.1
Write two versions of a function that, given a simple list of objects (e.g., integers or strings) as a parameter, checks whether there are duplicate elements in the list and return True of False accordingly. The input list should not be changed.

The first version of the function, `has_dups`, may use any data structure (lists, dictionaries, sets), while the second version, `has_dups_list`, may not use either dictionaries or sets. Test your functions using both lists with and without duplicates.

Use the following timing function to check which version runs faster:

```def timing(func, argument, repeat=1000):
import time
total = 0.0
for i in range(repeat):
start = time.time()
func(argument)
total += time.time() - start
print "Average time (ms):", total / repeat * 1000.0
timing(has_dups, test_list)
timing(has_dups_list, test_list)
```

You should use a variety of test lists. For example, how do these test data differ in run time for the two functions:

```test_list = list(range(1000))
test_list = list(range(1000)) ; test_list[-1] = test_list[500]
test_list = list(range(1000)) ; test_list[1] = test_list[0]
```
Assignment 4.2
Exercise 12.6 from Think Python.

Here's another Car Talk Puzzler (http://www.cartalk.com/content/puzzlers):

"What is the longest English word, that remains a valid English word, as you remove its letters one at a time?

"Now, letters can be removed from either end, or the middle, but you can't rearrange any of the letters. Every time you drop a letter, you wind up with another English word. If you do that, you're eventually going to wind up with one letter and that too is going to be an English word - one that's found in the dictionary. I want to know what's the longest word and how many letters does it have?

"I'm going to give you a little modest example: Sprite. Ok? You start off with sprite, you take a letter off, one from the interior of the word, take the r away, and we're left with the word spite, then we take the e off the end, we're left with spit, we take the s off, we're left with pit, it, and I."

Write a program to find all words that can be reduced in this way, and then find the longest one. This exercise is a little more challenging than most, so here are some suggestions:

1. You might want to write a function that takes a word and computes a list of all the words that can be formed by removing one letter. These are the “children” of the word.
2. Recursively, a word is reducible if any of its children are reducible. As a base case, you can consider the empty string reducible.
3. The wordlist I provided, words.txt, doesn't contain single letter words. So you might want to add “I”, “a”, and possibly the empty string.
4. To improve the performance of your program, you might want to memoize the words that are known to be reducible.
Bonus Exercise
Challenge #1: The Case of the Watermarked Bacteria
Week 5 - More About Files, Intro to Modules
Assignment 5.1
Read the documentation on the "os.walk" function at http://docs.python.org/2/library/os.html#os.walk. It is a more flexible version of `walk` than the code in Chapter 14 of Think Python. Write a function, `count_extensions`, that traverses a given directory and subdirectories and counts the number of files of each suffix type, e.g., `.py`, `.pyc`, `.txt`, etc.

The documentation for splitting a filename into a base name and an extension may be found at http://docs.python.org/2/library/os.path.html#os.path.splitext.

Assignment 5.2
Many web services on the Internet return data in eXtenisble Markup Language (XML) format. For example, the Protein Data Bank (PDB) supports a wide variety of queries, including the list of current PDB entries, the descriptions of the entities that are contained in a PDB file, or ligands found in a particular PDB entry. To retrieve data from the PDB programmatically, we need to construct the proper URL, send the web query, and decode the returned results.

Write a function, `get_pdb_ligands`, which takes a PDB code as parameter and returns a list of the ligands found in the entry. The URL for this query has the form:

```http://www.rcsb.org/pdb/rest/ligandInfo?structureId=4HHB
```

In this example, `4HHB` is the 4-letter code for a PDB entry of a “crystal structure of human deoxyhaemoglobin”. The returned results from this query is in XML format and looks like:

```<?xml version="1.0" encoding="windows-1252" standalone="no"?>
<structureId id="4HHB">
<ligandInfo>
<ligand structureId="4HHB" chemicalID="HEM" type="non-polymer" molecularWeight="616.487">
<chemicalName>PROTOPORPHYRIN IX CONTAINING FE</chemicalName>
<formula>C34 H32 FE N4 O4</formula>
<InChIKey>FEDYMSUPMFCVOD-UJJXFSCMSA-N</InChIKey>
<InChI>InChI=1S/C34H34N4O4/c1-7-21-17(3)25-13-26-19(5)23(9-11-33(39)40)31(37-26)16-32-24(10-12-34(41)42)20(6)28(38-32)15-30-22(8-2)18(4)27(36-30)14-29(21)35-25/h7-8,13-16,36-37H,1-2,9-12H2,3-6H3,(H,39,40)(H,41,42)/b25-13-,26-13-,27-14-,28-15-,29-14-,30-15-,31-16-,32-16-</InChI>
<smiles>Cc1c2/cc/3\nc(/cc\4/c(c(/c(/[nH]4)c/c5n/c(c\c(c1CCC(=O)O)[nH]2)/C(=C5C)CCC(=O)O)C=C)C)C(=C3C)C=C</smiles>
</ligand>
<ligand structureId="4HHB" chemicalID="PO4" type="non-polymer" molecularWeight="94.971">
<chemicalName>PHOSPHATE ION</chemicalName>
<formula>O4 P -3</formula>
<InChIKey>NBIIXXVUZAFLBC-UHFFFAOYSA-K</InChIKey>
<InChI>InChI=1S/H3O4P/c1-5(2,3)4/h(H3,1,2,3,4)/p-3</InChI>
<smiles>[O-]P(=O)([O-])[O-]</smiles>
</ligand>
</ligandInfo>
</structureId>
```

The data of interest are the text that appear betweeen the `<chemicalName>` and `</chemicalName>` tags. Normally, the XML results are processed using Python packages such as `minidom`; for this exercise, assume that the tags and data will appear on a single line and use string operations to extract the information.

To retrieve data from an URL, use the `urllib` module (Python 2: http://docs.python.org/2/library/urllib.html, Python 3: http://docs.python.org/3/library/urllib.html). The following example will retrieve and print data from an URL.

```# Python 2
import urllib
f = urllib.urlopen(url)
for line in f:
print line
f.close()

# Python 3
import urllib.request
f = urllib.request.urlopen(url)
for line in f:
print line
f.close()
```

For testing, the input parameter for `get_pdb_ligands` should be the string `"4HHB"` and the return value should be a list of two strings: `"PROTOPORPHYRIN IX CONTAINING FE"` and `"PHOSPHATE ION"`.

(If you are ambitious, try using `minidom` to extract the data. Your code may look something like:

```# Python 2
import urllib, xml.dom.minidom
f = urllib.urlopen(url)
f.close()
dom = xml.dom.minidom.parseString(data)
[... your code for processing the dom goes here ...]

# Python 3
import urllib.request, xml.dom.minidom
f = urllib.request.urlopen(url)
f.close()
# "data" is in "bytes" but xml.dom understands both bytes
# and strings so we can use "data" directly without decoding
dom = xml.dom.minidom.parseString(data)
[... your code for processing the dom goes here ...]
```

The example towards the end of `minidom` documentation, Python 2: http://docs.python.org/2/library/xml.dom.minidom.html, Python 3: http://docs.python.org/3/library/xml.dom.minidom.html, should help.)

Week 6 - Exceptions, Modules, Intro to Object-Oriented Programming
Assignment 6.1
Using the same class definition for Rectangle as found in Chapter 15 of Think Python, write the following four functions:
`create_rectangle`
Input parameters: `x`, `y`, `width`, `height`
Return value: instance of Rectangle
Operation: create a new instance of Rectangle
`str_rectangle`
Input parameter: `rect`
Return value: string
Operation: convert given Rectangle instance into string of form `(x, y, width, height)`
`shift_rectangle`
Input parameters: `rect`, `dx`, `dy`
Return value: None
Operation: change the x and y coordinates of the given Rectangle instance
`offset_rectangle`
Input parameters: `rect`, `dx`, `dy`
Return value: instance of Rectangle
Operation: create a new Rectangle instance which is offset from the given instance in x and y coordinates by `dx` and `dy` respectively

Test your functions with the following code:

```r1 = create_rectangle(10, 20, 30, 40)
print str_rectangle(r1)
shift_rectangle(r1, -10, -20)
print str_rectangle(r1)
r2 = offset_rectangle(r1, 100, 100)
print str_rectangle(r1)		# should be same as previous
print str_rectangle(r2)
```
Assignment 6.2
Write a function, `area_difference`, that takes two Rectangle instances as parameters and returns the signed difference in area between them. "signed difference" means that rather than always returning a positive number, the sign of the return value should be negative if the first rectangle is smaller. Test your code with:
```r1 = create_rectangle(10, 20, 10, 10)
r2 = create_rectangle(20, 50, 15, 20)
print area_difference(r1, r2)
```
Week 7 - OOP: Classes and Methods
Assignment 7.1
Write the functions from Assignment 6.1 as methods of the Rectangle class. `create_rectangle` becomes `__init__`; `str_rectangle` becomes `__str__`; `shift_rectangle` and `offset_rectangle` are renamed as `shift` and `offset`, respectively, and become methods of the class (so that the `rect` argument to the functions become the `self` argument to the method).

Test your new class with the following code:

```r1 = Rectangle(10, 20, 30, 40)
print r1
r1.shift(-10, -20)
print r1
r2 = r1.offset(100, 100)
print r1
print r2
```
Assignment 7.2
Write an `__add__` method for the rectangle class that returns the `sum` of two rectangles as a new rectangle which is the smallest rectangle that encloses the two input rectangles. Test your code with:
```r1 = Rectangle(10, 20, 10, 10)
r2 = Rectangle(20, 50, 15, 20)
print r1 + r2
```

The answer should be `(10, 20, 25, 50)`.

Week 8 - OOP: Inheritance
Assignment 8.1
Exercise 18.6 from Think Python.

The following are the possible hands in poker, in increasing order of value (and decreasing order of probability):

• pair: two cards with the same rank
• two pair: two pairs of cards with the same rank
• three of a kind: three cards with the same rank
• straight: five cards with ranks in sequence (aces can be high or low, so Ace-2-3-4-5 is straight and so is 10-Jack-Queen-King-Ace, but Queen-King-Ace-2-3 is not.)
• flush: five cards with the same suit
• full house: three cards with one rank, two cards with another
• four of a kind: four cards with the same rank
• straight flush: five cards in sequence (as defined above) and with the same suit

The goal of these exercises is to estimate the probability of drawing these various hands.

• Card.py: A complete version of the `Card`, `Deck` and `Hand` classes in this chapter.
• PokerHand.py: An incomplete implementation of a class that represents a poker hand, and some code that tests it.
2. If you run `PokerHand.py`, it deals seven 7-card poker hands and checks to see if any of them contains a flush. Read this code carefully before you go on.
3. Add methods to `PokerHand.py` named `has_pair`, `has_twopair`, etc. that return `True` or `False` according to whether or not the hand meets the relevant criteria. Your code should work correctly for “hands” that contain any number of cards (although 5 and 7 are the most common sizes).
4. Write a method named `classify` that figures out the highest-value classification for a hand and sets the `label` attribute accordingly. For example, a 7-card hand might contain a flush and a pair; it should be labeled “flush”.
Assignment 8.2
Write a short paragraph of what you plan to do for your project.
Bonus Exercise
Challenge #2: Six Degrees of Separation
Week 9 - Tkinter
Assignment 9.1
Write a two-player “gomoku” program (http://en.wikipedia.org/wiki/Gomoku):

Gomoku is an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with Go pieces (black and white stones) on a go board with 19x19 intersections; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil game. This game is known in several countries under different names.

Black plays first, and players alternate in placing a stone of their color on an empty intersection. The winner is the first player to get an unbroken row of five stones horizontally, vertically, or diagonally.

Your program should display the gomoku board and let players alternately select empty intersections by clicking on the canvas. Each click should result in a stone being placed on the board. The program should detect when a player wins and ask whether to start a new game.

For your implementation, use a Tkinter `Canvas` to display the board. For this exercise, specify the width and height of the canvas so that you can easily compute the coordinates for the board lines and stones; for example, using a 380x380 canvas for a 19x19 board would greatly simplify the convertion from pixels to row and column indices. The lines of the board may be drawn using `create_line` and the stones using `create_oval` while specifying the `fill` attribute for the color of the stones. To handle user interactions, you will need to `bind` an event handler to the canvas instance to get mouse clicks. The event instance that your handler receives as its argument will have `x` and `y` attributes for the position of the mouse click; these attribute units are in pixels, so you will need to convert them into board row and column indices.

For more information on how to use the Tkinter, see An Introduction to Tkinter (Work in Progress) by Fredrik Lundh.

(If you are ambitious, write your program so that the canvas may be resized. You will need to bind to `Configure` events to receive notification when the canvas changes size, and your board-to-pixel conversion factors will need to be updated each time the board size changes.)

Assignment 9.2
Write a description for your final project, including inputs, outputs, operations, what classes you plan to use, etc.