Questions about analysis of algorithm

In summary, the conversation discusses an algorithm that uses polynomial division to find the remainder and quotient of two polynomials. It involves subtracting a polynomial from the dividend in each iteration, with the goal of making the coefficient of the highest power in the dividend become 0. At the end of the algorithm, the remaining value of the dividend is assigned to the remainder, and the quotient is constructed from the values assigned to the quotient in each iteration. The conversation also addresses potential errors in the algorithm and clarifies the purpose of certain steps.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Wave)

The following algorithm is given:

View attachment 7522

And it says the following:

View attachment 7523

First of all, at the first line do they mean that the content of j is i?

About the second line, why don't we subtract the polynomial $f \cdot u \cdot h \cdot X^i $ from $(f[0], \dots, f[d'])$?

Is there then maybe an error at the algorithm at the line 8? Because at the first iteration for i=d' and j=i=d' we would get f[d']<-f[d']-uf[d']h[d'], but h[d'] is 0, when we suppose that d<d'. So should it maybe be f[j]<-f[j]-ah[j-d] ?Also, what do they mean at the part <<In line 5... unaltered.>> ? At line 5 of the algorithm, we have a<-u*f. Why is it said that the polynomial $f \cdot u \cdot h \cdot X^{i-d}$ is added to $h \cdot (q[0], \dots, q[d'-d])$ ? (Thinking)
 

Attachments

  • pol.JPG
    pol.JPG
    24.3 KB · Views: 79
  • ex.JPG
    ex.JPG
    26.4 KB · Views: 84
Last edited:
Physics news on Phys.org
  • #2
evinda said:
First of all, at the first line do they mean that the content of j is i?

Hi evinda! (Smile)

Yep. I think so too.

evinda said:
About the second line, why don't we subtract the polynomial $f \cdot u \cdot h \cdot X^i $ from $(f[0], \dots, f[d'])$?


Wouldn't we multiply $(f_{d'}\cdot u \cdot X^{d'-d})$ with $(h_dX^d+h_{d-1}X^{d-1} +... + h_0)$ to get $(f_{d'}X^{d'}+...)$? (Wondering)
So I think it is correct as it is given.

evinda said:
Is there then maybe an error at the algorithm at the line 8? Because at the first iteration for i=d' and j=i=d' we would get f[d']<-f[d']-uf[d']h[d'], but h[d'] is 0, when we suppose that d<d'. So should it maybe be f[j]<-f[j]-ah[j-d] ?

Yes, I believe there is an error too.
But I think it should be $f[j] \leftarrow f[j] - a\cdot h[j-(d'-d)]$, shouldn't it?
After all, the first time with $j=i=d'$, I think it should work out as $f[d'] \leftarrow f[d'] - a\cdot h[d'-(d'-d)]$. (Thinking)

evinda said:
Also, what do they mean at the part <<In line 5... unaltered.>> ? At line 5 of the algorithm, we have a<-u*f. Why is it said that the polynomial $f \cdot u \cdot h \cdot X^{i-d}$ is added to $h \cdot (q[0], \dots, q[d'-d])$ ? (Thinking)


This is the so called loop invariant.
In every iteration we have that $f_{original}=f+h\cdot q + r$.
Initially we have $q=r=0$, making it evidently true.
And at the end, when the algorithm is done, we have $f=0$ and $f_{original} = h\cdot q + r$, which is what we want to find. (Thinking)
 
  • #3
I like Serena said:
Wouldn't we multiply $(f_{d'}\cdot u \cdot X^{d'-d})$ with $(h_dX^d+h_{d-1}X^{d-1} +... + h_0)$ to get $(f_{d'}X^{d'}+...)$? (Wondering)
So I think it is correct as it is given.

Ah, but I think that we subtract the polynomial $f \cdot u \cdot X^{i-d}$ from $(f[0], \dots, f[d'])$. Or am I wrong? (Thinking)
I like Serena said:
Yes, I believe there is an error too.
But I think it should be $f[j] \leftarrow f[j] - a\cdot h[j-(d'-d)]$, shouldn't it?
After all, the first time with $j=i=d'$, I think it should work out as $f[d'] \leftarrow f[d'] - a\cdot h[d'-(d'-d)]$. (Thinking)

Yes, I see... (Nod)

I like Serena said:
This is the so called loop invariant.
In every iteration we have that $f_{original}=f+h\cdot q + r$.
Initially we have $q=r=0$, making it evidently true.
And at the end, when the algorithm is done, we have $f=0$ and $f_{original} = h\cdot q + r$, which is what we want to find. (Thinking)

I haven't really understood this. How can we show that this equality holds after each iteration? (Thinking)

And why do we have at the end $f=0$ and $f_{original} = h\cdot q + r$? (Thinking)
 
  • #4
evinda said:
Ah, but I think that we subtract the polynomial $f \cdot u \cdot X^{i-d}$ from $(f[0], \dots, f[d'])$. Or am I wrong?

Aren't we subtracting $a\cdot h[j-(d'-d)]$ from $f[j]$, where $a=u\cdot f$?
And repeat for every value of $j$ (Wondering)
So I think we're subtracting $f \cdot u \cdot X^{i-d} \cdot (h[0],\dots,h[d])$ from $(f[0], \dots, f[d'])$.
This is designed so that the coefficient of the highest power in $f$ becomes 0.
And simultaneously we add an entry to $q$ so that $f+h\cdot q$ remains the same.

evinda said:
I haven't really understood this. How can we show that this equality holds after each iteration? (Thinking)

And why do we have at the end $f=0$ and $f_{original} = h\cdot q + r$? (Thinking)

I didn't say it quite right, since $r$ only gets a value at the very end.
Initially we have $f_{original}=f+h\cdot q$, since $q=0$ at this time.
Then in each step we find another entry in $q$ (the quotient) and modify $f$ accordingly.
That is, we subtract a polynomial from $f$ such that the coefficient of its highest power becomes 0.
And finally, the remaining value of $f$, that now has a lower power than $h$, is assigned to $r$ (the remainder). (Thinking)
 
  • #5
I like Serena said:
Aren't we subtracting $a\cdot h[j-(d'-d)]$ from $f[j]$, where $a=u\cdot f$?


I think that we should subtract $a\cdot h[j-(i-d)]$ from $f[j]$. Right? (Thinking)

I like Serena said:
And repeat for every value of $j$ (Wondering)
So I think we're subtracting $f \cdot u \cdot X^{i-d} \cdot (h[0],\dots,h[d])$ from $(f[0], \dots, f[d'])$.


How do we see that $u f h[d]$ corresponds to the polynomial $f u h X^{i-d}$ ? I am confused right now. (Worried)
I like Serena said:
This is designed so that the coefficient of the highest power in $f$ becomes 0.

I see...
I like Serena said:
I didn't say it quite right, since $r$ only gets a value at the very end.
Initially we have $f_{original}=f+h\cdot q$, since $q=0$ at this time.

Ok.

I like Serena said:
Then in each step we find another entry in $q$ (the quotient) and modify $f$ accordingly.

I was thinking how we can show that after each iteration the equality holds. For an arbitrary $i$, we get that $q[i-d] \leftarrow uf$, $f \leftarrow 0$ and $f[i-k] \leftarrow f[i-k]-ufh[j-(i-d)], k=1, \dots, d$.

Do we get the desired equality from these equalities? If so, how? (Thinking)
 
  • #6
For $i=d'$, we get for example $q[0 \dots d'-d]=(0, \dots, u f[d'])$.
We set $a=u f[d']$ and we get

$$f[d']=0 \\ f[d'-1] \leftarrow f[d'-1]-a h[d-1] \\ \dots \\ f[d'-d] \leftarrow f[d'-d]-ah[0]$$

So after the first iteration we have that $f+hq=(0, f[d'-1]-a h[d-1], \dots, f[d'-d]-ah[0])+(h[0], \dots, h[d]) \cdot (0, \dots, u f[d])$. Right? If so, why is this equal to $f_{\text{original}}$ ? (Thinking)
 

1. What is an algorithm?

An algorithm is a set of instructions or steps used to solve a problem or perform a task. It is a fundamental concept in computer science and is used to design and analyze efficient solutions to problems.

2. Why is it important to analyze algorithms?

Analyzing algorithms helps us understand their efficiency and performance, and allows us to make informed decisions when choosing the best algorithm for a particular problem. It also helps in identifying areas for improvement and optimizing algorithms for better performance.

3. What is the time complexity of an algorithm?

The time complexity of an algorithm is a measure of the amount of time it takes to run as a function of the input size. It is usually expressed using big-O notation, which represents the worst-case scenario for the algorithm's runtime.

4. How do you determine the time complexity of an algorithm?

The time complexity of an algorithm can be determined by analyzing the number of operations or steps it takes to solve a problem as the input size increases. This can be done through mathematical analysis, empirical testing, or using tools such as algorithm visualizers.

5. Can two algorithms have the same time complexity?

Yes, two algorithms can have the same time complexity if they have a similar number of operations and steps for a given input size. However, one algorithm may still be more efficient than the other in terms of space complexity or other factors. Therefore, it is important to consider all aspects when analyzing and comparing algorithms.

Similar threads

  • Linear and Abstract Algebra
Replies
10
Views
2K
  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
1K
  • Linear and Abstract Algebra
Replies
16
Views
1K
  • Linear and Abstract Algebra
Replies
5
Views
2K
  • Advanced Physics Homework Help
Replies
2
Views
728
Replies
7
Views
820
Replies
7
Views
752
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
19
Views
2K
Back
Top