Algorithms A sequence of positive integers $\vec{{\bf a}} = (a_1,a_2\ldots a_n)$ is called a non-decreasing sequence if $a_1 \leq a_2 \leq \ldots \leq a_n$. For two positive integer sequences $\vec{{\bf a}} = (a_1,a_2\ldots a_n)$ and $\vec{{\bf b}} = (b_1,b_2\ldots b_n)$ we say that $\vec{{\bf b}}$ dominates $\vec{{\bf a}}$ if $\forall{i},\, 1 \leq i \leq n,\, b_i \geq a_i$. For a positive integer sequence $\vec{{\bf a}}$ we define count( $\vec{{\bf a}}$) as the number of different integers in $\vec{{\bf a}}$, i.e.,

count( $\vec{{\bf a}}$) = $\vert\{a_i \vert i=1,2\ldots n\}\vert$.

For a positive integer sequence $\vec{{\bf a}}$ we define weight( $\vec{{\bf a}}$) as the sum of all the elements of the sequence i.e.,

weight( $\vec{{\bf a}}$) = $\Sigma_{i=1}^n a_i$.

The goal of this problem is to design an efficient algorithm that given a positive non-decreasing integer sequence $\vec{{\bf a}}$ and an integer k finds a minimum weight integer sequence $\vec{{\bf b}}$ that satisfies:

• $\vec{{\bf b}}$ dominates $\vec{{\bf a}}$
• count( $\vec{{\bf b}}$) $\leq k$.

This problem has four parts:

(i)

Let $\vec{{\bf a}} = (a_1,a_2\ldots a_n)$ be a positive non-decreasing integer sequence.

(a)

Find a minimum weight integer sequence $\vec{{\bf b}}$ such that $\vec{{\bf b}}$ dominates $\vec{{\bf a}}$ and count( $\vec{{\bf b}}$) $\leq 1$. What is weight( $\vec{{\bf b}}$)? 7 pts

(b)

Find a minimum weight integer sequence $\vec{{\bf b}}$ such that $\vec{{\bf b}}$ dominates $\vec{{\bf a}}$ and count( $\vec{{\bf b}}$) $\leq n$. What is weight( $\vec{{\bf b}}$)? 8 pts

(ii)

Let $\vec{{\bf a}} = (2\,\, 5\,\, 6\,\, 11\,\, 13\,\, 22\,\, 22\,\, 28)$. Find a minimum weight integer sequence $\vec{{\bf b}}$ such that count( $\vec{{\bf b}}$) $\leq 3$ and $\vec{{\bf b}}$ dominates $\vec{{\bf a}}$. What is weight( $\vec{{\bf b}}$)? No justification is needed as to why your answer is indeed correct. 20 pts

(iii)

For a positive non-decreasing integer sequence $\vec{{\bf a}} = (a_1,a_2\ldots a_n)$, let C(i,j) denote the weight of a minimum weight sequence that dominates the sub-sequence $(a_1,a_2\ldots a_i)$ and has count at most j. Derive a recurrence relation for C(i,j). 30 pts

(iv)

Give an efficient (polynomial-time) algorithm that given a non-decreasing integer sequence $\vec{{\bf a}}$ and an integer k finds a minimum weight integer sequence $\vec{{\bf b}}$ that dominates $\vec{{\bf a}}$ and satisfies count( $\vec{{\bf b}}$) $\leq k$. Analyse the worst-case running time of your algorithm.

35 pts