~~NOTOC~~

===== Homework 01 - Solving univariate polynomial equation =====

=== Task ===

Solve the problems in [[https://cw.fel.cvut.cz/b211/_media/courses/pkr/labs/hw01.pdf|hw01.pdf]]:
  - Solve tasks 1, 2 and 3.a in hand.
  - Implement the root finding function for a univariate polynomial via companion matrices.
  - Solve tasks 3.b and 4 using the function implemented in 2. In task 4 find the roots of the polynomial specified for you in Brute. **The given polynomials have integer roots, so you need to identificate the roots with multiplicity from the output of ''roots'' method.**

<note warning>
**Allowed libraries**: numpy

**Forbidden methods/classes**: numpy.roots, numpy.polynomial, numpy.poly1D
</note>

Create a function ''roots(coeffs)'' which takes the coefficients of a univariate polynomial and outputs a list of its (complex) roots. 

Input/Output specifications for ''roots'':
  - ''coeffs'' : list of float numbers defining the coefficients of the polynomial starting from the term of the highest degree.
  - **Return value** : ''numpy.ndarray'' of complex float numbers defining the roots of the given polynomial.

Implement the solution in a single file ''hw01.py''. The file must contain the ''roots'' function, such that it can be imported (by the automatic evaluation) as

<code>
import hw01
res = hw01.roots(coeffs)
</code>

=== Upload ===

Upload a zip archive ''hw01.zip'' (via the [[https://cw.felk.cvut.cz/upload/|course ware]]) containing:
  - ''hw01.json'' - json file containing the answers to tasks 1, 2, 3.b and 4 (see below for the description of how to create it)
  - ''hw01.py'' - python script containing the implemented function ''roots''
  - ''hw01.pdf'' - pdf file containing the solution to tasks 1, 2, 3.a together with the companion matrices for tasks 3.b and 4 (LaTex, photographies, scans, ...).

<note>
All the files must be contained in the root of ''hw01.zip''.
</note>

**Creating** ''hw01.json'':

Create an empty dictionary in Python:

<code>
solution = {}
</code>

The keys for this dictionary will be ''"task1"'', ''"task2"'', ''"task3"'' (for task 3.b) and ''"task4"''. 

The value for the key ''"task1"'' is the list of coefficients of the product polynomial starting from the term of the highest degree, i.e. for the product polynomial ''2*x^4 + 5*x^3 + 3*x^2 + 1'' do

<code>
solution["task1"] = [2, 5, 3, 0, 1]
</code>

The value for the key ''"task2"'' is the list of lists of coefficients of the quotient polynomial and the remainder, respectively, starting from the term of the highest degree, i.e. for the quotient polynomial ''2*x^3 + 1'' and the remainder ''x + 2'' do

<code>
solution["task2"] = [[2, 0, 0, 1], [1, 2]]
</code>

The value for the key ''"task3"'' is the list of roots to the polynomial from task 3.b (**including multiplicities**), i.e. for the sequence of roots ''1, 1, 2, 3'' do

<code>
solution["task3"] = [1, 1, 2, 3]
</code>

The value for the key ''"task4"'' is created in the same way as for the key ''"task3"''.

Finally, save ''solution'' to ''hw01.json'':

<code>
import json
with open("hw01.json", "w") as outfile:
    json.dump(solution, outfile)
</code>