Introduction to Programming in Python, Aug-Dec 2014
                          Assignment 4
                  Due Monday, 13 October, 2014

----------------------------------------------------------------------
Instructions

** IMPORTANT: Note new policy regarding naming of zip file **

1. For each question, write a separate Python program with the
   filename indicated in the question.

   Zip your solutions into a single archive.  Use your CMI
   username to name the zip file (e.g. "madhavan.zip") and submit
   the zip file via moodle.

   If you don't name your zip file or the enclosed Python file
   correctly, you risk losing marks.

2. If the question asks for a function, you *must* write a
   function in Python (i.e., def f(x): ... )  Ensure that the
   function you define has the name indicated in the question.
   Also ensure that your function returns the value asked for,
   rather than printing it.

   If you add code to your file to test your function, make sure
   you *remove* this code when you submit your solution.  The
   Python file you submit should have *only* the function
   definition.

----------------------------------------------------------------------

NOTE: This assignment contains only one problem, and requires you
      to write two functions in a single file.

Filename: polynomial.py

Let us consider polynomials in a single variable x with integer
coefficients: for instance, 3x^4 - 17x^2 - 3x + 5.  Each term of
the polynomial can be represented as a pair of integers
(coefficient,exponent).  The polynomial itself is then a list of
such pairs.  

We have the following constraints to guarantee that each
polynomial has a unique representation:

-- Terms are sorted in descending order of exponent
-- No term has a zero cofficient
-- No two terms have the same exponent
-- Exponents are always nonnegative

For example, the polynomial introduced earlier is represented as

   [(3,4),(-17,2),(-3,1),(5,0)]

The zero polynomial, 0, is represented as the empty list [],
since it has no terms with nonzero coefficients.

Write Python functions for the following operations:

  addpoly(p1,p2)
  multpoly(p1,p2)

that add and multiply two polynomials, respectively.

You may assume that the inputs to these functions follow the
representation given above.  Correspondingly, the outputs from
these functions should also obey the same constraints.

Some examples:

   >>> addpoly([(4,3),(3,0)],[(-4,3),(2,1)])
   [(2,1),(3,0)]

   Explanation: (4x^3 + 3) + (-4x^3 + 2x) = 2x + 3

   >>> addpoly([(2,1)],[(-2,1)])
   []

   Explanation: 2x + (-2x) = 0

   >>> multpoly([(1,1),(-1,0)],[(1,2),(1,1),(1,0)])
   [(1,3),(-1,0)]

   Explanation: (x - 1) * (x^2 + x + 1) = x^3 - 1

Hint: You are not restricted to writing just the two functions
   asked for.  You can write auxiliary functions to "clean up"
   polynomials --- e.g., remove zero coefficient terms, combine
   like terms, sort by exponent etc.  Build a library of small
   functions that can be combined to achieve the desired format.
   
======================================================================