# Programming Task 1: Hello Polynomial World

### Reviewed Sept 17th, 2014

#### Guidelines

• You are working in teams of four (two sets of partners). This will require workplace-style maturity.
• These tasks will test your ability to put notions into practice within a team setting.
• Submit your teams' working code to andy at novocin.com prior to your scheduled review.
• I will run the code on real inputs using ideone.com with the C++11 environment.
• Presentation day will consist of a scheduled 45 minute meeting.
• At that meeting I will run the code.
• I will select one person from your team using a random integer, that person will explain the code and answer my questions.
• I will assign a grade that day for all of you based on the randomly selected team member's explanation.
• It is your responsibility to make sure that everyone on your team understands the concepts behind your solution.
• Coding in C++ is a soft requirement of the course, this method allows the coding aspects of the project to be spread while ensuring some practical awareness.

### The Programming tasks for this assignment:

1. Input: Two polynomials, one per line, each with format:

n  c1 c2 ... cn


The input will come from stdin. Here n is the length of the polynomial and it is followed by n integers which are the coefficients of the polynomial. Note that c1 is the constant coefficient (i.e. coefficient of $$x^0$$ ).

Output: The product of the two input polynomials, displayed to stdout, in the format:

c1*x^0 + c2*x^1 + c3*x^2 +  $$\cdots$$  + cm*x^m

Here m is the integer degree of the output polynomial. While ci is the $$i^{\textrm{th}}$$ coefficient of the product (i.e. the coefficient of $$x^{i-1}$$ ).

Constraints: Each input polynomial will have length at least 1 and at most 100. All coefficients will be between -100 and 100, inclusive. Your algorithm must have $$\mathcal{O}(n^2)$$ arithmetic operations, where $$n$$ is the maximum input length. You may assume that all coefficients of the output will fit into an int.

Sample instance:
Input:

4  -1 0 0 1
4  1 0 0 1

Output:

-1*x^0 + 0*x^1 + 0*x^2 + 0*x^3 + 0*x^4 + 0*x^5 + 1*x^6

2. Input: The same as above, two polynomials given as an integer length and a space followed by that many space-separated coefficients, one polynomial per line.

Output: The product of the two polynomials, evaluated at 1, i.e. let $$P(x) = f(x) g(x)$$ where $$f, g$$ are your input polynomials then your goal is to display $$P(1)$$. This will be an integer which should be displayed to stdout.

Constraints: Each input polynomial will have length at least 1 and at most 100. All coefficients will be between -100 and 100, inclusive. Your algorithm must have only $$\mathcal{O}(n)$$ arithmetic operations, where $$n$$ is the maximum input length.

Sample instance:
Input:

4  -100 2 3 99
2  1 -2


Output:

-4

3. Input: The length of two special polynomials, on one line, separated by a space, i.e.

n1 n2

Here the special polynomials are of the form   $$f_n (x) = 1 + 2x + 3x^2 + \cdots + nx^{n-1}$$. So if the input was 5 2 then the two polynomials would be $$1 + 2x + 3x^2 + 4x^3 + 5x^4$$ and $$1 + 2x$$.

Output: The product of the two polynomials, evaluated at 1, i.e. $$P(1)$$ where $$P(x) = f_{n1}(x) \cdot f_{n2}(x)$$. This will be an integer which should be displayed to stdout.

Constraints: The inputs will be two numbers between 1 and 10000, inclusive. Your algorithms must use only $$\mathcal{O}(1)$$ arithmetic operations, regardless of the input size.

Sample instance:
Input:

5 8


Output:

540


### Help

A sample environment is available at this IDEONE snippet. It happens to return the correct result for one input. A real algorithm will actually compute something.