Assignment

Assignment#

Access to the software and download of the assignment#

For this week, the assignment will be essentially empty. Using the git repository will mainly be a convenient way for you to save and transfer your work, and for us to review it.

Instructions#

All non-trivial code must be in the mycode.py file. If it becomes too long, you can create other files, mentioning them in the report.

Any function must:

  • be documented
    the documentation must include examples and a quick estimate of the algorithmic complexity of the function;

  • be tested
    see the example provided for how to write the tests as doctests;

  • by typed: use type annotations wherever possible.

You should have checked your code with static analyzers such as ruff or mypy.

In addition, you must keep a concise report up to date along the way.

Getting started#

See the files mycode.py and the report skeleton in the README.md.

Import the objects defined in mycode.py and reload them automatically when changes are made:

%load_ext autoreload
%autoreload 2
from mycode import *

Use:

response("Are you hungry")

Lookup the documentation:

response?

Static checks:

!ruff check mycode.py

!mypy mycode.py

Launching the tests:

!sage -t mycode.py

Indication

To use Sage objects in mycode.py, e.g. for type annotations, you need to import them. To this end, the mycode.py file starts with:

from sage.all import matrix  # type:ignore

Adjust that line if you need more Sage objects.

Gauß elimination#

  1. In the function reduced_echelon_form of mycode.py, implement Gauß’s algorithm for computing the row reduced echelon form of a matrix with coefficients in a field.

  2. What is the complexity of your implementation?

Note

Here and in latter complexity analyses, state explicitly your computation model: how do you measure the size of the input? What are the elementary operations? Justify your analysis.

Membership testing for a vector subspace#

Let V=(v_i)_i be a list of vectors. We wish to determine whether a vector w is in the vector subspace generated by (v_i)_i.

  1. Using reduced_echelon_form, implement the function subspace_membership.

  2. Would it be enough to have a matrix in echelon form?

  3. What is the complexity of your implementation?

Computation of a basis of the sum of two vector subspaces#

  1. Implement the function sum_of_vector_spaces

  2. What is the complexity of your implementation?