Home Page > > Details

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.

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Programhelp With ,Help With C++ Course... 2022-05-10
- Help With Data Programming,Help With C... 2022-05-10
- 5Cce2sashelp With ,Python，Java Progra... 2022-05-10
- Help With Program Programming,Help Wit... 2022-05-09
- Help With Csci 3110,Help With Java，Py... 2022-05-09
- Mth2222help With ,Help With C/C++，Pyt... 2022-05-09
- Cse3bdchelp With ,Help With Sql Progra... 2022-05-08
- Help With Cis 468,Help With Java，Pyth... 2022-05-08
- Comp Sci 4094/4194/7094 Assignment 3 D... 2022-05-07
- Cs 178: Machine Learning & Data Mining... 2022-05-07
- Data7703 Assignment 4 2022-05-07
- Data Programminghelp With ,Help With S... 2022-04-25
- Help With Ait681 Course,Help With Pyth... 2022-04-25
- Cse121l Programminghelp With ,Help Wit... 2022-04-25
- Help With Iti1120,Help With Java，C/C+... 2022-04-25
- Cmt304help With ,Help With C++，Python... 2022-04-25
- Help With Engn4528,Matlab Programmingh... 2022-04-24
- Help With Fin 2200,Help With Java，Pyt... 2022-04-24
- Bism 7255Help With ,Help With Java，Py... 2022-04-23
- Comp202help With ,Help With Java Progr... 2022-04-23

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2021 www.asgnhelp.com

Programming Assignment Help！