Homework 7 Solution

1. [40 points] (U&G-required)




A company with a photocopying service that has a single large machine faces the following scheduling problem. Every morning, the company receives a set of jobs from its customers. Ideally, the jobs should be run on their single machine in an order that keeps their customers happiest. We know that customer i’s job will take ti time to complete. Given a schedule (i.e., an ordering of the jobs), let Ci represent the finishing time of job i. For example, if job i is the first to be done, we would have Ci = ti; and if job j is done right after job i, we would have Cj = Ci + tj. Each customer i also has a given weight wi that represents his or her importance to the business. The happiness of customer i is expected to be dependent on the finishing time of i’s job. Therefore, the company decides that they want to order the jobs to minimize the weighted sum of the completion times, åin=1 wi Ci .




Design an efficient algorithm to solve this problem: given a set of n jobs with a processing time ti and a weight wi for each job, order the jobs so as to minimize the weighted sum of the completion times, åin=1 wi Ci .




Example. Suppose there are two jobs: the first takes time t1 = 1 and has weight w1 = 10, while the second job takes time t2 = 3 and has weight w2 = 2. Then doing job 1 first would yield a weighted completion time of 10*1 + 2*4 = 18, while doing the second job first would yield the larger weighted completion time of 10*4 + 2*3 = 46. Note: you have to prove that your strategy yields the optimal solution.




2. [40 points] (U&G-required)




An office manager has to schedule a group of n workers, each of whom is scheduled to work one shift during the week. Each shift is a contiguous amount of time [starti, finali] and there could me multiple shifts going on at once. The manager wants to select a subset of workers to form an advisory committee that she could meet with once week. She

considers a committee to be complete if, for every worker that is not on the committee, that worker’s shift overlaps (even partially) with the shift of a worker in the committee. This ensures that each worker’s performance can be observed by at least one worker in the advisory committee. Give an efficient algorithm that takes the schedule of n shifts and provides a complete advisory committee containing as few workers as possible.




Example. Suppose that there are n = 3 workers with the following shifts:




Worker 1: Monday 4pm – 8pm



Worker 2: Monday 6pm – 10pm



Worker 3: Monday 9pm – 11pm



The smallest complete advisory committee would consist of worker 2 only, since his/her shift overlaps with both other workers.




Note: to prove that your greedy strategy yields the optimal solution, you have to prove the greedy-choice property.




3. [20 points] (U&G-required)




Construct an optimal Huffman coding tree for the characters I with frequency 75, U with frequency 200, B with frequency 25, S with frequency 275, C with frequency 50, H with frequency 100, M with frequency 25, and P with frequency 250. How many bits are required to store the above characters using the resulting encoding? (Show your work for building the Huffman codes).

4. [20 points] (G-required)




Professor Gig A. Byte needs to store text made up of the characters A with frequency 6, B with frequency 2, C with frequency 3, D with frequency 2, and E with frequency 8. Professor Byte suggests using the variable length codes:










Character
Code
A
1
B
00
C
01
D
10
E
0






The professor argues that these codes store the text in less space than that used by an optimal Huffman code. Is the professor correct? Explain.




5. [20 points] (Extra credit)




A shipping company transports packages from Los Angeles to San Francisco every day. Their volume is large enough that the company may need to send multiple trucks every day. Each truck has a limited amount of weight W that it can carry. Packages arrive at the LA station one by one, each package i having a weight wi. Since the station is small, only one truck can be at the station at any time. The company’s policy is that packages must be sent out in the order received. Their current greedy policy is to load the packages into the truck in the order received; whenever a package does not fit, the truck is sent out and the package is held for the next shipment. Prove that for a given set of packages, with their corresponding weights, the company’s current strategy minimizes the number of trucks that are needed.