first part

# Implementation of the Sparse Matrix ADT using an array of linked lists.

from array import Array

class SparseMatrix : # Creates a sparse matrix of size numRows x numCols initialized to 0.

def __init__( self, numRows, numCols ): self._numCols = numCols self._listOfRows = Array( numRows ) self._listOfRows.clear( None ) # Just to ensure we have null head references

 # Returns the number of rows in 

def numRows( self ): return len( self._listOfRows )

 # Returns the number of columns 

def numCols( self ): return self._numCols

the matrix.

in the matrix. 

 # Returns the value of element (i,j): x[i,j] 

def __getitem__( self, ndxTuple ): ......

# Sets the value of element (i,j) to the value s: x[i,j] = s

def __setitem__( self, ndxTuple, value ):

row, col = ndxTuple # Grab the row and column indices

predNode = None curNode = self._listOfRows[row] # Start with the head reference

while curNode is not None and curNode.col != col : predNode = curNode curNode = curNode.next

 # See if the element is in the list. 

if curNode is not None and curNode.col == col : # The second part is unnecessary if value == 0.0 : # remove the node.

if curNode == self._listOfRows[row] : # Special case for head reference self._listOfRows[row] = curNode.next # Head reference for the current row

else : predNode.next = curNode.next

else : # change the node's value. curNode.value = value

# Otherwise, the value is not in the sparse matrix. So we will have to add it

elif value != 0.0 : # Create a new node and add it to the appropriate row newNode = _MatrixElementNode( col, value ) newNode.next == curNode if curNode == self._listOfRows[row] : # if self._listOfRows[row] == None:

self._listOfRows[row] = newNode # Special case for head else :

predNode.next = newnode # Append new node to the end on the current row

# Scales the matrix by the given scalar. 

def scaleBy( self, scalar ):

for row in range( self.numRows() ) :

curNode = self._listOfRows[row] # Start with the head reference of the current row while curNode is not None :

 curNode.value *= scalar curNode = curNode.next 

# Creates and returns a new matrix that is the transpose of this matrix.

def transpose( self ): ......

 # Matrix addition: newMatrix = self + rhsMatrix. 

def __add__( self, rhsMartrix ) : # Make sure the two matrices have the correct size.

assert rhsMatrix.numRows() == self.numRows() and \ rhsMatrix.numCols() == self.numCols(), \ "Matrix sizes not compatable for adding."

 # Create a new sparse matrix of the same size. 

newMatrix = SparseMatrix( self.numRows(), self.numCols() )

for row in range( self.numRows() ) :

curNode = self._listOfRows[row]

while curNode is not None :

newMatrix[row, curNode.col] = curNode.value curNode = curNode.next 

for row in range( rhsMatrix.numRows() ) :

curNode = rhsMatrix._listOfRows[row]

while curNode is not None :

value = newMatrix[row, curNode.col] value += curNode.value newMatrix[row, curNode.col] = value curNode = curNode.next 

# Return the new matrix. 

return newMatrix

class _MatrixElementNode : def __init__( self, col, value ) :

 self.col = col self.value = value self.next = None 

second part

# Implementation of the Polynomial ADT using a sorted linked list.

class Polynomial : # Create a new polynomial object.

def __init__(self, degree = None, coefficient = None): if degree is None :

self._polyHead = None else :

self._polyHead = _PolyTermNode(degree, coefficient) self._polyTail = self._polyHead

 # Return the degree of the polynomial. 

def degree( self ): if self._polyHead is None :

return -1 # Returning None may be the better choice else :

return self._polyHead.degree # Assuming first node will be the one with highest degree

# Return the coefficient for the term of the given degree.

def __getitem__( self, degree ): assert self.degree() >= 0,

 "Operation not permitted on an empty polynomial." 

curNode = self._polyHead while curNode is not None and curNode.degree >= degree

if curNode is None or return curNode.degree != degree :

return 0.0

else :

return curNode.coefficient

# Evaluate the polynomial at the given scalar value. 

def evaluate( self, scalar ): assert self.degree() >= 0,

"Only non-empty polynomials can be evaluated." result = 0.0;

curNode = self._polyHead while curNode is not None :

result += curNode.coefficient * (scalar ** curNode.degree)

curNode = curNode.next return result

# Polynomial addition: newPoly = self + rhsPoly. 

def __add__( self, rhsPoly ):

# Polynomial subtraction: newPoly = self - rhsPoly. def __sub__( self, rhsPoly ):

......

 # Polynomial multiplication: newPoly = self * rhsPoly. 

def __mul__( self, rhsPoly ):

def _appendTerm( self, degree, coefficient ) : if coefficient != 0.0 :

 newTerm = _PolyTermNode( degree, coefficient ) 

if self._polyHead is None : self._polyHead = newTerm

else : self._polyTail.next = newTerm

self._polyTail = newTerm 

# Class for creating polynomial term nodes used with the linked list.

class _PolyTermNode( object ): def __init__( self, degree, coefficient ):

 self.coefficient = coefficient self.degree = degree self.next = None 

Test and complete the implementation of the SparseMatrix class in Listing 6.11 on page 176 in your book. Also see Exercise 6.5, and add your answers to these questions below. Your demonstration must also include the iterator for the SparseMatrix class! You will have to implement this on your own. The iterator for this class must return 2-tuples, where the first value must a 2-tuple with the (row, column) indices of the value in question. The second value in the top 2-tuple must be the value at that (row, column) in the sparse matrix. For example, the value ((2, 2), 9) means that value 9 is at cell (2, 2) in the sparse matrix. Demonstrate with enough number of examples that the class behaves as expected with all its APIs. Question 9 Test and complete the implementation of the Polynomial class in Listing 6.11 on page 183 in your book. You will need to refer to subsequent code listings for some of the methods. Your demonstration must also include the iterator for the Polynomial class! You will have to implement this on your own. The iterator for this class must return a _PolyTermNode. Think of adding ___str_() and repr_ methods to the _PolyTermNode so that you can easily display its content. Demonstrate with enough number of examples that the class behaves as expected with all its APIs. Also solve PROGRAMMING PROJECT 6.5 as part of this