From: Gene on 19 Mar 2010 22:03 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.
From: Patricia Shanahan on 19 Mar 2010 23:13 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. Patricia
From: Pascal J. Bourguignon on 20 Mar 2010 05:16 Patricia Shanahan <pats(a)acm.org> writes: > 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. But the degree of such a polynomial representation can be determined in O(length) which is good. -- __Pascal Bourguignon__
From: Kai-Uwe Bux on 20 Mar 2010 07:01 Pascal J. Bourguignon wrote: > Patricia Shanahan <pats(a)acm.org> writes: > >> 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. > > But the degree of such a polynomial representation can be determined in > O(length) which is good. True, but finding the product p*q using interpolation will still require some deg(p)+deg(q) evaluations of the product. When deq(p) and deg(q) are large compared to the input length, you exceed the allowed complexity, e.g.: O( len(p) * len(q) * log( len(p) * len(q) ) ) Best Kai-Uwe Bux
From: Patricia Shanahan on 20 Mar 2010 09:22 Kai-Uwe Bux wrote: > Pascal J. Bourguignon wrote: > >> Patricia Shanahan <pats(a)acm.org> writes: >> >>> 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. >> But the degree of such a polynomial representation can be determined in >> O(length) which is good. > > True, but finding the product p*q using interpolation will still require > some deg(p)+deg(q) evaluations of the product. When deq(p) and deg(q) are > large compared to the input length, you exceed the allowed complexity, e.g.: > > O( len(p) * len(q) * log( len(p) * len(q) ) ) Or, for the case that I find troubling: O( len(p) * len(q) * len(q) ) where p is the longer input. Maybe the person setting the problem assumed degree and length were equivalent, but then it is hard to see why the target complexities are so high. Patricia
First
|
Prev
|
Next
|
Last
Pages: 1 2 3 4 5 Prev: Looking for a development tool to list all the functions in a ?source file Next: System Calls |