# Homework Assignment #9.5

## Objectives

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

## Exercises

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

### Question 1

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 2

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.

Back to top