1 Scheduling with Weights

The deadline for homework 1 is upon us. The TA sits in front of the computer, with a mountain of emails from students with doubts. Say we have a set of n emails to answer, where each email j requires time t_j to answer, and has an importance w_j that represents how urgent it is (higher weight means more urgent). We want to find an order to schedule the replies that gives precedence to writing critical emails sooner. Formally, let C_j denote the completion time of email j. For example, if the first three emails to write are i, j, and k (in that order), we would have that C_i = t_i, C_j = t_i + t_j , and C_k = t_i + t_j + t_k. Our goal is to find an order to schedule the replies that minimizes.

As it turns out, this problem has a similar solution to the Minimizing Max Lateness problem we solved in class. Specifically, if we sort the jobs based on the correct criteria, our schedule will be optimal. For each of the following criteria, either give a small example showing it does not always produce an optimal schedule, or give a proof of correctness based on the exchange argument (following the framework we used for minimizing max lateness, i.e. show that swapping two adjacent out-of-order emails in a schedule only improves the objective).

1. Greedy by smallest time t_i
2. Greedy by largest weight w_i
3. Greedy by largest weight-per-unit-time first (break ties by index of emails, i.e. if two emails have the same ratio then choose the one with smaller index).

2 Divide and Conquer

Let T be a table of n relative integers. We want to find the maximum sum of contiguous elements, namely, two indices i and j (1 i j n) that maximize

j k=i T[k].

1. If the values in the table are T[1] = 2,T[2] = 18,T[3] = 22,T[4] = 20,T[5] = 8,T[6] = 6,T[7] = 10,T[8] = 24,T[9] = 13, and T[10] = 3, can you return the two indices and the corresponding optimal sum?
2. Design an algorithm that return the maximum sum of contiguous elementswith a divide-and-conquer algorithm.
3. Bonus: Design a linear-time algorithm that solves the problem through a

single scan of the array.

3 Master Theorem

For each of the following recurrences, give the asymptotic solution if the recurrence can be solved with Master Theorem. Otherwise, briefly explain why Master Theorem is not applicable.

a)

b)

c)

d)

e)

4 Dynamic Programming

Barry Cage is developing a new Search engine, Boogle, and beta testing has shown that many users hastily enter queries that do not have spaces between words, like herecomesthesun and javatutorials. So, Barry needs your help in writing an efficient algorithm to perform string segmentation. Now there are several possible segmentations of the string herecomesthesun, such as here comes the sun or her eco me st hesun. One possible solution would be to maximize the cumulative quality/plausibility of the individual segmented words.

Thanks to some open source code, he already has access to a function that computes the plausibility of words. Given a string of letters x = x₁x₂x_k, plausibility(x) returns a number that can be either positive, or negative; larger numbers indicate more plausible English words (so plausibility(sun) would be positive, while plausibility(hesun) would be negative). The value of plausibility(x) is defined for any string of characters.

Given a long string of letters y = y₁y₂y_k, a segmentation of y is a partition of its letters into contiguous blocks of letters; each block corresponding to a word in the segmentation. The total plausibility of a segmentation is determined by adding up the plausibility scores of each of its blocks. For example, the plausibility of the segmentation here comes the sun of the string herecomesthesun is equal to plausibility(here) + plausibility(comes)+ plausibility(the) + plausibility(sun).

Give and analyze a polynomial time algorithm that takes a string y and computes a segmentation of maximum total plausibility, MaxPlausibility(y). (One call to the function plausibility(x) can be considered as a single computational step.) Follow these steps:

1. prove that the problem has optimal substructure
2. write a recursive expression for MaxPlausibility, specifying the base cases and the goal
3. write a recursive algorithm with memoization, and analyze its time andspace complexity
4. derive a valid order in which subproblems can be evaluated bottom-up,and write the iterative (bottom-up) version of your algorithm.