Prev: Looking for a development tool to list all the functions in a ?source file
Next: System Calls
From: Alf P. Steinbach on 16 Mar 2010 03:10
* Ashton K:
> Alf P. Steinbach <alfps(a)start.no> wrote:
>> Peter's solving a problem that depending on input can be different, with
>> different m and n.
>>
>> In the list case the O( m*n log(m*n) ) refers to the number of elements in the
>> lists M and N.
>>
>> In Peter's case m and n refer to highest powers present in the lists M and N,
>> which if there is no restriction can be arbitrarily large, even for lists of
>> size 1, i.e. his O(m*n) does not necessarily refer to list sizes; it does that
>> only if each list of size n+1 contains terms with powers 0 through n.
>>
>> Hence my comment about probably an assumption of consecutive powers (implicitly
>> startng with zeroth power) in the lists.
>>
>> That said, the OP effectively made that assumption by showing an example with
>> highest power n and then explaining that n was the length of one polynomial.
>>
>> But I think we should be clear about O(in-list-size) and O(in-highest-exponent).
>>
>
> Sorry about the sig thing. Still getting used to my news reader.
>
> I'd probably still go with O(in-highest-exponent), in your termonology, as
> that's the worst case scenario (two polynomials with no zero terms).
>
> Normally I'd be tempted to say "screw it, just used a linked list for the
> scratch space, and be over with it". But I feel like the algorithms would
> be far more efficient using a nice array full of coefficient "buckets", to
> avoid having to traverse and fill in coefficients when creating (or sort
> through later and condense).
>
> Yes, I'm aware this isn't the way I originally proposed, I've been thinking
> it over.
>
> So in this particular case, I'd be more interested in m and n in terms of
> polynomial degree, rather than list size. For if m and n are the degrees,
> we know we need *exactly* m+n scratch space, but if m and n are list lengths,
> we know we need at *minimum* m+n scratch space (as skipped coefficients could
> increase the size of the required scratch space).
>
> Now, technically they're both O(m+n) as far space is concerned, and
> O(m*n) as far as time is concerned. It's just a nitpick on terminology.
>
>
> Unless, of course, I completely misunderstood you. Which is always a
> distinct possibility when I'm involved. If so, explain what you meant
> better please.

Consider two lists A and B each of which contains a single element, that element
representing 1*x^1000.

For the array approach to multiplication that translates to scanning an array of
one million (plus one) elements, about one million operations.

That's what I mean by O(in-highest-exponent).

For the simple list multiplication it translates to 1 multiplication, sorting a
1-element result list, and scanning that 1-element list to collect together like
powers, and that's sort of like 3 operations, or something.

That's what I mean by O(in-list-size).


Cheers & hth.,

- Alf
From: Ashton K on 16 Mar 2010 03:25
Alf P. Steinbach <alfps(a)start.no> wrote:
> Consider two lists A and B each of which contains a single element, that element
> representing 1*x^1000.
>
> For the array approach to multiplication that translates to scanning an array of
> one million (plus one) elements, about one million operations.
>
> That's what I mean by O(in-highest-exponent).
>
> For the simple list multiplication it translates to 1 multiplication, sorting a
> 1-element result list, and scanning that 1-element list to collect together like
> powers, and that's sort of like 3 operations, or something.
>
> That's what I mean by O(in-list-size).
>
>


Ohhh, hadn't thought of it that way. Good point.

--Ashton
From: Patricia Shanahan on 16 Mar 2010 08:58
Kai-Uwe Bux wrote:
> 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.

I agree with this for the O(mn log(mn)) algorithm, but what about
O(nm^2)? There is no guarantee that m increases as fast as log(n).

More generally, the O(nm^2) case seems very hard. It has to do something
clever, other than a comparison sort, to gets its terms ordered.

That is implied by the possible reduction of sorting a list of N
integers to a polynomial multiplication of a length N polynomial by a
length 1 polynomial, 1*x^0. If m is a constant, O(nm^2) is the same as
O(n), so the reduction would lead to an O(N) sort of the N integers.
That cannot be done by comparison sorting.

Patricia
From: Walter Banks on 16 Mar 2010 13:17


arun wrote:

> I am trying to solve the problems in "Data Structures and Algorithm
> Analysis in C".
>
> So its like ax^0 + bx^1 + ... + nx^n
>
> just some hints or pointers which will help me solve this
> problem.

There are lots of hits on horner's method or horner polymonial
evaluation

Essentially it is

r = ax^0 + bx^1 + cx^2 + dx^3

can be rewritten as

r = dx^3+cx^2+ bx^1 + ax^0

which can be rewritten
.
r = ((dx + c) x + b) x + a

This will reduce teh number of multiplies by n.


Regards

Walter
--

Walter Banks
Byte Craft Limited
http://www.bytecraft.com


From: Pascal J. Bourguignon on 19 Mar 2010 12:16
Kai-Uwe Bux <jkherciueh(a)gmx.net> writes:

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

If you have a list of polynomial terms, you can convert it into a
normalized polynomial vector in O(max(length(list),degree)). Because in
this condition, each term must have the power with itself.

For example, for ax�+bx+c, ((b 1) (c 0) (a 2)) --> [c b a] in 3 steps.

(defun normalize-polynomial (terms)
(let* ((degree (reduce (function max) terms
:key (function term-exponent)
:initial-value 0)) ; O(length(terms))
(normalized (make-array (1+ degree )
:initial-element 0))) ; O(degree)
(dolist (term terms) ; O(length(terms))
(incf (aref normalized (term-exponent term))
(term-coefficient term)))
normalized))

(defstruct (term (:type list)) coefficient exponent)

(normalize-polynomial '((2 1) (1 0) (1 2))) --> [1 2 1]
(normalize-polynomial '((2 3) (-1 0) (1 6))) --> [-1 0 0 2 0 0 1]


--
__Pascal Bourguignon__
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