Page 256 - Discrete Mathematics and Its Applications

Computer Projects 235

Exercises 37–40 deal with the problem of scheduling n jobs on sleeping bag, an 8-kg tent, a 7-kg food pack, a 4-kg
a single processor. To complete job j, the processor must run container of water, and an 11-kg portable stove.
job j for time t j without interruption. Each job has a dead- In Exercises 42–46 we will study the problem of load balanc-
line d j . If we start job j at time s j , it will be completed at ing. The input to the problem is a collection of p processors
time e j = s j + t j . The lateness of the job measures how long and n jobs, t j is the time required to run job j, jobs run without
it finishes after its deadline, that is, the lateness of job j is interruption on a single machine until finished, and a proces-
max(0,e j − d j ). We wish to devise a greedy algorithm that sor can run only one job at a time. The load L k of processor
minimizes the maximum lateness of a job among the n jobs.
k is the sum over all jobs assigned to processor k of the times
37. Suppose we have five jobs with specified required times required to run these jobs. The makespan is the maximum
and deadlines: t 1 = 25, d 1 = 50; t 2 = 15, d 2 = 60; t 3 = load over all the p processors. The load balancing problem
20, d 3 = 60; t 4 = 5, d 4 = 55; t 5 = 10, d 5 = 75. Find the asks for an assignment of jobs to processors to minimize the
maximum lateness of any job when the jobs are scheduled makespan.
in this order (and they start at time 0): Job 3, Job 1, Job 4, 42. Suppose we have three processors and five jobs requiring
Job 2, Job 5. Answer the same question for the schedule times t 1 = 3, t 2 = 5, t 3 = 4, t 4 = 7, and t 5 = 8. Solve
Job 5, Job 4, Job 3, Job 1, Job 2. the load balancing problem for this input by finding the
assignment of the five jobs to the three processors that
38. The slackness of a job requiring time t and with deadline
d is d − t, the difference between its deadline and the minimizes the makespan.
∗
time it requires. Find an example that shows that schedul- 43. Suppose that L is the minimum makespan when p pro-
ing jobs by increasing slackness does not always yield a cessors are given n jobs, where t j is the time required to
schedule with the smallest possible maximum lateness. run job j.
∗
a) Show that L ≥ max j=1,2,...,n t j .
39. Find an example that shows that scheduling jobs in or- 1 n
t
∗
b) Show that L ≥ j=1 j .
der of increasing time required does not always yield a p
schedule with the smallest possible maximum lateness. 44. Write out in pseudocode the greedy algorithm that goes
through the jobs in order and assigns each job to the pro-
∗ 40. Provethatschedulingjobsinorderofincreasingdeadlines
cessor with the smallest load at that point in the algorithm.
always produces a schedule that minimizes the maximum
45. Run the algorithm from Exercise 44 on the input given in
lateness of a job. [Hint: First show that for a schedule to
Exercise 42.
be optimal, jobs must be scheduled with no idle time be-
tween them and so that no job is scheduled before another An approximation algorithm for an optimization problem
with an earlier deadline.] produces a solution guaranteed to be close to an optimal so-
lution. More precisely, suppose that the optimization problem
41. Suppose that we have a knapsack with total capacity of
asks for an input S that minimizes F(X) where F is some
W kg. We also have n items where item j has mass w j .
function of the input X. If an algorithm always finds an input
The knapsack problem asks for a subset of these n items
T with F(T ) ≤ cF(S) where c is a fixed positive real number,
with the largest possible total mass not exceeding W.
the algorithm is called a c-approximation algorithm for the
a) Devise a brute-force algorithm for solving the knap- problem.
sack problem. ∗ 46. Prove that the algorithm from Exercise 44 is a 2-
b) Solve the knapsack problem when the capacity of the approximation algorithm for the load balancing problem.
knapsack is 18 kg and there are five items: a 5-kg [Hint: Use both parts of Exercise 43.]
Computer Projects

Write programs with these inputs and outputs.

1. Given a list of n integers, find the largest integer in the 6. Given a list of n integers, sort them using an insertion
list. sort.
2. Given a list of n integers, find the first and last occurrences
of the largest integer in the list. 7. Given an integer n, use the greedy algorithm to find the
change for n cents using quarters, dimes, nickels, and
3. Given a list of n distinct integers, determine the position
pennies.
of an integer in the list using a linear search.
4. Given an ordered list of n distinct integers, determine the 8. Given the starting and ending times of n talks, use the
position of an integer in the list using a binary search.
appropriate greedy algorithm to schedule the most talks
5. Given a list of n integers, sort them using a bubble sort. possible in a single lecture hall.