a
To prove the problem of determining the minimum number of bins required is NP-HARD.
a
Explanation of Solution
Suppose and are the same (indeed if the answer is yes for. Then there exists . On the other hand if the answer is yes for , so if
Note that
So, the answer of derived bin-packing problem can-not be less than 2 . First assume that the answer to the given instance of sub set -sum problem is “yes”.
Now, there is
Now
b
To argue that the optimal number of bins required is at least
b
Explanation of Solution
Consider the packing ofn objects with sizes
Let
Therefore,
Since bis an integer number,
c
To argue that the first-fit heuristic leaves at most one bin less than half full.
c
Explanation of Solution
The first- fit heuristic places each object in the first available bin. Suppose by contradiction that two bins
d
To prove that the number of bins used by the first-fit heuristic is never more than
d
Explanation of Solution
Consider a bin- packing solution provided by the first-fit HEURISTIC.
Using similar notation as in (b) (let
It can be assumed without loss of generality that
e
To prove an approximation ratio of 2 for the first-fit heuristic.
e
Explanation of Solution
Letb be the number of the bins used the first-fit HEURISTIC and let
e
To give an efficient implementation of the first-fit heuristic, and analyze its running time.
e
Explanation of Solution
1.
2. initialize data structures
3. fori = 1 to ndo
4. letjbe the first bin that can fit objecti with size
5. ifjexists then
6. inserti at the list (list
7.update data structures
8.else
9.
10. insertiat the list
11.update data structures II
12.endif
13. endfor
Each of the above steps can be done in
Want to see more full solutions like this?
Chapter 35 Solutions
Introduction to Algorithms
- Suppose a set of n objects is given, such that the size of the ith object satisfies that 0 < < 1. It is required to pack all the objects in a set of boxes of unit size. Each box can contain any subset of objects whose total size does not exceed 1. The heuristic first-fit takes each object and fits it into the first box that can hold it. Finally, let S be sum of the sizes of all objects: a. Show that the total number of boxes used by the first-fit heuristic is never greater than ⌈2S⌉. b. Show that the approximation factor of the first-fit heuristic is 2.arrow_forwardConsider eight points on the Cartesian two-dimensional x-y plane. a g C For each pair of vertices u and v, the weight of edge uv is the Euclidean (Pythagorean) distance between those two points. For example, dist(a, h) : V4? + 1? = /17 and dist(a, b) = v2? + 0² = 2. Because many pairs of points have identical distances (e.g. dist(h, c) V5), the above diagram has more than one minimum-weight spanning tree. dist(h, b) = dist(h, f) Determine the total number of minimum-weight spanning trees that exist in the above diagram. Clearly justify your answer.arrow_forward(I)Prove that for any integer n, n6k-1 is divisible by 7 if gcd(n,7)=1 and k is a positive integer. (Ii)Show that a 6×n board (n>=2) can be tiled with L-shaped tiles,without gap and overlapping.Each L-shaped tile covers three squares.arrow_forward
- Let X = {1, 2, 3, 4, 5} and Y = {7, 11, 13} are two sets. find R = {(x, y): x EX and %3D * y EY and (y – x) is divisible by 6}arrow_forwardCorrect answer will be upvoted else downvoted. Computer science. lamp can be coordinated to enlighten either a few lights to the left or a few lamps to the right. In the event that the I-th lamp is gone to one side, it enlightens all such lights j that j∈[i−pi,i−1]. Also, in case it is gone to one side, it enlightens all such lamps j that j∈[i+1,i+pi]. You will probably pick a course for every light so every lamp is enlightened by undoubtedly another lamp, or report that it is incomprehensible. Input The primary line contains one integer t (1≤t≤10000) — the number of experiments. Each experiment comprises of two lines. The primary line contains one integer n (2≤n≤3⋅105) — the number of lamps. The subsequent line contains n integers p1,p2,… ,pn (0≤pi≤n) — the force of the I-th lamp. The amount of n over all experiments doesn't surpass 3⋅105. Output For each experiment, print the appropriate response as follows: In case it is feasible to coordinate all lamps…arrow_forwardImagine a 3D plane P in your 3D scene. An infinite number of lines can lie on that plane. Consider one set of parallel lines on this 3D plane. This set will produce one vanishing point when projected on the image plane. Consider now all possible sets of parallel line on the plane P. What is the locus of all vanishing points produced by all sets of parallel lines? [Note that you do not have to right down a formula in order to solve this. You need to use a geometric argument.]arrow_forward
- Your training set is made up of the following 2-dimensional points: A={a', a², a³, a², a³} {(1,0), (1,3), (3,0), (0,-2), (-2,0)}, where a', a², and a³ belong to class 1, and at, a5 to class 2. (a) Plot all samples into a 2-dimensional Cartesian axis system Calculate the Manhattan distance 1 between the test sample b=(0,0) and every a of the (b) training set (c) Use the K- Nearest Neighbor algorithm with K=1 to assign a class to 'b'. Explain (d) Classify 'b' using K=5. Explain 'Manhattan(a, b) = E; la² – b' , Vi = 1,2arrow_forwardDetermine P(A x B) – (A x B) where A = {a} and B = {1, 2}.arrow_forward; 3. Let T U V and S: V W. We have that SoT: U → W. Prove that (SoT)* = T* o S*. 4. Let v₁,.., Un EV be a basis of V. (a) Define the dual basis vi,.., v € V*. (b) Prove that formula: a = Σi-na (v₁) vi for every a € V*. i=1:n (c) Prove the reciprocal formula: v= Ei=1:n v (v) v₁ for every v € V.arrow_forward
- Long chain of friends: You are given a list of people, and statements of the form “x knows y”. You are asked to find, is there a chain of k distinct people, such as x1 knows x2, x2 knows x3, and xk-1 knows xk. Prove that this problem is NP-complete by using one of the known NP-complete problems (CLIQUE, 3-SAT, Hamiltonian Path, Hamiltonian Cycle, Independent Set, etc.)arrow_forward3) The graph k-coloring problem is stated as follows: Given an undirected graph G = (V,E) with N vertices and M edges and an integer k. Assign to each vertex v in Va color c(v) such that 1< c(v)arrow_forwardGIVEN: n red points and n blue points in the plane in general position (i.e., no 3 points are on the same line) PROVE: there exists a matching (i.e., 1-1 correspondence) between red and blue points such that the segments connecting the corresponding points do not intersect. EXTRA/HINT: describe an algorithm for finding such matchingarrow_forwardarrow_back_iosSEE MORE QUESTIONSarrow_forward_ios
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education