A Looping Problem

[e(ho0n3]

How many times does the print statement execute?

 

for i[1] = 1 to n do
 for i[2] = 1 to min(i[1], n - 1) do
   for i[3] = 1 to min(i[2], n - 2) do
     .
      .
       for i[n - 1] = 1 to min(i[n - 2], 2) do
         for i[n] = 1 to 1 do
           print i[1], i[2], ..., i[n]

 

I get a headache just from looking at it...

[pulkit]

If [MATH]fib(n)[/MATH] is the [MATH]n^{th}[/MATH] fibonacci number where the recurssion [MATH]fib(n)=fib(n-1)+fib(n-2)[/MATH] holds. Also you take [MATH]fib(1)=fib(2)=1[/MATH].

Next if given [MATH]n[/MATH], the number of times the loop runs is [MATH]P(n)[/MATH]..........

 

Your solution is [MATH]P(n)=fib(2n-1)[/MATH]

 

I can't write the full solution using LaTex due to obvious reasons of it being slightly cumbersome, but still if you want I can try and explain it sometime later.......

Nice question though, took me almost half an hour to solve it.

[e(ho0n3]

I would need to see your explanation since that is not the answer (at least according to my book). I know what the answer is, although I don't know how to derive it myself.

[pulkit]

Can you atleast tell me if I came close, because I don't wanna miss out just because of an odd +/- 1. I am pretty sure of the method I used, I'll try and put up the solution.......

[pulkit]

I got the following reccursion :-

 

[MATH]P(n)=\Sigma_{i=1}^{n-1}P(i) + P(n-1)[/MATH]

 

Along with base cases of [MATH]P(1)=1[/MATH] and [MATH]P(2)=2[/MATH]

[e(ho0n3]

I got the following reccursion :-

 

[MATH]P(n)=\Sigma_{i=1}^{n-1}P(i) + P(n-1)[/MATH]

 

Along with base cases of [MATH]P(1)=1[/MATH] and [MATH]P(2)=2[/MATH]

I think the problem stems from you definition of P(n). What exactly is your definition? I have something similar to what you have (and ended up with your exact same solution, i.e. P(n) = f(2n - 1)), but then I realized I made a mistake, that being the definition of P(n).

 

Note there are n for loops, with the top for loop going from 1 to n. This is different from n for loops going from 1 to k, k < n, which is still different from k for loops, k < n, the top for loop going from 1 to n.

 

So let me define P(a,b) as the number of times the print statement is executed given a for loops, the top for loop executing from 1 to b. I then get the following recurrence:

 

P(n,n) = 2P(n-1,n-1) + P(n-1,n-2) + P(n-1,n-3) + ... + P(n-1,1)

 

This is as far as I can go since I don't know how to solve such a recurrence relation. Maybe you can shine some light on this.

[pulkit]

I defined [MATH]P(n)[/MATH] as the number of print statements executed in n loops, with the top most going from 1 to n. Alternatively, it is the required answer in the case when you have n loops. The fact is that whenever there shall be n loops the outer most will go from 1 to n. There is no need to define it as [MATH]P(n,n)[/MATH] because all the terms that come out in the recurrance you mentioned can be reduced some [MATH]P(i)[/MATH]. In fact, [MATH]P(n-1,i)=P(i)[/MATH] for [MATH]i \leq n-1[/MATH] .

[YT2095]

E1 (echo-one) have you actualy tried to run it on a computer and used the "Trace" command to find out?

[pulkit]

That'll not be the right way to do it. Thats the worst way to go about solving theoretical computer science problems, you never learn and hardly ever get anywhere

[YT2095]

so are you`re saying it wouldn`t work and give you your answer?

[pulkit]

It won't simply because you can't write a program with a generic number 'n' of loops. You would need to keep modifying the number of loops which would be very tedious and then need to figure out a pattern in the numbers that you get out......a hard task.

[pulkit]

And most importantly, you would have no concrete proof to support your claim.

[YT2095]

get a printout!

[e(ho0n3]

I defined [MATH]P(n)[/MATH] as the number of print statements executed in n loops, with the top most going from 1 to n. Alternatively, it is the required answer in the case when you have n loops. The fact is that whenever there shall be n loops the outer most will go from 1 to n. There is no need to define it as [MATH]P(n,n)[/MATH] because all the terms that come out in the recurrance you mentioned can be reduced some [MATH]P(i)[/MATH]. In fact, [MATH]P(n-1,i)=P(i)[/MATH] for [MATH]i \leq n-1[/MATH'] .

Let's look at the second for loop, i.e. then one that goes from 1 to min(i[1], n - 1). When the i[1] = 1 (first iteration), the second loop goes from 1 to 1. This is your P(1). Then P(1) is "number of print statements executed in 1 loop, with the top most going from 1 to 1". This is clearly not true. It should be "the number of print statements executed in n - 1 for loops with the top most going from 1 to 1", which is just P(n-1,1).

 

For i[1] = 2 (next iteration), the second loop goes from 1 to 2. This is your P(2). Then P(2) is "number of print statements executed in 2 loops, with the top most going from 1 to 2". This is clearly not true either. It should be "the number of print statements executed in n - 1 for loops with the top most going from 1 to 2", which is just P(n-1,2). And so on.

 

Convinced?

 

E1 (echo-one) have you actualy tried to run it on a computer and used the "Trace" command to find out?

I'm supposed to solve this problem without the aid of a computer. As I said before, I know what the answer is; I just don't know how to derive it. The pattern isn't "pretty" so it would be very, very hard to guess from looking at a couple of numbers in the sequence.

[pulkit]

Let's look at the second for loop, i.e. then one that goes from 1 to min(i[1], n - 1). When the i[1] = 1 (first iteration), the second loop goes from 1 to 1. This is your P(1). Then P(1) is "number of print statements executed in 1 loop, with the top most going from 1 to 1". This is clearly not true. It should be "the number of print statements executed in n - 1 for loops with the top most going from 1 to 1", which is just P(n-1,1).

When i[2] goes from 1 to 1, all subsequent loops will also go from 1 to 1. For example, i[3] will go to min{i[2], n-2} which is 1, similarly i[4] will also go to 1. As a result the print statement is executed exactly once hence [MATH]P(1)=P(n-1,1)=1[/MATH]

 

Similarly if you work out for the case when the outermost loop reaches its 2nd iteration, then i[2] will go from 1 to 2. Again if you try to work out you'll see that from the 4th loop inwards all loops will only ever go from 1 to 1 making them redundant. As a result you can reduce the problem to just the loop numbers 2 and 3, which is just the case of P(2).

 

You can discuss generally and show [MATH]P(i)=P(n-1,i)[/MATH]

[e(ho0n3]

OK, I'm convinced (I just did a proof by induction and it worked). But anyways, your solution (the one with the fibonacci equation) is wrong. I suggest we start looking for another route towards solving this. I was thinking of looking at the number generated by the print statement in each iteration.

 

In general we have that n ≥ i[1], n - 1 ≥ i[2], ... 1 ≥ i[n], and i[k] > 0 for k = 1, ..., n. Hmm...this is to ugly (and tricky). I'm becomming exasperated.

 

OK. We have that:

 

[math]P(n) = P(n-1) + \sum_{i=1}^{n-1}P(i)[/math]

[math]P(n-1) = P(n-2) + \sum_{i=1}^{n-2}P(i)[/math]

 

Then,

 

[math]P(n) - P(n-1) = P(n-1) + \sum_{i=1}^{n-1}P(i) - P(n-2) - \sum_{i=1}^{n-2}P(i)[/math]

 

Simplifying and solving for P(n) gives (and this seems strange to me),

 

[math]P(n) = 3P(n-1) - P(n-2)[/math]

 

This looks like the fibonacci recurrence doesn't it! Unfortunately this is all bogus (it doesn't work for n = 4).

[pulkit]

What doesn't work for n=4 ?

Atleast if I put in [MATH]fib(2n-1)=P(n)[/MATH] and [MATH]n=4[/MATH] then I get :-

[MATH]fib(2*4-1)=3*fib(2*3-1)-fib(2*2-1)[/MATH]

[MATH]fib(7)=fib(5)*3 - fib(3)[/MATH]

[MATH] fib(7)=13 \ldots fib(5)=5 \ldots fib(3)=2 [/MATH]

So it holds !

[e(ho0n3]

The problem is P(4) shouldn't be 13, it should be 14. Hence my statement.

[pulkit]

Can you provide the correct answer ?

[e(ho0n3]

P(n) is equal to the nth Catalan number. If you don't believe that P(4) is 14, here is printout of a program a made in perl for n = 4:

 

1 1 1 1

2 1 1 1

2 2 1 1

2 2 2 1

3 1 1 1

3 2 1 1

3 2 2 1

3 3 1 1

3 3 2 1

4 1 1 1

4 2 1 1

4 2 2 1

4 3 1 1

4 3 2 1

 

There are 14 number combinations above.

[pulkit]

I am unfamiliar with catalan numbers....what are they ?

[e(ho0n3]

See here: http://mathworld.wolfram.com/CatalanNumber.html.

[pulkit]

Wow ! These are quite a series of numbers, and scale a lot lot more steeply than fibonaccis.

Have you yet wprked out an explicit solution to this problem ? or just one using induction ?

[e(ho0n3]

The solutiion I gave you is explicit. What I would like to do is derive the solution.