**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.)

How many samples are in the sample space?

What is the probability <math>p(X=2)</math>?

What is the probability <math>p(X\geq 2)</math>?

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.

Back to top