Pseudocode recursive function

14,475

Solution 1

For the second question, you could use the law of total probability (transferred to expected values - you possibly have to search for this).

M(a) denotes the number of glasses (as you suggested), E() is the expected value of something. This law of total probability then yields:

E(M(a)) = sum(E(M(a) | b=i) * Pr(b=i), i=1..a-1) =
        = ... =
        = 1/(a-1) * (1+sum(E(M(i)+M(a-i), i=1..a-1)))

As far as I understood, the base case M(1)=0 holds.

If you transform the above recurrence relation and try it out (e.g. in a small python program), you should be able to recognize a simple pattern that possibly can be proven via induction.

Solution 2

The first answer is fine.

The second, however, is not. Consider a=1. Your answer is two glasses or milk, whereas the correct answer is zero. Hint: Try working through some small examples by hand to get a feel for what's going on in the algorithm.

Solution 3

For your first question note that both expressions below are less than a, and recursion stops when a equals 1, and what can you observe about how many times milk() is called? Is it bounded?

b < a
a-b < a
MILK(1) returns (no recursion)

Work out the number of drinks of milk by hand for a couple of values, you will see a pattern. That will help.

Note that the random number generation adds complexity, but ask yourself, is the result any different if you pick b=1, b=2, b=a/2, or b=a-1?

Your answer is correct, but the above should help you explain your reasoning.

Once you have calculated the number of drinks for a couple of calls to MILK(v), you should be able to advance a formula for MILK(v) = formula(v).

Try MILK(3), MILK(4), MILK(5), MILK(9),

Note that Ruby can express your algorithm with little added syntax,

rdm = Random.new
def milk(a)
    if(a==1) then
        print "eat cookie\n";
    else
        print "drink milk\n";
        b = Random.rand(1..a-1)
        print "rand (1,#{a-1}) #{b}\n";
        milk(b)
        milk(a-b)
    end
end
ARGV.each { |argi| milk(argi.to_i); }
Share:
14,475
pyramid
Author by

pyramid

Updated on June 19, 2022

Comments

  • pyramid
    pyramid over 1 year

    I'm studying for my midterm and one of the practise questions asks:

    Consider the recursive pseudo algorithm Milk(a), which takes as an input integer a>=1.

    MILK(a)
        if a = 1;
        then eat cookie;
        else drink glass of milk;
           select a random integer b with 1 <= b <= a-1
           MILK(b);
           MILK(a-b);
        endif
    

    1) Explain why for any integer a>= 1 algorithm MILK(a) terminates

    I think for this one because of the n-1, the possibility for m becomes smaller and smaller for the input into the recursive function MILK(b);, eventually reaching 1 which satisfies condition a = 1; therefore eating a cookie and so terminating the algorithm.

    2) Let M(a) be the amount of glasses of milk you drink when running MILK(a). Determine the exact value of M(a)

    For this one I assume it will be M(a) = a + a, since every time you run it 'a' is the input and adding every input together will give you the total.

    How are my answers looking? Or this completely incorrect. Thank you!

  • pyramid
    pyramid about 10 years
    Thanks, but can I say in B(n) = n + n - 1(total number of ns). So if it's 2 for example, it will be 2+2-2 as n will eventually hit 1? Sorry if my answer is a bit confusing.
  • Mashmagar
    Mashmagar about 10 years
    @pyramid Where did B(n) come from? Is that the same as M(a)?
  • pyramid
    pyramid about 10 years
    Oh yea sorry, I looked at the wrong question. B(n) is the same as M(a). I meant M(a)= a + a -1