There are two teams A and B playing against each other to see who will win n gam

Question

There are two teams A and B playing against each other to see who will win n games first. A and B are equally competent. Therefore, each team has a 50% chance of winning any particular game. Suppose they have already played x + y games, of which A has won x and B has won y games, respectively. Give an algorithm to compute the probability that A will go on to win the match. What's the worst-case time complexity of your algorithm? For instance, if x = n - 1 and y = n - 3 then the probability that A will win the match is 7/8, since it must win any of the next three games.

Explanation / Answer

We can use Dynamic programming or divide and conquer approach, but dynamic programming is quicker and more efficient. below is the algorithm.

We adopt iterative method :

function series (n, p)

            int P[n, n];

            int p=1, q= 1;

            int s;

           

for (s=1;s<=n; s++){                           /* fill top left to diagonal*/

                        P [0][s]= 1;

                        P [s][0]= 1;

                        for (k=1;k<=s-1;k++){

                                    P[k] [s-k] = p* P[k-1] [s-k] + q* P[k] [s-k-1];

}

}

for (s=1;s<=n; s++){               /* Fill from below main diagonal to bottom right*/

                        for (k=0;k<=n-s; k++){

                                    P [s+ k] [n-k]= p*P[s+k-1] [n-k]+q*P[s+ k] [n-k-1];

}

}

return P [n] [n];

The program fills array of size n*n and hence execution time is O(n^2).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.