代写CS6382程序、代写c++，Java编程

日期：2022-02-20 11:22

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.

2