Chapter 15, Problem 8P

(a)

Program Plan Intro

To show the number of possible seams grows exponential.

Explanation of Solution

Consider an array A for the compressing the picture so it requires to remove the pixels in the two adjacent rows in the same or adjacent column and the pixels are removed forms a seam from the top row to the bottom row.

Suppose $n>1$ for the seam algorithm the choice of pixel at any row have at least 2 choices of the pixels to the next row added to the seam.

The total area enclosed by the seams is order of m and it has two choices for every area of m so the total probability of the total number of seams can be varies from 2^m to 2^m -1.

Hence, the total number of possibilities of seams is bounded by $O(2^m)$ so the grow of number of seam will be exponentially.

(b)

Program Plan Intro

To give an algorithm that finds a seam with lowest disruption measure.

Explanation of Solution

The algorithm to find a seam with the lowest disruption is given below:

Seam(A)

Initialize tables $D[\mathrm{1.....}m,\mathrm{1.....}n]$ of zeros and $S[\mathrm{1....}m,\mathrm{1....}n]$ of empty lists.

For $i=1$ to n do

  $\begin{array}{l}S[1,i]=(1,i).\\ D[1,i]=d1i.\end{array}$

End for.

for $i=2$ to m do

for $j=1$ to n do

If $j==1$ then

If $D[i,j]<D[i-1,j+1]$ then

  $\begin{array}{l}D[i,j]=D[i-1,j]+d.\\ S[i,j]=S[i-1,j].insert(i,j).\end{array}$

End if.

Else

  $\begin{array}{l}D[i,j]=D[i-1,j+1]+d.\\ S[i,j]=S[i-1,j+1].insert(i,j).\end{array}$

End if.

Else if( $j==n$ ) then

If() then

  $\begin{array}{l}D[i,j]=D[i-1,j-1]+d.\\ S[i,j]=S[i-1,j-1].insert(i,j).\end{array}$

End if.

End if.

  $x=MIN(D[i-1,j-1],D[i-1,j],D[i-1,j+1])$

  $\begin{array}{l}D[i,j]=D[i-1,j+x].\\ S[i,j]=S[i-1,j+x].insert(i,j).\end{array}$

End for.

End for.

  $q=1.$

For $j=1$ to n do

If $D[m,j]<D[m,q]$ then

  $q=j$ .

End if.

End for.

Print the list $S[m,q]$ .

End.

The algorithm compressing the picture so it requires to removes the pixels in the two adjacent rows in the same or adjacent column and the pixels are removed forms a seam from the top row to the bottom row.

This algorithm takes the array A as input and the cases to insert pixel according to the defined condition and return the list of seam as $S[m,q]$ .