Homework Assignment #9.5

To gain experience with convolution. Also to find a specific solution to a recurrence relation and to perform an average-case analysis.

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

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)

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.