~~NOTOC~~

===== Homework 07 - Division Algorithm =====

=== Task ===

Implement the algorithm of polynomial division for more than one divisor (the examples and pseudo-algorithm of polynomial division can be found in [[https://cw.fel.cvut.cz/b211/_media/courses/pro/lab08.pdf|lab slides from week 8 ]] and [[https://cw.fel.cvut.cz/b211/_media/courses/pro/02_slides_solving_equation.pdf|lecture slides from week 9 and 10]]. )

Create a function ''poly_div(f, divs, mo)'' for dividing the polynomial ''f'' by the list of polynomials ''divs'' using the specified monomial ordering ''mo''.

Input/Output specifications for ''poly_div'':
  - ''f'' : ''Poly'' object
  - ''divs'' : list of ''Poly'' objects
  - ''mo'' : String. It can take the following values (according to SymPy documentation): 
    - ''"lex"''       - lexicographic order
    - ''"grlex"''     - graded lexicographic order
    - ''"grevlex"''   - graded reversed lexicographic order
  - **Return value** : dictionary with 2 keys ''"q"'' and ''"r"'', whose values are the list of quotient polynomials (list of ''Poly'' objects) and the remainder of the division (''Poly'' object), respectively. That is,
$$ f = \sum_{i}q[i]\cdot divs[i] + r, \quad \mathrm{LT}(r) \text{ is not divisible by any of  } \mathrm{LT}(divs[i]) \;\text{ or }\; r = 0. $$

For the explanation of how to work with ''Poly'' objects see [[https://docs.sympy.org/latest/modules/polys/reference.html|Sympy documentation]]. **You can use only Sympy library. It is not allowed to use the method ''reduced'' from Sympy library**.

=== Upload ===

Upload a zip archive ''hw07.zip'' (via the [[https://cw.felk.cvut.cz/upload/|course ware]]) containing the following files:
  - ''hw07.py'' - python script containing the implemented function ''poly_div''