### Assignment 1: Vector and Matrix

**Submission Deadline: Friday, November 23 2018, at noon**

In this assignment you are asked to implement your own Vector and Matrix types in Python and to compare them with Numpy array type implementations.

In your git repository you will find the following spec files that you
will need to edit `vec.py`

and `mat.py`

. In addition, you will find the
file `banchmark.py`

that will use your implementations to carry out the
comparison with NumPy.

The files `vec-sparse.py`

and `mat-sparse.py`

are for an optional part
of the assignment. For implementing the methods in these files you will
get help by the instructors in Computer Lab class of week 47.

Your job is to implement the appropriate methods for the classes `Vec`

and `Mat`

such that the functions in the doctest examples and those in
`benchmark.py`

that use the operators with objects from those classes
work correctly. To facilitate your task the procedures that you have to
finish implementing have been moved out of the class where they are
called. Hence you should make no changes to the class definition. Your
code for a procedure can include calls to other procedures.

The table below resumes the functions that are used for the different operators:

operation | syntax | function |
---|---|---|

vector addition | u+v | `__add__` |

vector negation | -v | `__neg__` |

vector subtraction | u-v | |

scalar-vector multiplication | alpha*v | `__rmult__` |

division of a vector by a scalar | v/alpha | `__truediv__` |

dot-product | u*v | `__mult__` |

getting value of an entry | v[d] | `__getitem__` |

setting value of an entry | v[d] = . | `__setitem__` |

testing vector equality | u == v | `__eq__` |

pretty-printing a vector | print(v) | `__str__` |

copying a vector | v.copy() | `copy` |

You can test if your modules pass all their `doctests`

from a console,
by typing

```
python3 -m doctest vec.py
```

or

```
python3 vec.py
```

To benchmark your implementations against those from Numpy you can call:

```
python3 benchmark.py
```

You can play around with the size of the matrices to observe the growing rate of computation time but you should otherwise not edit this file. This file will be updated when we deal with the sparse matrix part.

Your code will be graded on another set of tests that will be unveiled during grading.

*Assertions*: For most of the procedures to be written, the first
statement after the docstring is an assertion. Executing an assertion
verifies that the condition is true, and raises an error if not. The
assertions are there to detect errors in the use of the procedures. Take
a look at the assertions to make sure you understand them. You can take
them out, but you do so at your own risk.

#### Sparse Vectors and Matrices (Optional)

This part will be discussed in class in one of the Computer Lab. It is
associated with the files `vec_sparse.py`

and `mat_sparse.py`

.

A vector (matrix) most of whose values are zeros is called a *sparse
vector (matrix)*.

*Sparse representation*:
To represent sparse vectors and matrices in Euclidean spaces, it might be useful to regard
them as functions from a domain $D$ to a co-domain $\mathbb{B}$. For
example the vector
$
[3.14159, 2.718281828, −1.0, 2.0]
$
can be represented as the function:

For a matrix the domain $D$ is made by the product of a domain $R$ for the rows and a domain $C$ for the columns. For example, the identity matrix of size $3\times 3$ can be seen as the function that maps the pairs $(r,c)\in R\times C$ where $R=C=\{1,2,3\}$.

All other elements of the domain $R\times C$ are mapped to zero and do not need to be explicitly stated.

Functions like these can be represented in Python by dictionaries, where the keys are elements from the set $D$ or tuples from the set $R\times C$ and values are the corresponding values from $\mathbb{R}$.

Sparse vectors and matrices are implemented in Python in the module
`scipy`

, which contains the numerical code for operations on
arrays. Here
you find a short introduction to sparse matrices in
`scipy`

.

Your procedures should be able to cope with sparse representation, For example, getitem(v, k) should return a value for every domain element even if k is not a key of v.f.

However, your procedures need not make any effort to retain sparsity
when adding two vectors. That is, for two instances `u`

and `v`

of
`Vec`

, it is okay if every element of `u.D`

is represented explicitly in
the dictionary of the instance `u+v`

. Several other procedures need to
be written with the sparsity convention in mind. For example, two
vectors can be equal even if their `.f`

fields are not equal: one vector’s
`.f`

field can contain a key-value pair in which the value is zero, and
the other vector’s `.f`

field can omit this particular key. For this
reason, the `equal(u, v)`

procedure needs to be written with care.