**This is an old revision of the document!**


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 <math>(1,2,3,4)</math>. 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:

  • <math>X(\{(1, 2, 3, 4)\}) = 0</math>
  • <math>X(\{(1, 3, 2, 4)\}) = 2</math>
  • <math>X(\{(4, 3, 2, 1)\}) = 4</math>
  • <math>X(\{(4, 1, 2, 3)\}) = 4</math>

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 <math>p(X=2)</math>?
  3. What is the probability <math>p(X\geq 2)</math>?
  4. What is the expected value of our random variable <math>X</math> 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: <math>T(n) = 4 T(n/3) + n^3</math>. 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 <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.
cs-312/hw9.1420066740.txt.gz · Last modified: 2014/12/31 15:59 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