~~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 and we want you to upload them as integers, including multiplicities.**

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

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

<note>
You are not allowed to use other libraries than the ones indicated in the list **Allowed libraries**.
</note>

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

Input/Output specifications for ''roots(coeffs: numpy.ndarray) -> numpy.ndarray'':
  - ''coeffs'' : 1-dimensional ''numpy.ndarray'' that defines the coefficients of the polynomial starting from the term of the highest degree.
  - **Return value** : 1-dimensional ''numpy.ndarray'' containing 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
import numpy as np
coeffs = np.array([1, 2, 3])
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, photos, 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 are ''"task1"'', ''"task2"'', ''"task3"'' (for task 3.b) and ''"task4"''. 

The value for the key ''"task1"'' is a 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 a 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 a list of roots to the polynomial from task 3.b (**including multiplicities**), i.e. for the sequence of integer 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>