Complete the following exercises. Whenever you propose an algorithm, make
sure to prove its correctness and analyze its efficiency.
A real polynomial of degree $n$ is a function of the form
$f(x) = a_n x^n + \cdots + a_1 x + a_0$, where $a_n, \ldots, a_1, a_0$ are
real numbers. In computational situations, such a polynomial is represented
by a sequence of its coefficients $(a_0, a_1, \ldots, a_n)$. Assuming that
any two real numbers can be added/multiplied in $O(1)$ time, design an
$o(n^2)$-time algorithm to compute, given two real polynomials $f(x)$ and
$g(x)$ both of degree $n$, the product $h(x) = f(x)g(x)$ (for the definition
of the $o(\cdot)$ notation, see Homework 2,
Exercise 2(b)). Your algorithm should return $h(x)$ as a sequence of the
coefficients of $h(x)$. Your algorithm should not be based on the
Fast Fourier Transform (FFT) technique.
pp. 313, 314, Exercise 2.
Let $S = (s_1, \ldots, s_n)$ be a sequence of integers and
$S' = (s'_1, \ldots, s'_m)$ be a subsequence of $S$ (that is, there is a
sequence of integers $i_1 < \cdots < i_m$ such that $s'_j = s_{i_j}$ for
$j = 1, \ldots, m$). We say $S'$ is an increasing subsequence if
$s'_1 \le \cdots \le s'_m$. For example, if $S = (8, 5, 2, 7, 2, 3, 6, 9)$,
then $(5, 7, 9)$ as well as $(2, 2, 6, 9)$ are increasing subsequences of
$S$. Design an $O(n^2)$-time algorithm to find, given a sequence $S$ of $n$
integers, an increasing subsequence of $S$ of the longest length.
Plagiarism and academic dishonesty.
Remember, under any circumstance, you must not copy part or all of another's
work and present it as your own. For more details, read
our course policy on plagiarism and academic
dishonesty.
