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

Line 12: | Line 12: | ||

Probability Theory: | Probability Theory: | ||

- | Let's define a simple experiment as follows: permute the numbers <math>(1,2,3,4)</math>. 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</math>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</math> 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</math> | + | * $X(\{(1, 2, 3, 4)\}) = 0$ |

- | * <math>X(\{(1, 3, 2, 4)\}) = 2</math> | + | * $X(\{(1, 3, 2, 4)\}) = 2$ |

- | * <math>X(\{(4, 3, 2, 1)\}) = 4</math> | + | * $X(\{(4, 3, 2, 1)\}) = 4$ |

- | * <math>X(\{(4, 1, 2, 3)\}) = 4</math> | + | * $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)</math>? | + | # What is the probability $p(X=2)$? |

- | # What is the probability <math>p(X\geq 2)</math>? | + | # What is the probability $p(X\geq 2)$? |

- | # What is the expected value of our random variable <math>X</math> 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</math>. 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</math> and that the running time on that instance is 1 (i.e., <math>T(3)=1</math>). 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. |