IntroductionWe are now fast-forwarding in time several steps after you presented your designs from phase 1 to the client. A few iterations of tweaking and discussion have repeated, and we now have a much better idea of the ADT that we need to implement. You may notice that some things have been added, and some taken away, this is normal for a project like this (and shows why its a good idea to settle on a design before you spend large chunks of time developing the actual code). The ADT is almost nalized, and now we can start to work on the implementation.
The ADTThe starter code provided in a1.py represents an almost complete ADT. The class hier-archy is settled, and all of the methods have been outlined, at least at their highest level. Weve decided which exception types we need, but not exactly when and where they should be raised, and we havent gured out yet which methods will need to be over-ridden in children classes. These final elements of the design should be your first task.
Implementation
Once were ready to implement the actual Matrix class and its sub-classes, we need to think about a sensible data structure that we can use. Obviously we could simply have lists of lists, but this seems impractical. What if the client wants to create a 1000 x 1000 matrix, but only cares about 1 or 2 values. Wed be using up millions of times more space than we actually need. Fortunately, weve learned about linked lists in lecture. Maybe they can help us.
Linked Data Structure
Suppose we have the matrix:[email protected]A D GB E HC F I1CCA
Each element can be held in a node like in a linked list, with A pointing to B, etc.This would be ne if all we cared about were the columns, but sometimes were going to need to deal with rows, so maybe each node could have a link to the node, beside it as well (i.e, A could also link to D). We could create a linked data structure, that can hold a matrix of elements, like so:ABCDEFGHI
This is a nice start, but doesnt help us with our initial problem of saving space, since every node has to be created for us to be able to gure out where we are in the matrix. If we didnt have a D node, we wouldnt know if the item to the right of A was supposed to be in column 1 or 2 or 20. So lets add a set of index nodes that tell us the index of each row or column. Since we want to have a single point of entry into the data structure, well also add an extra node with no data, but that can be used as the head of the structure.
None0120ABC1DEF2GHI2So now lets see what happens when we dont have all the nodes. Lets say that our matrix is all 0s, except for A, G and F.
[email protected]A 0 G0 0 00 F 01CCA
We could create the matrix like this:None020A1F2GNotice now that we only need to create nodes for the data that actually exists in our matrix. Any node that doesnt exist, we know must have a value of 0 (or whatever other default value we want to ascribe).Make sure you fully understand this data structure before moving on.Try drawing out what it would look like with dierent matrices).
Your Task
Your task is to complete the code in a1.py using the linked data structure described above.In particular, you may not use any other Python data structure (e.g., lists, dictionaries)in completing your code. You may add other methods if you wish, but you must at least implement the ADT as provided in the starter code.
Hints & TipsPlan everything before you write anythingDraw lots of picturesThink about boundary cases (inserting at the beginning/end of a row/col, emptymatrices, etc)If youre stuck, you can go with the simpler approach of just creating every node,even those with default values, this wont get you full marks, but its better thannot having any of your code workRemember that this must be 100% your own work. You may ask for clarication on Piazza, but you should not discuss this assignment with your classmates, or look for help elsewhere{ If you dont understand something about the matrix mathematics, ask me, andIll explain it or post a tutorial on Piazza (I dont want to test your linear algebra
Reviews
There are no reviews yet.