CS6382: Assignment 1
February 18, 2022
Question 1: Scheduling
Given a job set J = { j1, · · · , jn } consisting of n jobs and one machine. Each
job ji has a processing time pi
. The processing time pi
is a position related
function, i.e., pi = a
β
i
, where β ∈ { 1, 2, · · · , n } is the position that the job is
processed and ai
is a given parameter which is associated with job ji
. Note
that different jobs have different ai
. Once a job starts processing, the next job
cannot be started until it finishes.
Give an algorithm that computes a job order such that the makespan is
minimized, where makespan is the maximum finishing time among all jobs.
The algorithm should be polynomial and you need to prove the correctness.
Example consider the following job set J = { j1, j2, j3 }, where a1 = 2, a2 = 3
and a3 = 4. If the job order is j1, j2, j3, then the makespan is 21 + 32 + 43 = 75.
Question 2. Stacking Boxes
You are given a set of n types of rectangular boxes, where the i-th box has
height h[i], width w[i], and depth d[i] (all positive integers). You want to build
a stack of boxes as high as possible, but you can place a box above another only
if the dimensions of the base of the box below are strictly greater than the base
of the box above. It is possible to turn the boxes, so that all sides can serve as
a base. It is also possible to use several instances of the same type of box.
Design an algorithm to output the best solution.
Question 3. Divide and Conquer
Given an array A with n entries, with each entry holding a distinct number. The
values in this array first decrease and then increase with the index. That is, for
some index p between 1 and n, the values in the array entries A[1], A[2], · · · , A[p]
decrease and the values in the array entries A[p], A[p + 1], · · · , A[n] increase.
Give an algorithm that finds p by reading at most O(log n) entries of A. You
need to prove the running time of the algorithm.
1
Question 4. Bin Packing
Suppose that we are given a set of n objects, where the size si of the i-th object
satisfies 0 < si < 1. We wish to pack all the objects into the minimum number
of unit-size bins. Each bin can hold any subset of the objects whose total size
does not exceed 1.
1. Prove that the problem of determining the minimum number of bins required
is NP-hard.
2. The first-fit heuristic takes each object in turn and places it into the first
bin that can accommodate it. Let S =
Pn
i=1 si
.
(a) Argue that the optimal number of bins required is at least ⌈S⌉.
(b) Argue that the first-fit heuristic leaves at most one bin less than half
full.
(c) Prove that the number of bins used by the first-fit heuristic is never
more than ⌈2S⌉.
(d) Prove an approximation ratio of 2 for the first-fit heuristic.