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.
cs-312/hw9.5.txt · Last modified: 2014/12/31 23:24 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