Exercise Sheet 4
COMS10007 Algorithms
1 Search in a Sorted Matrix
We are given an n-by-n integer matrix A that is sorted both row- and column-wise, i.e., every row is sorted in non-decreasing order from left to right, and every column is sorted in nondecreasing order from top to bottom. Give a divide-and-conquer algorithm that answers the
question:
“Given an integer x, does A contain x?”
What is the runtime of your algorithm?
2 Maxima of Windows of length n/2
Given is an array A of n positive integers, where n is even. Give an algorithm that outputs an array B of length n/2 such that B[i] = max{A[j] , i ≤ j ≤ i + n/2 − 1}. Can you find an algorithm that runs in time O(n)?
3 Breaking a String
A certain string-processing language allows a programmer to break a string into two pieces. Because this operation copies the string, it costs n time units to break a string of n characters into two pieces. Suppose a programmer wants to break a string into many pieces. The order
in which the breaks occur can affect the total amount of time used. For example, suppose that the programmer wants to break a 20-character string after characters 2, 8, and 10 (numbering the characters in ascending order from the left-hand end, starting from 1). If she programs the breaks to occur in left-to-right order, then the first break costs 20 time units, the second break costs 18 time units, and the third break costs 12 time units, totaling 50 time units. If she programs the breaks to occur in right-to-left order, however, then the first break costs 20 time units, the second break costs 10 time units, and the third break costs 8 time units, totaling 38 time units. In yet another order, she could break first at 8 (costing 20), then break the left piece at 2 (costing 8), and finally the right piece at 10 (costing 12), for a total cost of 40.
Design an algorithm that, given the number of characters after which to break, determines a least-cost way to sequence those breaks. More formally, given a string S with n characters and an array L[1..m] containing the break points, compute the lowest cost for a sequence of breaks, along with a sequence of breaks that achieves this cost.
4 Image Compression by Seam Carving
We are given a color picture of an m×n array A[1..m, 1..n] of pixels, where each pixel specifies a triple of red, green, and blue (RGB) intensities. Suppose that we wish to compress this picture slightly. Specifically, we wish to remove one pixel from each of the m rows, so that the whole picture becomes one pixel narrower. To avoid disturbing visual effects, however, we require that the pixels removed in two adjacent rows be in the same or adjacent columns; the pixels removed form a “seam” from the top row to the bottom row where successive pixels in the seam are adjacent vertically or diagonally.
1. Show that the number of such possible seams grows at least exponentially in m, assuming that n ≥ 2.
2. Suppose now that along with each pixel A[i, j], we have calculated a real-valued disruption measure d[i, j], indicating how disruptive it would be to remove pixel A[i, j]. Intuitively, the lower a pixel’s disruption measure, the more similar the pixel is to its neighbors. Suppose further that we define the disruption of a seam to be the sum of the disruption measures of its pixels.
Give an algorithm to find a seam with the lowest disruption measure. How efficient is your algorithm?