CS 1510 Midterm 1

Fall 1999

1.

(40 points) The first problem that we considered this semester was the following one:

INPUT: A collection of intervals $C = \{(a_1, b_1), \ldots, (a_n, b_n) \}$ over the real line.

OUTPUT: A maximum cardinality collection of disjoint intervals.

We consider greedy algorithms for solving this problem that are of the following form:

1. Pick the interval I from the remaining intervals in C, and add I to the solution set S.

2. Remove I, and any intervals that overlap with I, from C.

3. If C is not yet empty, go to step 1.

One can get different greedy algorithms depending on how I is selected. For each of the following method of selecting I, prove or disprove the that resulting greedy algorithm correctly solves the problem.

(a)

Pick I to be the interval (a_i, b_i) that minimizes b_i, that is, pick I to be the interval with the leftmost right endpoint. Ties may be broken arbitrarily.

(b)

Pick I to be the interval (a_i, b_i) that minimizes b_i - a_i, that is, pick I to be the shortest interval. Ties may be broken arbitrarily.

(c)

Pick I to be the interval (a_i, b_i) that intersects the least number of other intervals currently in C. Ties may be broken arbitrarily.

2.

(20 points) We consider the problem of computing the longest common subsequence of two sequences $A=a_1, \ldots, a_m$ and $B=b_1, \ldots, b_n$. Let T(i,j) be the length of the longest common subsequence of $a_1, \ldots, a_i$ and $b_1, \ldots, b_j$.

(a)

Write a recursive function to compute T(i, j) in the naive way. Don't forget the base case(s).

(b)

Show that if you implement this recursion directly in say the C programming language, that the program could use time that is exponential in n.

(c)

Write iterative array based code to compute T(m, n) that runs in O(n²) time.

(d)

Write code to actually find the longest common subsequence from your array.

3.

(20 points) Consider the following problem. The input to this problem consists three points s₁, s₂ and s₃ in the Euclidean plane that represent the starting locations of three taxis and a list $r_1, r_2, \ldots, r_m$ of m requests, where each request is a point in the plane. These requests must be serviced in order, i.e. request r₁ must be handled before request r₂, which must be serviced before request r₃, etc. If the taxi cabs are currently at points v₁, v₂ and v₃, then in response to a request r_i one of the three taxi cabs must move to point r_i; If the first taxi moves then the taxi company incurs a cost of d(v₁, r_i), of the distance between v₁ and r_i, if the second taxi moves then the taxi company incurs a cost of d(v₂, r_i), the distance between v₂ and r_i, and if the third taxi moves then the taxi company incurs a cost of (v₃, r_i) the distance between v₃ and r_i, The taxi company's problem is to compute the cost of the cheapest schedule for handling these requests. Give an O(n³) time algorithm that solves this problem.

Note that this is identical to the taxi cab homework problem except that we now assume three taxis instead of two taxis.

4.

(20 points) Consider the following problem. The input to this problem of consists of a positive integer k, and a sequence $A = a_1, \ldots, a_n$ of integers. The output should be the longest k-slowly increasing subsequence of A. A sequence $B = b_1, \ldots, b_m$ is is k-slowly increasing if $b_{i+1} - k \le b_i < b_{i+1}$ for $1 \le i \le m-1$, that is, if B increases by some number between 1 and k on each step. Give an O(n²) time algorithm that solves this problem.