[TechSyndrome]

I get it! Pn-3 is P minus 3 index which is P0! Then Pn-1 is P minus index 1 which equals P2! So the first few indexes have already been defined, and all we are doing is subtracting the index!

This post has been edited by TechSyndrome: 20 May 2012 - 01:17 PM

[sepp2k]

Okay, so let's say we're looking for P₆. We know we need to use the rule "P_n = (P_{n - 3} * P_n-1) + 1". The way to use that rule to find P₆ is to replace each occurrence of n with 6. So we get the rule:

P₆ = (P_{6 - 3} * P_6-1) + 1

Now we 6-3 and 6-1 are easily calculated, so we get:

P₆ = (P₃ * P₅) + 1

Now we only need to know the values of P₃ and P₅. If we already calculated those, we can just insert them and we're done. If we haven't calculated them yet, we need to apply the rule again, this time replacing n with 5 (and then after that with 3), instead of 6.

[TechSyndrome]

sepp2k, on 20 May 2012 - 01:17 PM, said:

Okay, so let's say we're looking for P₆. We know we need to use the rule "P_n = (P_{n - 3} * P_n-1) + 1". The way to use that rule to find P₆ is to replace each occurrence of n with 6. So we get the rule:

P₆ = (P_{6 - 3} * P_6-1) + 1

Now we 6-3 and 6-1 are easily calculated, so we get:

P₆ = (P₃ * P₅) + 1

Now we only need to know the values of P₃ and P₅. If we already calculated those, we can just insert them and we're done. If we haven't calculated them yet, we need to apply the rule again, this time replacing n with 5 (and then after that with 3), instead of 6.

I'm writing this out with a pen right now to make sure I understand it fully.

[TechSyndrome]

TechSyndrome, on 20 May 2012 - 01:28 PM, said:

sepp2k, on 20 May 2012 - 01:17 PM, said:

Okay, so let's say we're looking for P₆. We know we need to use the rule "P_n = (P_{n - 3} * P_n-1) + 1". The way to use that rule to find P₆ is to replace each occurrence of n with 6. So we get the rule:

P₆ = (P_{6 - 3} * P_6-1) + 1

Now we 6-3 and 6-1 are easily calculated, so we get:

P₆ = (P₃ * P₅) + 1

Now we only need to know the values of P₃ and P₅. If we already calculated those, we can just insert them and we're done. If we haven't calculated them yet, we need to apply the rule again, this time replacing n with 5 (and then after that with 3), instead of 6.

I'm writing this out with a pen right now to make sure I understand it fully.

I'm sorry if I'm going around in circles, but how does P3 in "P₆ = (P₃ * P₅) + 1" represent the value 2? We know that P0, P1, P2 is equal to 1, but P3 hasn't actually been given a value yet?

This post has been edited by TechSyndrome: 20 May 2012 - 01:43 PM

[TechSyndrome]

Please refer me back if you have already explained this to me.

[macosxnerd101]

P₃ is equal to the value of P₀ * P₂ + 1, which evaluates to 1 * 1 + 1, which is 2.

[TechSyndrome]

macosxnerd101, on 20 May 2012 - 01:42 PM, said:

P₃ is equal to the value of P₀ * P₂ + 1, which evaluates to 1 * 1 + 1, which is 2.

Oh right, I thought the gentleman who was helping was giving me an alternative method to work backwards. Thanks.

[sepp2k]

TechSyndrome, on 20 May 2012 - 10:34 PM, said:

I'm sorry if I'm going around in circles, but how does P3 represent the value 2? We know that P0, P1, P2 is equal to 1, but P3 hasn't actually been given a value yet?

We calculate P3 the same way we do P6, i.e. by taking the rule "P_n = (P_{n - 3} * P_n-1) + 1" and replacing n with 3, so we get:

P₃ = (P_{3 - 3} * P_3-1) + 1

, which is:

P₃ = (P₀ * P₂) + 1

Since we already know P₀ and P₂ this becomes:

P₃ = (1 * 1) + 1

, which is 2.

[macosxnerd101]

Look at your recurrence and plug in the values. P₀, P₁ and P₂ are your base cases. Since P₃ is the first term defined by the recurrence relation, that's the first term that will utilize the base cases.

[TechSyndrome]

OMG, OMG! I've figured it out! I'm so excited, I'm gonna display how I did it and you guys please confirm! Thank you for your help!

So basically I worked backwards as #23 sepp2k explained. I was looking for P6, so I replaced all occurrences of n in the fourth rule with 6. The key was to do the calculation AFTERWARDS, but to replace all occurrences of n in the fourth rule FIRST.

[sepp2k]

TechSyndrome, on 20 May 2012 - 10:44 PM, said:

I thought the gentleman who was helping was giving me an alternative method to work backwards. Thanks.

Oh, I am. To make this more clear, let's start with P6 and go all the way down to the bottom:

P₆ = (P_{6 - 3} * P_6-1) + 1

Now 6-3 and 6-1 are easily calculated, so we get:

P₆ = (P₃ * P₅) + 1

Now we only need to know the values of P₃ and P₅. So let's start with P₅:

P₅ = (P_{5 - 3} * P_5-1) + 1
= (P₂ * P₄) + 1

We already have P₂ because that's one of the base cases. We still need P₄, so let's calculate that:

P₄ = (P_{4 - 3} * P_4-1) + 1
= (P₁ * P₃) + 1

So now P3:

P₃ = (P₀ * P₂) + 1

We know P0 and P2, so we get:

P₃ = 2

So now we can go up again to P4:

P₄ = (P₁ * P₃) + 1
= (1*2)+1 = 3

And now P5:

P₅ = (P₂ * P₄) + 1
= (1*3)+1 = 4

And now P6:

P₆ = (P₃ * P₅) + 1
= (2*4)+1 = 9

What we did here basically is to start at the top, then go all the way down to the bottom and then go up again. As I said earlier, this has no advantage over simply starting at the bottom and then going up in this case.

However in cases where we don't need to calculate all the preceding elements to calculate the next one, this approach can save needless calculations.

In fact there are even sequences where an element can depend on other elements that come after it. In those cases the bottom-up approach doesn't work and you actually need to use this approach.

[macosxnerd101]

Also, I'm going to move this to the Computer Science forum since it isn't a Java question.

[TechSyndrome]

sepp2k, on 20 May 2012 - 01:55 PM, said:

TechSyndrome, on 20 May 2012 - 10:44 PM, said:

I thought the gentleman who was helping was giving me an alternative method to work backwards. Thanks.

Oh, I am. To make this more clear, let's start with P6 and go all the way down to the bottom:

P₆ = (P_{6 - 3} * P_6-1) + 1

Now 6-3 and 6-1 are easily calculated, so we get:

P₆ = (P₃ * P₅) + 1

Now we only need to know the values of P₃ and P₅. So let's start with P₅:

P₅ = (P_{5 - 3} * P_5-1) + 1
= (P₂ * P₄) + 1

We already have P₂ because that's one of the base cases. We still need P₄, so let's calculate that:

P₄ = (P_{4 - 3} * P_4-1) + 1
= (P₁ * P₃) + 1

So now P3:

P₃ = (P₀ * P₂) + 1

We know P0 and P2, so we get:

P₃ = 2

So now we can go up again to P4:

P₄ = (P₁ * P₃) + 1
= (1*2)+1 = 3

And now P5:

P₅ = (P₂ * P₄) + 1
= (1*3)+1 = 4

And now P6:

P₆ = (P₃ * P₅) + 1
= (2*4)+1 = 9

What we did here basically is to start at the top, then go all the way down to the bottom and then go up again. As I said earlier, this has no advantage over simply starting at the bottom and then going up in this case.

However in cases where we don't need to calculate all the preceding elements to calculate the next one, this approach can save needless calculations.

In fact there are even sequences where an element can depend on other elements that come after it. In those cases the bottom-up approach doesn't work and you actually need to use this approach.

I just used your bottom up approach in a different question and it worked!!! THANK YOU SO MUCH! I'm gonna read what you've just written right now...I'm so afraid I'm gonna forget this stuff. Amazing that just 1 hour ago I was depressed at not understanding any of this!

macosxnerd101, on 20 May 2012 - 01:57 PM, said:

Also, I'm going to move this to the Computer Science forum since it isn't a Java question.

The second part of this question is related to Java. This is all part of Data Structures and Algorithms in Java. Does that count?

[jon.kiparsky]

The material in Algorithms and Data Structures applies to programming generally, not to any particular language. A linked list is a linked list, no matter what syntax you use to define it for the computer.