Dynamic Programming Short Answer

2.

(a) Scheduling. IT is trying to write a scheduler for two identical machines. They know that there are n jobs and that the ith job takes ti seconds, regardless of which machine it is assigned to (the machines are identical). Each ti is a positive integer. Each job must be assigned to one of the two machines, and we want to assign jobs so as to minimize the completion time of the last job to finish.

More precisely, if we assign a set S1 ? {1, . . . , n} of jobs to the first machine then we necessarily assign S2 = {1,...,n} \ S1 to the second. The finish time is F1 = ??i?S1 ti for machine one and F2 = ??i?S2 ti for machine two. The final finish time is then F = max{F1,F2}. Design an efficient algorithm to find the cost of the optimal schedule, which is the smallest value F attainable by an assignment of jobs to machines. You do not need to find the assignment itself. If each ti is a k-bit integer, what is the running time of your algorithm as a function n and k?

(b) Longest Common Substring. Given two strings X = x1x2 . . . xm and Y = y1y2 . . . yn, we wish to find the length of the longest common substring, which is the largest k such that there exists i, j with xixi+1 . . . xi+k?1 = yj yj+1 . . . yj+k?1. Design an O(nm) algorithm to find both the length of the longest common substring, and the actual substring.