Prev: Looking for a development tool to list all the functions in a ?source file
Next: System Calls
From: Gene on 20 Mar 2010 23:31
On Mar 19, 11:13 pm, Patricia Shanahan <p...(a)acm.org> wrote:
> Gene wrote:
> > On Mar 15, 2:09 am, arun <arunw...(a)gmail.com> wrote:
> >> I am trying to solve the problems in "Data Structures and Algorithm
> >> Analysis in C".
> >> One of the questions asks you to find algorithms to find the product
> >> of two polynomials. The polynomials are represented using linked
> >> lists. The terms in the list may not be in sorted order. However the
> >> product itself should be a linked list where there is a single term
> >> for any power and is sorted by exponent.
>
> >> So its like ax^0 + bx^1 + ... + nx^n
>
> >> Finding an algorithm which does this in O((mn)^2) is easy (m and n are
> >> lengths of the polynomials). However the question is to find
> >> algorithms which can do this in O(nm^2) (m is the length of the
> >> shorter polynomial) and in O(mn log(mn)).
>
> >> I haven't been able to figure this out even after trying hard. I don't
> >> want complete solution (I know that this could be given as a homework
> >> problem), just some hints or pointers which will help me solve this
> >> problem.
>
> >> thanks,
> >> Arun
>
> > A different way to think about this problem is to note that you can
> > uniquely specify a polynomial of degree k with k+1 points.  So pick k
> > +1 values of x, evaluate both polynomials at these x values, multiply
> > these k+1 pairs, then find the unique polynomial that passes through
> > the resulting points.  The initial evaluation doesn't need the terms
> > in sorted order, so there are no sorting costs.  Finding the resultant
> > polynomial requires expanding the Lagrange interpolant.  I'll let you
> > all work out how quickly this can be accomplished.  The more
> > sophisticated algorithms consider the multiplication as a convolution.
> > Convolution in cartesian space is pointwise multiplication in the
> > frequency domain.  So take the FFT of the coefficients, multiply
> > pointwise, take the reverse FFT, and be happy.
>
> Remember that we don't know the degree of the input polynomials, only
> the lengths of their representations. We could have a very short
> polynomial of degree 1000.

I realize this. The other problem is that the polynomial values can
be large, so the pointwise multiplications--depending on precision
requirements--can be expensive. The only intent was to say there is
another way of thinking about the problem.
First  |  Prev  | 
Pages: 1 2 3 4 5
Prev: Looking for a development tool to list all the functions in a ?source file
Next: System Calls