Hey! I\'m having a bit of trouble with this question, I\'m kinda confused on the
ID: 648941 • Letter: H
Question
Hey! I'm having a bit of trouble with this question, I'm kinda confused on the dynamic programing aspect of the problem and the time complexity associated with it.
A number of sports decide championships based on multigame series: two teams play until one wins k games; without ties, such a series can last for 2k ? 1 games (in professional basketball, for example, the final series is best of 7: the first team winning 4 games wins.) Suppose we have 2 teams (X and Y) in a series, and the probability of X winning a game is the same for each game, and equal to p. Allowing no ties, the probability of Y winning is therefore always 1 ? p. Let W(i, j) be the probability of X winning the series when X needs to win i games to win the series and Y needs to win j games to win the series.
(a) Set up a recurrence relation for W(i, j) that would allow you to use dynamic programming to solve this problem.
(b) Find the probability of team X winning a seven-game series if the probability of X winning a game is 0.4.
(c) Write the pseudocode for a dynamic programming algorithm to solve this problem, and give its time complexity.
Explanation / Answer
Dynamic programming solution
a) Draw diagram of (i,j) plane
Boundary cases are
W[i,0] = 0 for i>=1
W[i,<0] = infinity for i>=1
W[0,j] = infinity for j>=1
Domain of dependence for (i,j) is contained in rectangle
Scan by rows, from left to right
Pseudocode
games(N) {
for i = 1 to n=# of denominations {
c[i,0] = 0
for j = -1 downto d[n] {
W[i,j] = infinity
}
}
for j = 1 to N=target quantity {
W[0,j] = infinity
}
for i = 1 to n {
for j = 1 to N {
W[i,j] = min( W[i-1,j], 1 + W[i,j-d[i]] )
}
}
}
b.
C(7,7) (0.4)^7=1*1.6384*10^-3=1.6384*10^-3