PC204 Logo

PC-204 – Introduction to
Object-Oriented Computer Programming

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

For your test data, use the PDB file from http://www.rcsb.org/pdb/download/downloadFile.do?fileFormat=pdb&compression=NO&structureId=3FX2.

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)
data = f.read()
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)
data = f.read()
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.

  1. Download the following files:
    • 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.