|
CSE 326 - Winter 2004 |
|
 CSE Home |
About Us |
Search |
Contact Info |
by Chris Baker (former TA)
This page provides the Matlab scripts we used to generate the test files . Use these to create new test cases or to learn how to use Matlab, or just to understand the assignment better.
The cool thing about Matlab is that the language is fairly close to pseudocode, so even if you don't know the language, just reading the code might help you understand the problem. The bad thing about Matlab is that unlike Java or C++, it isn't designed to be object oriented and it's harder to encapsulate functionality and use good programming practices.
Because of this, it would be very difficult to program an actual sparse matrix "class" in Matlab. Luckily, Matlab provides sparse matrices natively. I was curious whether operations such as addition or scaling on these sparse matrices have the same complexity as the sparse matrices that you will be implementing. In the graphs below, I plotted the complexity of scaling and adding Matlab sparse matrices as a function of the number of elements. As you can see, adding two matrices is approximately linear in the sum of the number of elements in each, and scaling is also linear in the number of elements. Note that you are required to implement scaling in constant time. Why do you think the Matlab designers chose to implement scaling of sparse matrices this way? What are the tradeoffs involved?
 |
Figure 1: Complexity of A + B as a function of numItems A + numItems B. The red line is the line of best fit for the data. |
 |
Figure 2: Complexity of const * A as a function of numItems A. The red line is the line of best fit for the data. |
 |
Figure 3: Complexity of A * C as a function of numItems A + numItems C. Here, there is no line of best fit because the complexity is not a simple expression of the size of matrices A and C. |
How see how the test files we provide were generated, read run_createPlots.m in the Matlab files section. The format of the test files is simple and explained in the assignment description.
 |
Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX |