CSC148H - Assignment 2
Preamble
Part 3 of this assignment was slightly modified on October 30. See bulletin board for more information.
This assignment is due 9 November 2009 at 10:00am.
No late assignments will be accepted.
Solutions should be clearly written, well documented, and conform to the PEP 8 style guide.
To submit the assignment, log in to the Mark Us webpage. You should be able to submit the required files. Your user name and password is the same as the CDF user name and password. Make sure you can log in as soon as possible, especially if you were late to enroll in the course. You may submit files as often as you like; the most recent version (submitted before Nov. 9, 10:00am) will be the one graded. Frequent submissions are encouraged.
For all questions, you are allowed to write helper methods to help your solution. Remember that any new methods you write should be appropriately named and documented.
Part 1 (30%)
The determinant of a square matrix A = [ai,j] (for 0 <= i, j < n-1) can be defined recursively as follows:
where A-(i,j) is the (n - 1) x (n - 1) matrix created by removing row i and column j from the matrix A.
Now there are many better methods of calculating the determinant than using this formula (for example, Gaussian Elimination). We are going to look at calculating a different, yet similiar value called the permanent.
Using the same notation defined above, the permanent of a square matrix A is defined to be:
We say that the permanant of a 1 x 1 matrix is simply a0,0 (the single element it contains).
Complete the method permanent in part1.py to calculate the permanent using the recursive definition stated above. The input to your method matrix will be a list representation of a matrix, where each element of matrix corresponds to a row (given in order).
For example,
print permanent([[5,3],[2,1]]) # Should print 11 (5*1 + 3*2)
print permanent([[1,2,3],[4,5,6],[7,8,9]]) # Should print 450 (1*(5*9 + 6*8) + 2*(4*9 + 6*7) + 3*(4*8 + 5*7))
print permanent([[1,1,1],[1,1,1],[1,1,1]]) # Should print 6 (which, by no coincidence, is 3!)
Part 2 (30%)
For this part, you will fill in the code for the method blob_removal.
Consider a grid where each element is either a . (denoting a free space) or a # (denoting an occupied space). Two #s are said to be in the same blob if there is a path between them moving only up, down, left or right which only uses other # squares. Look at the following example of a grid:
.#.##
.....
#####
#...#
#.#.#
#...#
#####
In this grid there are 4 blobs. Here they are labeled with uppercase letters:
.A.BB
.....
CCCCC
C...C
C.D.C
C...C
CCCCC
You are to fill in the code for the method blob_removal(grid, row, col) in part2.py which takes grid is a list of lists representing the grid; elements of grid are the rows (in order) and each element of a row is either '.' or '#'. If grid[row][col] is a '#' (making it part of a blob), the method should replace each element of the blob with a '.'.
For your convenience, two methods have been provided to read a grid from a file and print it to the screen. A sample grid file is given here. Here is an example of how your method should work. When the following code is run:
grid = load_grid('./grid.in')
draw_grid(grid)
print
remove_blob(grid, 0, 1)
draw_grid(grid)
print
remove_blob(grid, 2, 4)
draw_grid(grid)
print
remove_blob(grid, 0, 4)
draw_grid(grid)
print
remove_blob(grid, 3, 3)
draw_grid(grid)
print
This should produce the following output:
.#.##
.....
#####
#...#
#.#.#
#...#
#####
...##
.....
#####
#...#
#.#.#
#...#
#####
...##
.....
.....
.....
..#..
.....
.....
.....
.....
.....
.....
..#..
.....
.....
.....
.....
.....
.....
..#..
.....
.....
Your solution should be recursive.
Part 3 (40%)
For this part, you will implement some of the functionality of a list using a binary tree.
The start code part3.py contains the basic definition of a binary tree, with one exception; the Node class contains an additional attribute size which stores how many nodes are in the subtree rooted at that node. Part of this assignment will require you to maintain this value.
There are three methods you are required to fill in.
get(self, index) should return element index of the list, and should raise an appropriate exception if index exceeds the number of elements in the list, or is less than zero.
insert(self, index, value) should insert value at position index, or raise an exception if the index given is invalid (beyond the end of / before the beginning of the list). This should always create a new leaf node in the tree.
size(self) should return how many elements are in the list.
The list is implicitly defined by the in-order traversal of this tree. For example, my_list.get(0) should return the first element output in an in-order traversal, my_list.get(1) the second, etc. Likewise, my_list.insert(4, value) should insert a new leaf into the tree which will be visited 5th in an in-order traversal. The runtime of both insert and get should both be O(height of the tree). The runtime of size should be O(1).
For example:
my_list = TreeList()
my_list.insert(0, 1)
my_list.insert(1, 2) # The "list" is now [1,2]
print my_list.get(1) # Should print 2
my_list.insert(1, 3) # The "list" is now [1,3,2]
print my_list.get(1) # Should print 3
try:
my_list.insert(4, 7) # Should raise an exception, my_list should be unchanged.
except Exception, e:
print 'Exception handled.'
print my_list.get(1) # Should print 3
Updated October 30: Two new methods have been added to TreeList; get_root and set_root. These return and set the root of the tree (respectively). The purpose of this is to make it easier to test partial solutions; the get(index) method is significantly easier to implement than insert(index, value). get_root and set_root will be used to test your get(index) method correctly built trees that we have constructed. As a result of this, you should not add any new attributes to TreeList or Node; if you add them to TreeList, keep in mind they may not be correctly set when the root node is replaced, and if you add them to Node, the new_root we give your TreeList will not have them set.
What to Submit
For Part 1: part1.py
For Part 2: part2.py
For Part 3: part3.py
Note that although you are not required to submit tests for your code, you should test them; much of the marking will be done by automatically running your code on a variety of test cases. You are free to write and submit additional files with your solution. Make sure you submit all files required to run your solution.
Log in to Mark Us with your CDF username and password. Everything must be submitted by Nov. 9, 10am. No late assignments will be accepted.