##### Differences

This shows you the differences between two versions of the page.

 cs-312:hw8 [2014/12/31 15:58]ringger created cs-312:hw8 [2014/12/31 16:22]ringger 2014/12/31 16:22 ringger 2014/12/31 15:58 ringger created 2014/12/31 16:22 ringger 2014/12/31 15:58 ringger created Line 1: Line 1: - __NOTOC__ + = Homework Assignment #8 = - <​big>'''​Homework Assignment #8'''​ + == Objective == == Objective == Line 17: Line 16: Let's define a simple experiment as follows: ​ Roll two dice.  Each sample (outcome) is an ordered pair of die faces. Let's define a simple experiment as follows: ​ Roll two dice.  Each sample (outcome) is an ordered pair of die faces. * How many samples are in the sample space? * How many samples are in the sample space? - Now define a random variable ​<​math>​X​which assigns to each sample the total number of dots on the faces of the two dice.  Also, assume a uniform distribution over samples. + Now define a random variable ​$X$which assigns to each sample the total number of dots on the faces of the two dice.  Also, assume a uniform distribution over samples. - * What is the probability ​<​math>​p(X=7) ​with these fair dice? + * What is the probability ​$p(X=7)$ with these fair dice? * What is the probability of rolling the outcome "snake eyes" (two ones) with these fair dice? * What is the probability of rolling the outcome "snake eyes" (two ones) with these fair dice? - * What is the expected value of our random variable ​<​math>​X ​with respect to this fair distribution?​ + * What is the expected value of our random variable ​$X$ with respect to this fair distribution?​ ===Question 2=== ===Question 2=== Probability Theory: Probability Theory: - Let's define another simple experiment involving rolling two dice as follows: again, each sample (outcome) is an ordered pair of die faces, and we define a random variable ​<​math>​X​which assigns to each sample the total number of dots on the faces of the two dice.  This time assume that the dice are "​loaded"​ (in other words, not fair) and that for each die the probability of rolling a 1 is 1/4, while the other outcomes for each die share the remaining 3/4 probability mass equally. + Let's define another simple experiment involving rolling two dice as follows: again, each sample (outcome) is an ordered pair of die faces, and we define a random variable ​$X$which assigns to each sample the total number of dots on the faces of the two dice.  This time assume that the dice are "​loaded"​ (in other words, not fair) and that for each die the probability of rolling a 1 is 1/4, while the other outcomes for each die share the remaining 3/4 probability mass equally. - * What is the probability ​<​math>​p(X=7) ​with these loaded dice? + * What is the probability ​$p(X=7)$ with these loaded dice? * What is the probability of rolling the outcome "snake eyes" (two ones) with these loaded dice? * What is the probability of rolling the outcome "snake eyes" (two ones) with these loaded dice? - * What is the expected value of our random variable ​<​math>​X ​with respect to this unfair distribution?​ + * What is the expected value of our random variable ​$X$ with respect to this unfair distribution?​ ===Question 3=== ===Question 3=== Recurrence Relations: Recurrence Relations: - Suppose an algorithm has running time described by the following recurrence relation: ​<​math>​T(n) = 3 T(n/4) + n^2​.  Use the theory of recurrence relations to solve this recurrence relation. ​ Come up with the general solution and then place it in an asymptotic order of growth. + Suppose an algorithm has running time described by the following recurrence relation: ​$T(n) = 3 T(n/4) + n^2$.  Use the theory of recurrence relations to solve this recurrence relation. ​ Come up with the general solution and then place it in an asymptotic order of growth. 