Let $f(x),g(x)$ be two polynomial functions given by $f(x)=a_0+a_{1}x+a_2{x}^2+$cdots$+a_n{x}^n$

and $g(x)=b_0+b_{1}x+b_2{x}^2+$cdots$+b_m{x}^m.$

$($a$)(6$ pts$.)$ Write an algorithm called PolyAdd $(A,n,B,m)$ in pseudocode to com$-$

pute $h(x)=f(x)+g(x),$ where $f(x)$ and $g(x)$ are given as arrays $A[0..n],B[0..m]$

with $A[i]=a_i$ and $B[i]=b_i.($The indexing goes from $0$ here instead of $1$ ; the

lengths of these arrays are respectively $n+1$ and $m+1.$ The result $h(x)$ should

be returned as an array $C,$ which stores its coefficients, and its size $(max(n,m)).$

$($b$)(4$ pts$.)$ Analyze the running time of PolyAdd$(A,n,B,m).$ You may assume

that $nm$ and give your result in terms of $n.$

$($c$)(4$ pts$.)$ Write an algorithm PolyMult $(A,n,B,m)$ in pseudocode to compute

$h(x)=f(x)g(x)$ where $f(x)$ and $g(x)$ are given as before. An array $C[0..n+m]$

defining $h(x)$ and its size $(n+m)$ should be returned. Justify the correctness of

your algorithm. $($What loop invariant does your algorithm maintain?$)$

$($d$)(4$ pts$.)$ Analyze the running time of Poly$lt(A,n,B,m).$ You may assume

that $n=m,$ and give your result in terms of $n.$

$($e$)(6$ pts$.)$ Now assume that the first input polynomial $f(x)$ is always sparse, i$.$e$.,$

we know that $a_i$ will be nonzero for at most $K$ values of $i,$ where $K$ is a constant.

Modify the algorithm from part $($c$)$ to create SparsePolyMult $(A,n,B,m),$ which

takes advantage of the sparsity of $f.$ Write pseudocode for this algorithm $($or

clearly note how to modify PolyMult $(A,n,B,m)).$ Assuming $nm,$ analyze

the running time of SparsePolyMult $(A,n,B,m)$; the running time should be

$O(n).$