1. Algorithms on Sequences

Part (a)

Sort the sequence of n elements in increasing order. Then,

for i = 1 to n/2
S'[i] = S[i] + S[n-i+1]
return S'

Running time: sorting takes O(n log n) and the for loop takes O(n) time. Thus, the running time of the algorithm is O(n log n).

Part (b)

To show that the algorithm minimizes the maximum sum we will use contradiction. Let a₁,a₂,...,a_n be the elements of S and let a_i+ a_n-i+1 be the maximum value computed by our algorithm.

First observe that if the sum a_i+ a_j with i >= n/2 and j >= n/2 (i not equal to j) will only increase the maximum. Thus, the maximum is the sum of two numbers a_i+ a_j with i <= n/2 and j > n/2.

If our algorithm is not correct, then it means that there is some other sum a_j+ a_n-j+1 in our sequence S' such that each of the sums a_i+ a_n-j+1 and a_j+ a_n-i+1 is less than our computed maximum a_i+ a_n-i+1. Without loss of generality assume that j > i, which implies that a_j> a_i and a_n-i+1 < a_j+ a_n-j+1. But a_j+ a_n-i+1 < a_i+ a_n-i+1 implies that a_j < a_i, which is a contradiction.

2. Edit Distance between Strings

The dynamic programming solution to the problem of computing the edit distance between two strings A and B finds the solution to subproblems and uses these solutions to find an optimal solution to the problem. The algorithm stores the solution to the subproblems in an m by n array of integers, so that array element c[i,j] is the edit distance between the two strings (a₁,a₂,...,a_i) and (b₁,b₂,...,b_j). In particular, the array element c[i,m] is the edit distance between (a₁,a₂,...,a_i) and (b₁,b₂,...,b_m).

Now, let us compute the edit distance between (a_n,a_n-1,...,a₁) and (b_m,b_m-1,...,b₁). The value of the solution to this modfied input is equal to the edit distance between (a₁,a₂,...,a_n) and (b₁,b₂,...,b_m). Hence, element c'[i,m] of the new table is the edit distance between (a_i,a₂,...,a_n) and (b₁,b₂,...,b_n). Therefore, to compute the edit distance between B and A[i], we first compute the edit distance between (a_n,a_n-1,...,a₁) and (b_m,b_m-1,...,b₁); this will take O(n²) time. We then find the minimum value of the last row of the table in linear time. This will make the total running time of the algorithm equal to O(n²).

3. Graph Embeddability

Part (a)

We show this by using a mapping known as stereographic projection. Consider a spherical surface S, touching a plane P at the point x. The point y (called the point of projection) is on S and diametrically opposite x. Any point z on P can be projected uniquely onto S at z' by making y,z and z' collinear. In this way any graph embedded in P can be projected onto S. Conversely, we can project any graph embedded in s onto P, choosing y so as not ot lie on any vertex or edge of the graph.

Part (b)

Any face of G is defined by the path which forms its boundary. Any such path, T, identified in a particular plar representation P of G, may be made to define the exterior face of a different planar representation P' as follows. We form, as we can according to the previous theorem, a sperical embedding P'' of P. P' is then formed by projecting P'' onto the plane in such a way that the point of projection lies in the face defined by the image of T on the sphere.