Homework Assignment #9

Objective

To gain more experience with probability theory, to gain experience with convolution, and to practice working with recurrence relations.

Exercises

Show all work. i.e., justify your answers.

Questions 1-4

Probability Theory:

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

  • $X(\{(1, 2, 3, 4)\}) = 0$
  • $X(\{(1, 3, 2, 4)\}) = 2$
  • $X(\{(4, 3, 2, 1)\}) = 4$
  • $X(\{(4, 1, 2, 3)\}) = 4$

Also, assume a uniform distribution over samples. (Each question scored individually.)

  1. How many samples are in the sample space?
  2. What is the probability $p(X=2)$?
  3. What is the probability $p(X\geq 2)$?
  4. What is the expected value of our random variable $X$ with respect to this uniform distribution?

Question 5

Convolution:

Convolve these two sequences (signals) A and B to produce a new third sequence (signal) C:

  • A: (0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0)
  • B: (0, 1, 1, 0)

Question 6

Recurrence Relations:

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