Prev: Looking for a development tool to list all the functions in a ?source file
Next: System Calls
From: arun on 15 Mar 2010 02:09
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

From: Alf P. Steinbach on 15 Mar 2010 02:35
* arun:
> 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.

From my point of view finding an algorithm that does the thing in O((mn)^2) or
O(nm^2) is hard. I can't imagine what algorithms you're thinking of? The
straightforward way, when limited to using linked lists, no arrays, goes like
O(mn log(mn)) -- loop for multiplication, a sort, collection of likes.


Cheers,

- Alf (puzzled)
From: Ashton K on 15 Mar 2010 10:21
Alf P. Steinbach <alfps(a)start.no> wrote:
> * arun:
>> 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.
>
> From my point of view finding an algorithm that does the thing in O((mn)^2) or
> O(nm^2) is hard. I can't imagine what algorithms you're thinking of? The
> straightforward way, when limited to using linked lists, no arrays, goes like
> O(mn log(mn)) -- loop for multiplication, a sort, collection of likes.
>
>
> Cheers,
>
> - Alf (puzzled)


I was going to say. The trivial way gets you O(mn log(mn)), I was having
a hard time imagining anything worse.

Generally speaking, in a sloppy and not in-place way, here's how you do it.


Create a new scratch space (linked list). For every element n of the list N,
multiply n by every element m in the list M. Place all these new elements on
the scratch space.

Now, using your favorite sorting algorithm (pick something that's O(n log(n))),
sort your scratch space by the power of the term. Make sure you pick a sort
that makes some sense for a linked list.

Now go through and collect all the coefficients of the same power, and produce
the final polynomial. You could do this in another storage area, or with some
tricky in-place pointer fu.

Don't forget to free any mallocs!

--Ashton
From: Kai-Uwe Bux on 15 Mar 2010 10:39
arun 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)).
[...]

First, I think, the representation of the input polynomial polynomials as
linked lists is a red herring: you can change the representation into the
one required for output in O( m log(m) ). Thus doing that for both input
polynomials feasible within the desired bound.

Second, when the input is in standard form (e.g., using arrays), you can
apply term-by-term multiplication and get good complexity bounds. You can
also apply more fancy multiplication methods (see Knuth: The Art of Computer
Programming, Vol II).

Third, insisting that the algorithm has to use linked lists internally, you
could do mn multiplications and create a list of size mn containing all the
products. Then you sort that list bringing products for the same degree
together. That takes log(mn)mn. A linear pass at the end can output the
product polynomial.


Best

Kai-Uwe Bux
From: Peter Nilsson on 15 Mar 2010 18:46
Ashton K <ash...(a)ashtonk.ath.cx> wrote:
> Alf P. Steinbach <al...(a)start.no> wrote:
> > arun:
> > > 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. ...
> >
> > The straightforward way, when limited to using linked
> > lists, no arrays, goes like O(mn log(mn))  --  loop for
> > multiplication, a sort, collection of likes.
>
> Create a new scratch space (linked list). For every element
> n of the list N, multiply n by every element m in the list M.
> Place all these new elements on the scratch space.

If you're going to allocate scratch space, then an O(m + n)
array will get you O(mn) multiplication.

--
Peter
 |  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