##### Differences

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

 cs-312:hw9 [2014/12/31 15:59]ringger created cs-312:hw9 [2014/12/31 16:19] (current)ringger 2014/12/31 16:19 ringger 2014/12/31 15:59 ringger created 2014/12/31 16:19 ringger 2014/12/31 15:59 ringger created Line 12: Line 12: Probability Theory: Probability Theory: - Let's define a simple experiment as follows: ​ permute the numbers ​<​math>​(1,2,3,4)​.  Each sample (outcome) is such a permutation. + Let's define a simple experiment as follows: ​ permute the numbers ​$(1,2,3,4)$.  Each sample (outcome) is such a permutation. - Now define a random variable ​<​math>​X​which assigns to each sample the number of elements that are not in their correct (sorted) position. ​ For example, for the following samples, ​<​math>​X ​assigns the indicated values: + Now define a random variable ​$X$which assigns to each sample the number of elements that are not in their correct (sorted) position. ​ For example, for the following samples, ​$X$ assigns the indicated values: - * <​math>​X(\{(1, 2, 3, 4)\}) = 0​ + * $X(\{(1, 2, 3, 4)\}) = 0$ - * <​math>​X(\{(1, 3, 2, 4)\}) = 2 ​ + * $X(\{(1, 3, 2, 4)\}) = 2$ - * <​math>​X(\{(4, 3, 2, 1)\}) = 4 ​ + * $X(\{(4, 3, 2, 1)\}) = 4$ - * <​math>​X(\{(4, 1, 2, 3)\}) = 4 ​ + * $X(\{(4, 1, 2, 3)\}) = 4$ Also, assume a uniform distribution over samples. ​ (Each question scored individually.) Also, assume a uniform distribution over samples. ​ (Each question scored individually.) # How many samples are in the sample space? # How many samples are in the sample space? - # What is the probability ​<​math>​p(X=2)​? + # What is the probability ​$p(X=2)$? - # What is the probability ​<​math>​p(X\geq 2)​? + # What is the probability ​$p(X\geq 2)$? - # What is the expected value of our random variable ​<​math>​X ​with respect to this uniform distribution?​ + # What is the expected value of our random variable ​$X$ with respect to this uniform distribution?​ ===Question 5=== ===Question 5=== Line 35: Line 35: Recurrence Relations: Recurrence Relations: - Suppose an algorithm has running time described by the following recurrence relation: ​<​math>​T(n) = 4 T(n/3) + n^3​.  Use the theory of recurrence relations to solve this recurrence relation. + Suppose an algorithm has running time described by the following recurrence relation: ​$T(n) = 4 T(n/3) + n^3$.  Use the theory of recurrence relations to solve this recurrence relation. * Come up with the general solution. * Come up with the general solution. - * Assume that the smallest instance of the problem solved by this algorithm has size <​math>​n=3 ​and that the running time on that instance is 1 (i.e., ​<​math>​T(3)=1​).  Find the specific solution to the recurrence given this initial condition. + * Assume that the smallest instance of the problem solved by this algorithm has size $n=3$ and that the running time on that instance is 1 (i.e., ​$T(3)=1$).  Find the specific solution to the recurrence given this initial condition. 