getDerivative, Plus, Minus, Times Hints

[Igor Ivkovic]

If you look at my previous post to the newsgroup, it should be clear how
to implement all of the other methods.

If it is not clear, let me repeat that if you know that you are dealing
with a PolynomialAsLinkedList instance - and that will hold for new
instances created in getDerivate, plus, minus, and times as well as for
"this" polynomial - you may directly call LinkedList methods on the
underlying linked lists for any of these polynomials. Hence, you will save
running time by avoiding possible overhead associated with calling
SetCoefficient on new polynomials by using LinkedList "append" method.

With regards to GetCoefficient, let me remind you that your other
implementation of PolynomialAsArray returns the coefficient in O(1) time,
as it accesses it directly from the polynomial array. Therefore, calling
GetCoefficient M times in the case when you are passed a parameter that is
not an instance of PolynomialAsLinkedList will only take O(M) time, and
that compounded with O(n) time required to access the elements of "this"
will result in the overall running time of O(n + M).

Igor

Hey there,
I'm having trouble implementing the "add" method for project 3 within
the time bounds of O(n + M) when "p" is NOT a PolynomialAsLinkedList.
If we're assuming that "p" is any concrete class implementing the
Polynomial interface then the only way to traverse it (that I can see),
is to run a for loop from the degree of the polynomial down to 0 because
we don't know what data structure it implements underneath. Now, once
we do that it's already 0(M), and the only way to access the
coefficients is the "getCoefficient" method which runs O(n). Running an
O(n) inside a for loop is now O(Mn). I cannot see a way around this,
could you perhaps give me some guidance?
Thanks,
Paul
----------------------------------------
This mail sent through www.mywaterloo.ca

[Luc Gallant]

This is insightful, but I do have one question. Should we be making the
assumption here that p ( the polynomial passed in ) cannot be of type
linked list. I mean, I don't mean "PolyonmialAsLinkedList", I mean ilke
"PolALList" or something of a different type. Like, what if someone else
implements it with their own class that uses linked lists but not the same
name as what we're looking for. In this case, isn't it necessary to have
O(n*M)? I mean, you have to use getCoefficient for each term of the
polyonmial passed in. Can you help with this please?

Luc

Post by Igor Ivkovic
If you look at my previous post to the newsgroup, it should be clear how
to implement all of the other methods.
If it is not clear, let me repeat that if you know that you are dealing
with a PolynomialAsLinkedList instance - and that will hold for new
instances created in getDerivate, plus, minus, and times as well as for
"this" polynomial - you may directly call LinkedList methods on the
underlying linked lists for any of these polynomials. Hence, you will save
running time by avoiding possible overhead associated with calling
SetCoefficient on new polynomials by using LinkedList "append" method.
With regards to GetCoefficient, let me remind you that your other
implementation of PolynomialAsArray returns the coefficient in O(1) time,
as it accesses it directly from the polynomial array. Therefore, calling
GetCoefficient M times in the case when you are passed a parameter that is
not an instance of PolynomialAsLinkedList will only take O(M) time, and
that compounded with O(n) time required to access the elements of "this"
will result in the overall running time of O(n + M).
Igor

Hey there,
I'm having trouble implementing the "add" method for project 3 within
the time bounds of O(n + M) when "p" is NOT a PolynomialAsLinkedList.
If we're assuming that "p" is any concrete class implementing the
Polynomial interface then the only way to traverse it (that I can see),
is to run a for loop from the degree of the polynomial down to 0 because
we don't know what data structure it implements underneath. Now, once
we do that it's already 0(M), and the only way to access the
coefficients is the "getCoefficient" method which runs O(n). Running an
O(n) inside a for loop is now O(Mn). I cannot see a way around this,
could you perhaps give me some guidance?
Thanks,
Paul
----------------------------------------
This mail sent through www.mywaterloo.ca

[Igor Ivkovic]

In general, what you are saying is true; other people could implement this
same class and give it a different name. However, in our P3 AE test case
we scope this problem to Polynomial being either PolynomialAsArray or
PolynomialAsLinkedList instance (i.e., your P2 or your P3 implementation).

You may use this hint to define the scope of your implementation to
PolynomialAsArray and PolynomialAsLinkedList but when dealing with the
former (i.e., PAA) you are to *strictly* use the Polynomial interface
(i.e., you may NOT make any direct calls as you may in the later case).

Igor

Post by Luc Gallant
This is insightful, but I do have one question. Should we be making the
assumption here that p ( the polynomial passed in ) cannot be of type
linked list. I mean, I don't mean "PolyonmialAsLinkedList", I mean ilke
"PolALList" or something of a different type. Like, what if someone else
implements it with their own class that uses linked lists but not the same
name as what we're looking for. In this case, isn't it necessary to have
O(n*M)? I mean, you have to use getCoefficient for each term of the
polyonmial passed in. Can you help with this please?
Luc

Post by Igor Ivkovic
If you look at my previous post to the newsgroup, it should be clear how
to implement all of the other methods.
If it is not clear, let me repeat that if you know that you are dealing
with a PolynomialAsLinkedList instance - and that will hold for new
instances created in getDerivate, plus, minus, and times as well as for
"this" polynomial - you may directly call LinkedList methods on the
underlying linked lists for any of these polynomials. Hence, you will save
running time by avoiding possible overhead associated with calling
SetCoefficient on new polynomials by using LinkedList "append" method.
With regards to GetCoefficient, let me remind you that your other
implementation of PolynomialAsArray returns the coefficient in O(1) time,
as it accesses it directly from the polynomial array. Therefore, calling
GetCoefficient M times in the case when you are passed a parameter that is
not an instance of PolynomialAsLinkedList will only take O(M) time, and
that compounded with O(n) time required to access the elements of "this"
will result in the overall running time of O(n + M).
Igor

Hey there,
I'm having trouble implementing the "add" method for project 3 within
the time bounds of O(n + M) when "p" is NOT a PolynomialAsLinkedList.
If we're assuming that "p" is any concrete class implementing the
Polynomial interface then the only way to traverse it (that I can see),
is to run a for loop from the degree of the polynomial down to 0 because
we don't know what data structure it implements underneath. Now, once
we do that it's already 0(M), and the only way to access the
coefficients is the "getCoefficient" method which runs O(n). Running an
O(n) inside a for loop is now O(Mn). I cannot see a way around this,
could you perhaps give me some guidance?
Thanks,
Paul
----------------------------------------
This mail sent through www.mywaterloo.ca