Differences

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

Link to this comparison view

cs-312:hw9 [2014/12/31 22:59]
ringger created
cs-312:hw9 [2014/12/31 23: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, ​$Xassigns 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 ​$Xwith 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=3and 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.
  
cs-312/hw9.txt · Last modified: 2014/12/31 23:19 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0