Question1:

For bit stringsX=x1: : : xm; Y=y1: : : ynandZ=z1: : : zm+n, we say thatZis an interleavingof X and Y if it can be obtained by interleaving the bits in X and Y in a way that maintains the left-to-right order of the bits in X and Y . For example, if X = 1101 and Y = 01 then x1x2y1x3y2x4 = 110011 is an interleaving of X and Y . Give the most e cient algorithm you can

to    determine if Z is an interleaving of X and Y .

Question2:

Consider a modification to the activity selection problem in which each activity ai has, in addition to a start and finish time, a value vi. The objective is no longer to maximize the number of activities scheduled, but instead to maximize the total value of the activities scheduled. That is, we wish to choose a set A of compatible activities such that is maximized. Give a polynomial-time algorithm for this problem.

Question3:

Consider a grid of sizen m(nrows,mcolumns). Each cell in the grid has either an x’ or an’o’. We like to find the largest square (in terms of area) in this grid, in which all the cells contain an x’ (hint: Design a dynamic programming solution for this problem. Consider the function C(i; j) which represents the area of the largest square, where (i; j) cell is the bottom-right-most corner

cell of that square.)

Question4:

Describe an efficient algorithm that, given a set {x1,x2€¦.xn}of points on the

real line, determines the smallest set of unit-length closed intervals that contains

all of the given points. Argue that your algorithm is correct.

Question5:

LetSbe a finiteset and letS1, S2, €¦,Skbe a partition of Sinto nonempty disjoint

subsets. Define the structure (S, l) by the condition that l = {A:|AnSi| ? 1 for i = 1,

2, €¦,k}. Show that (S, l) is a matroid. That is, the set if all sets Athat contain at most

one member in each block of the partition determines the independent sets of a

matroid.

Question6:

Consider N chords in a circle, each determined by its endpoints. Describe an O(nlogn) time Algorithm to determining the number of pairs of chords that intersect inside the circle. (For example, if the n chords are all diameters that meet at the center, then the correct answer is (n/2). ASSUMPTION: No two chords share an endpoint.