You are given n biased coins. Coin i has probability of heads p_i and probabilit

Question

You are given n biased coins. Coin i has probability of heads p_i and probability of tails 1 - p_i, independent of the other coins. Give a dynamic programming algorithm to calculate the probability that if all n coins are tossed, then exactly k heads will be observed. Your input are the quantities n, k, p_1, p_2, ..., p_n, and your algorithm should run in O(nk) time. As an example, if n = 2, p_1 = 0.3, p_2 = 0.6, and k = 1, then the probability is: Pr[One head observed if both coins tossed] = 0.3 times (1 - 0.6) + 0.6 times (1 - 0.3) = 0.54

Explanation / Answer

As in dynamic programming we reuse the result of previous output. So we create a table to use the previous result to calculate current one.

As we can see that nth term is independent of (n-1)th term.

dp[n][k] where dp[i][j] is the getting j in i trials

for i -> 1 to n

for j-> 1 to k

dp[i][j] = dp[i-1][j]*(1 - P[i]) + dp[i-1][j-1]*P[i]

so finaly we will get dp[n][k] that will be out answer.

As we have two for loop first run in n times ans second run in k times.

So time complexity is T(n) = O(n*k).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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