Prev: Looking for a development tool to list all the functions in a ?source file
Next: System Calls
From: Alf P. Steinbach on 15 Mar 2010 19:02
* Peter Nilsson:
> 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.

I think you're making an assumption of consecutive powers in the lists.


Cheers,

- Alf
From: Peter Nilsson on 16 Mar 2010 01:26
"Alf P. Steinbach" <al...(a)start.no> wrote:
> * Peter Nilsson:
> > Ashton K <ash...(a)ashtonk.ath.cx> wrote:
<snip>
> > > 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.
>
> I think you're making an assumption of consecutive powers
> in the lists.

No, I only need the max from each.

% type poly.c
#include <stdlib.h>

struct term_t
{
struct term_t *next;
int c;
int n;
};

typedef struct term_t term_t;

term_t *poly_mul(const term_t *p, const term_t *q)
{
int pn, qn, rn, i, j;
const term_t *pt, *qt;
term_t **r;
term_t *s;

if (!p || !q)
return 0;

for (pt = p, pn = pt->n; pt = pt->next; )
if (pn < pt->n) pn = pt->n;

for (qt = q, qn = qt->n; qt = qt->next; )
if (qn < qt->n) qn = qt->n;

rn = pn + qn;
r = malloc((1 + rn) * sizeof *r);
if (!r) return 0;

for (i = 0; i <= rn; i++)
{
r[i] = malloc(sizeof *r[i]);
if (!r[i])
{
for (j = 0; j < i; j++) free(r[j]);
return 0;
}

r[i]->c = 0;
r[i]->n = i;
}

for (r[rn]->next = 0, i = 0; i < rn; i++)
r[i]->next = r[i + 1];

for (pt = p; pt; pt = pt->next)
for (qt = q; qt; qt = qt->next)
r[pt->n + qt->n]->c += pt->c * qt->c;

s = r[0];
free(r);
return s;
}

#include <stdio.h>

void poly_dump(const term_t *p)
{
for (; p; p = p->next)
if (p->c)
{
printf(" %c ", p->c < 0 ? '-' : '+' );
printf("%d", p->c < 0 ? -p->c : p->c);

if (p->n != 0) printf(".x");
if (p->n > 1) printf("^%d", p->n);
}
puts("");
}

int main(void)
{
static term_t p[2] = /* 1 - 2x */
{
{ p + 1, 1, 0},
{ 0, -2, 1}
};
static term_t q[3] = /* -3 - 4x + 5x^2 */
{
{ q + 1, -3, 0},
{ q + 2, 5, 2},
{ 0, -4, 1}
};

poly_dump(p);
poly_dump(q);
poly_dump(poly_mul(p, q));

return 0;
}

% acc poly.c -o poly.exe
poly.c: In function 'poly_mul':
poly.c:22: warning: suggest parentheses around assignment used as
truth value
poly.c:25: warning: suggest parentheses around assignment used as
truth value

% poly
+ 1 - 2.x
- 3 + 5.x^2 - 4.x
- 3 + 2.x + 13.x^2 - 10.x^3

%

--
Peter
From: Ashton K on 16 Mar 2010 02:10
Alf P. Steinbach <alfps(a)start.no> wrote:
> * Peter Nilsson:
>> 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.
>
> I think you're making an assumption of consecutive powers in the lists.
>
>
> Cheers,
>
> - Alf


No, as long as he's accumulating coefficients of the same pwoer as he runs
into them, you'llonly need m+n spots (assuming we're multiplying m and n
degree polynomials), as the largest term will be of the order m+n.

(a_nx^n + a_(n-1)x^(n-1) + ... + a_1x + a_0) *
(b_mx^m + b_(n-1)x^(m-1) + ... + b_1x + b_0)
= a_n*b_mx^(m+n) + ... + a_0*b_0.


--Ashton

From: Alf P. Steinbach on 16 Mar 2010 02:22
* Ashton K:
> Alf P. Steinbach <alfps(a)start.no> wrote:
>> * Peter Nilsson:
>>> 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.
>> I think you're making an assumption of consecutive powers in the lists.
>
>
> No, as long as he's accumulating coefficients of the same pwoer as he runs
> into them, you'llonly need m+n spots (assuming we're multiplying m and n
> degree polynomials), as the largest term will be of the order m+n.
>
> (a_nx^n + a_(n-1)x^(n-1) + ... + a_1x + a_0) *
> (b_mx^m + b_(n-1)x^(m-1) + ... + b_1x + b_0)
> = a_n*b_mx^(m+n) + ... + a_0*b_0.

Please don't quote signatures.

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


Cheers & hth.,

- Alf
From: Ashton K on 16 Mar 2010 02:35
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.

--Ashton

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