Solution to Data Structures

1. There are many solutions to this problem. One that works is storing the elements of the matrix in a triple structure with slots for row, column and value. The matrix itself will be a list of these triples. The first element of the list will always be a pair which stores the size of the matrix. Further, this new implementation will require that the list of matrix elements be ordered by their position in the matrix.  Thus this implementation makes it possible to define new generic functions for equals?, <, and >. These generic functions will return booleans based on position in the matrix, rather than the value.
   
   

2. 
   (define (sparse-add (A <list>) (B <list>))
     (if (equal? (head A) (head B))
         (letrec ((iter (lambda (A B)
                    (cond ((empty? A) B)
   	               ((empty? B) A)
   		       ((equals? (head A) (head B))
   		         (cons (make-elem (elem-row (head A))
   					  (elem-col (head A))
   					  (+ (elem-val (head A))
   					     (elem-val (head B))))
   			       (iter (tail A) (tail B))))
   		       ((< A B) (cons (head A)
   				      (iter (tail A) B)))
   		       (else (cons (head B)
   				   (iter A (tail B))))))))
   	(cons (head A) (iter (tail A) (tail B))))
         (error "Matrices not the same size")))

Question

Return to CS 212 Prelim 2 - Spring 1998