In this assignment you will use Python to implement several functions that operate on vector spaces and polynomials.
**Please submit a single file a4.py containing your solutions.**

**Your file may not import any modules or employ any external library functions
(unless the problem statement explicitly permits this).
You will be graded on the correctness, concision, and mathematical legibility of your code.
The different problems and problem parts rely on each other; carefully consider whether you can use functions you define
in one part within subsequent parts.**

In this assignment, we will represent vectors in **R**^{n} and matrices in **R**^{n×n} using Python tuples and nested tuples, respectively
(as we did in Assignment #3).
A helper function `solve()`

is provided below. This function takes a **square** matrix `M`

as its first argument and a vector
`w`

as its second argument. If there is a solution `v`

to the equation `M * v = w`

, it returns the vector `v`

;
otherwise, it returns `None`

.
**The solve() method has been updated. Please use the implementation below, which should handle
zero rows and columns correctly.**

def solve(M, w, epsilon = 1.0/(10**10)): rows, cols = len(M)+1, len(M[0])+1 if rows != cols: return None I = [[1 if c==r else 0 for c in range(cols)] for r in range(rows)] M = [([M[c][r] for c in range(cols-1)] if r < rows-1 else list(w))+[0]+I[r] for r in range(rows)] def soln(M): if len([1 for i in range(cols) if abs(M[-1][i]) > epsilon]) > 0: return None return tuple([-1*M[-1][cols+j] for j in range(cols-1)]) for r in range(rows): lead = 0 if lead >= cols: return soln(M) i = r while M[i][lead] == 0: i += 1 if i == rows: i, lead = r, lead + 1 if cols == lead: return soln(M) while abs(M[r][lead]) < epsilon: lead += 1 if abs(M[r][lead]) > epsilon: M[r] = [ mrx / M[r][lead] for mrx in M[r]] for i in [j for j in range(rows) if j != r]: if r < rows-1: M[i] = [ iv - M[i][lead]*rv for rv,iv in zip(M[r],M[i])] return soln(M)Below is an example of

`solve()`

being invoked:
solve( ((1,3),(2,1)), (5,6) ) # Returns (2.6, 0.8).

- A definition of the
`Span`

class is provided below. Objects of this class represent spans; the`vectors`

field of each object is the finite set of vectors {*v*_{1}, ...,*v*_{k}} in the notation span {*v*_{1}, ...,*v*_{k}}.class Span(): def __repr__(self): return "span " + str(self.vectors) def __str__(self): return "span " + str(self.vectors) def __init__(self, vectors): self.vectors = vectors def contains(self, v): pass # Implement for Problem #1, part (a). def __eq__(span1, span2): pass # Implement for Problem #1, part (b). def basis(self): pass # Implement for Problem #1, part (c). def dim(self): pass # Implement for Problem #1, part (d). def orthonormal(self): pass # Implement for Problem #1, part (e).

- Define the
`Span`

class's`contains()`

method, which returns`True`

if the vector argument`v`

is in the vector space defined by the span, and`False`

otherwise.V = Span( { (1,0), (0,1) } ) V.contains((2,-3)) # Returns True.

- Define the
`Span`

class's`__eq__()`

method, which takes two arguments that are both`Span`

objects. The method should return`True`

if the two spans are equivalent; it should return`False`

otherwise. This method is invoked if you apply the`==`

operator to two`Span`

objects:Span( { (1,0), (0,1) } ) == Span( { (2,3) } ) # Returns False.

- Define the
`Span`

class's`basis()`

method, which returns a finite set of vectors corresponding to a basis of the vector space represented by the`Span`

object. - Define the
`Span`

class's`dim()`

method, which returns a positive integer corresponding to the dimension of the vector space represented by the`Span`

object. - Define the
`Span`

class's`orthonormal()`

method, which returns a finite set of vectors corresponding to an orthonormal basis of the vector space represented by the`Span`

object.

- Define the
- Define a function
`exactFit()`

that takes as its input a set of vectors in**R**^{2}. If there are*k*+ 1 vectors in the input, the function should find a polynomial of the form*f*(*x*) =*a*_{k}*x*^{k}+ ... +*a*_{1}*x*+*a*_{0}that exactly fits these vectors. The function should return a single vector (*a*_{k}, ...,*a*_{1},*a*_{0}) containing the coefficients of the polynomial.exactFit( { (-1,31), (-4, 268327), ( 1, 17), (-5, -1520701), ( 3, 389147), \ (-3, 78869), (-6, -19979509), ( 5, 29571949), ( 0, -1), (-2, 5027) \ } ) # The above should return (8, 36, -1, -2, 0, -9, -4, 0, -10, -1) where k is 9.

- In this problem, input polynomials are represented as Python functions. Below are a few examples:
def f(x): return 2 * x**2 + 3 * x - 5 def g(x): return x**3 + 4 * x**2 - 2 * x + 8

Implement the following functions.- Define a function
`findK()`

that takes two inputs, a function`f`

and a positive integer`k`

. If there exists a polynomial of the form*f*(*x*) =*a*_{k}*x*^{k}+ ... +*a*_{1}*x*+*a*_{0}that represents the function`f`

, the function should return a vector (*a*_{k}, ...,*a*_{1},*a*_{0}) containing the coefficients of the polynomial. Otherwise, it should return`None`

.def f(x): return x**3 + 4 * x**2 - 2 * x + 8 findK(f, 3) # Should return (1, 4, -2, 8).

- Define a function
`find()`

that takes a single input, a function`f`

. If for any*k*there exists a polynomial of the form*f*(*x*) =*a*_{k}*x*^{k}+ ... +*a*_{1}*x*+*a*_{0}that represents the function`f`

, the function should return a vector (*a*_{k}, ...,*a*_{1},*a*_{0}) containing the coefficients of the polynomial. Otherwise, it should return`None`

.def f(x): return x**3 + 4 * x**2 - 2 * x + 8 find(f) # Should return (1, 4, -2, 8).

Try to make your implementation of`find()`

as efficient as possible.

- Define a function