CSE 101 Midterm Exam Page 1 of 8
1. Assignment [15 points]
Consider the following table:
T1 T2 T3 T4
A 8 7 2 9
B 7 3 4 6
C 8 1 8 5
D 4 9 6 7
1.a. [4 points] Compute a feasible solution with the Smallest-Number-Heuristic. Give the assignment and
the total time to complete all tasks.
Solution:
1.b. [10 points] Solve the problem with Branch-and-Bound : Use the solution value of the Smallest-
Number-Heuristic as the first Best Upper Bound, UB1.
1. Branch: Level = Agent, and continue always at that vertex with the smallest Lower Bound.
2. Lower Bound: Use the Row-Min-Strategy. If this is ≥ the current Best Upper Bound, cross out this
vertex; otherwise, proceed.
3. Upper Bound: Use the Smallest-Number-Heuristic. If this is ≤ to the Best Upper Bound, set this
as the newest Best Upper Bound and immediately cross out any open vertices with a Lower Bound ≥
this new Best Upper Bound.
4. Crossing out a vertex: all assignments are done or its Upper Bound is ≤ its Lower Bound.
5. Lastly, number each vertex in the order they are constructed.
The vertex with the Best Upper Bound is an optimal solution.
Make sure you clearly label the bound(s) that are computed at each node, whether a node is crossed out,
and label the edges with corresponding agent → task (e.g. A → T1). Box your final answer, where you
should give the assignment and the total time to complete all tasks.
CSE 101 Midterm Exam Page 2 of 8
Solution:
1.c. [1 point] How many vertices can you avoid computing if you used Branch-and-Bound instead of
Complete Enumeration?
Solution:
CSE 101 Midterm Exam Page 3 of 8
2. Bin Packing [8 points]
An ordered list of items (A, B, C, D, E, F, G, H, I, J) with sizes (4, 7, 5, 13, 3, 9, 2, 7, 1, 4) need to be packed
into bins with capacity 15. Minimize the number of bins used. Apply the following heuristics and give the
number of bins used, as well as the items in each bin.
In your solution, label the bins with 1 , 2 , 3 , … , and specify the items in each bin. An example of
the solution format is: 1 : {A}, 2 : {B, E}, . . .
2.a. [4 points] Next Fit.
Solution:
2.b. [4 points] First Fit Decreasing.
Solution:
CSE 101 Midterm Exam Page 4 of 8
3. Scheduling [20 points] Part (a) concerns the following 8 jobs, which have to be scheduled
on a single processor.
jobs A B C D E F G H
processing times 5 3 8 7 6 11 7 10
due dates 6 27 20 29 32 19 16 15
3.a. [10 points] Schedule the jobs on a single processor so that the number of late jobs is minimized
using the Moore-Hodgson Algorithm. Show the steps of your work, and box the total number of late jobs.
Solution:
CSE 101 Midterm Exam Page 5 of 8
Parts (b) and (c) concern the same 8 jobs, which have to be scheduled on three parallel, identical processors.
jobs A B C D E F G H
processing times 5 3 8 7 6 11 7 10
3.b. [5 points] Schedule the jobs so that the makespan is minimized (no preemptions allowed). What
is Cmax?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
P3
3.c. [5 points] Schedule the jobs so that the sum of completion times is minimized (no preemptions
allowed). What is
∑
Cj?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
P3
CSE 101 Midterm Exam Page 6 of 8
4. Bin Packing [17 points]
Consider the following problem. You are given n items with weights 0 < w1, w2, . . . , wn ≤ 1. You are
tasked with the problem of putting these items into bins with capacity 1 (i.e. the total weight of all items
in any one bin is at most 1). Your objective is to minimize the total number of bins used.
Consider the following algorithm for this problem:
Put each item of weight wi > 0.5 in its own bin. If there are items remaining, take a new bin and put
items in it one at a time until it is filled to at least half capacity. Repeat this until there are no items
remaining.
int procedure MyBinPacking(W = [w1, w2, . . . , wn])
1. b := 0 // b keeping track of the number of bins
2. for i = 1 to n
3. if wi > 0.5
4. Open a new bin and set b := b + 1
5. Assign item i to bin b. Remove wi from W .
6. while there is an element wi left in W
7. if total weight in bin b > 0.5 or b == 0
8. Open a new bin and set b := b + 1
9. Assign item i to bin b. Remove wi from W .
10. return b
4.a. [5 points] Find the big-O time complexity of the algorithm.
Solution:
CSE 101 Midterm Exam Page 7 of 8
4.b. [5 points] Give a counter example where the algorithm does not give the optimal solution.
Solution:
4.c. [7 points] Prove that the algorithm is a 2-approximation for Bin Packing.
Solution:
CSE 101 Midterm Exam Page 8 of 8
5. Extra Credit [10 points]
Given n items (x1, x2, . . . , xn) with positive integer weights (w1, w2, . . . , wn), give an algorithm that com-
putes the number of non-empty sets of these items (sets do not have repeated elements) with total weight
at most C.
For example, your are given items (x1, x2, x3, x4) with weights (1, 2, 3, 5) and the capacity is C = 4. There
are 5 non-empty sets of these items whose total weight is at most C: {x1}, {x2}, {x3}, {x1, x2}, {x1, x3},
so your algorithm should return 5.
Describe your algorithm (make sure to specify the return value) and give a brief explanation on why it is
correct. You do not need to provide a time analysis. For full credit, your algorithm should run in time
O(C · n) or better. (Hint: use dynamic programming)
Solution: