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 |
||
---|---|---|---|

Line 1: | Line 1: | ||

- | __NOTOC__ | + | = Homework Assignment #8 = |

- | <big>'''Homework Assignment #8'''</big> | + | |

== 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</math>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)</math> 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</math> 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</math>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)</math> 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</math> 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</math>. 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. |