Dynamic Programming Short Answer 2. (a) Scheduling. IT is trying to write a sche
ID: 3740810 • Letter: D
Question
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.
Explanation / Answer
Solution:
b part is done, please repost part a. If you don't have any questions left, please let me now. I will help.
Solution:
Algorithm:
Now for printing
2) Traverse the 2D array starting from L[m][n]. Do following for every cell L[i][j]
…..a) If characters (in X and Y) corresponding to L[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.
…..b) Else compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.
The above pseudocode will print the string which is longest common subsequence between them.
Running time:
The running time of the above algorithm is O(nm), since there are two loops nested which are running on the string length of both of the strings.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.