Suppose we have two polynomials P and Q$,$ where all coefficients are $0$ or $1($for example,

x$6+$ x$5+$ x$2).$ How does the coefficient of some term xk in the polynomial product P Q relate

to the powers of the terms present in P and Q$?$

$($b$)$ Now, let$$s consider the following problem:

There are two stores in town, one selling packets of blue marbles and the other

selling packets of white marbles. The packet sizes offered in the first store are

listed in an array B$[1..$p$],$ whose entries are all distinct positive integers no larger

than n$.$ Similarly, an array W $[1..$q$]$ describes the packet sizes offered in the other

store.

Wasim wishes to buy exactly one packet from each store. Help him find:

$$ all possible values for the total number of marbles he can buy and

$$ for each of these values, how many different ways $($i$.$e$.$ different combinations of packets

of marble$)$ he can buy to get to that value.

For example, suppose the first store sells packets of three, five and eight blue marbles, so

p $=3$ and B $=[3,5,8],$ and likewise suppose q $=3$ and W $=[1,4,6].$ Then Wasim can get:

$4$ marbles in one way $($three blue and one white$),$

$6$ marbles in one way $($five blue and one white$),$

$7$ marbles in one way $($three blue and four white$),$

$9$ marbles in three different ways $($three blue and six white, five blue and four white,

or eight blue and one white$),$

$11$ marbles in one way $($five blue and six white$),$

$12$ marbles in one way $($eight blue and four white$),$ or

$14$ marbles in one way $($eight blue and six white$).$

Using your observations from $($a$),$ design and analyse an O$($n log n$)$ algorithm to solve the

problem. Recall that n is the largest packet size available.