CSE 101 Final Exam Page 1 of 22
1. Knapsack with Branch-and-Bound [16 points]
Recall the Knapsack Branch-and-Bound description:
1.Branch: Level = Largest Value, and continue always at that vertex with the largest
Upper Bound.
2.Upper Bound: Use the Largest-Relative-Values-Strategy. If this is ≤ the current Best
Lower Bound, cross out this vertex; otherwise, proceed.
3.Lower Bound: Use the Largest-Relative-Value-Heuristic. If this is ≥ to the Best
Lower Bound, set this as the newest Best Lower Bound and immediately cross out any
open vertices with an Upper Bound ≤ this new Best Lower Bound.
4.Crossing out a vertex: all assignments are done or its Lower Bound is ≥ its Upper
Bound.
5.Number each vertex in the order they are constructed.
The vertex with the Best Lower Bound is an optimal solution.
The problem is on the next page.
CSE 101 Final Exam Page 2 of 22
Consider the following knapsack instance with 7 items and 160 capacity where each item can
only be taken at most once.
A B C D E F G
Values 40 49 50 55 60 70 85
Weights 30 35 40 45 50 55 60
Relative values 1.33 1.40 1.25 1.22 1.20 1.27 1.41
The largest-relative-value is 174 and the first lower bound LB1 is 174. Carry out the first
two “levels” of the Branch-and-Bound tree. Make sure each node box indicates (1) the upper
bound, (2) the lower bound (if calculated), (3) when a node is closed, and (4) why the node
was closed. For the upper and lower bound, round to the nearest one.
Solution:
G in G out
in
out in
out
CSE 101 Final Exam Page 3 of 22
2. SSSP and APSP [19 points]
A
B C
E
F
D
-3 1
-2
5
7
3
2
-1
1
2.a. [8 points] Using Bellman/Ford’s algorithm, find the single-source-shortest-paths
(SSSP) solution starting at vertex A to all other vertices of the above graph. Relax the
edges in lexicographic order: (A,B), (A,F), (B,C), (C,A), (C,D), (C,E), (D,E), (E,A), (F,E)
and complete the following table:
Solution:
A B C D E F
Initialization
Phase 1
Phase 2
Phase 3
Phase 4
Phase 5
CSE 101 Final Exam Page 4 of 22
Using Floyd-Warshall’s algorithm, find the all-pairs-shortest-paths (APSP) of the
graph below.
C
B A
D
7
4
−112 −3
5
2.b. [1 point] Initialization step: First, please fill out the adjacency matrix of the graph
above.
Solution:
Adjacency matrix
u A B C D
A 0
B 0
C 0
D 0
CSE 101 Final Exam Page 5 of 22
C
B A
D
7
4
−112 −3
5
2.c. [10 points] Please fill out the following matrices where u denotes current vertex using
Floyd-Warshall’s algorithm.
Solution:
Phase 1:
u = A A B C D
A 0
B 0
C 0
D 0
Phase 2:
u = B A B C D
A 0
B 0
C 0
D 0
Phase 3:
u = C A B C D
A 0
B 0
C 0
D 0
Phase 4:
u = D A B C D
A 0
B 0
C 0
D 0
CSE 101 Final Exam Page 6 of 22
3. CVRP [16 points] Savings heuristic for Capacitated Vehicle Routing Planning.
Consider the following graph. The depot is marked with O. The time required to get from
one place to another on the respective route is shown at each edge.
O
A
C
B
D
7
8
3
7
2 4
There are Q = 10 units per truck available. The demand of each customer are in the following
table.
A B C D
2 5 4 4
The distances of the shortest paths can be found in the following table.
O A B C D
O 0 5 13 3 10
A 0 8 2 9
B 0 10 4
C 0 7
D 0
3.a. [2 points] Calculate the total length of the tour planning if only round trips are used.
Solution:
CSE 101 Final Exam Page 7 of 22
A B C D
2 5 4 4
O A B C D
O 0 5 13 3 10
A 0 8 2 9
B 0 10 4
C 0 7
D 0
3.b. [4 points] Calculate the Savings values and enter the Savings values in the table below:
Solution:
O A B C D
O – – – – –
A – –
B – – –
C – – – –
D – – – – –
3.c. [10 points] Apply the Savings heuristic for Capacitated Vehicle Routing Planning and
answer the following questions.
•Which tours are generated in this way?
•What are the total demands and saving of each tour?
•What is the total distance?
In your solution, write the tours along with the demand and saving in the following format,
Tour : O → → ………….→ O (demand: and saving: miles)
Tour : O → → ………….→ O (demand: and saving: miles)
Total distance: miles
Solution:
CSE 101 Final Exam Page 8 of 22
4. Linear Programming [24 points]
The Whitt Window Company, a company with only three employees, makes two different
kinds of hand-crafted windows: 1) a wood-framed and 2) aluminium-framed. They earn
$60 profit for each wood-framed window and $30 for each aluminum-framed window. Doug
makes the wood frames, and can make 6 per day. Linda makes the aluminum frames, and
can make 4 per day. Bob forms and cuts the glass, and can make 54 square feet of glass
per day. Each wood-framed window uses 6 square feet of glass and each aluminum-framed
window uses 9 square feet of glass.
4.a. [5 points] Formulate a Linear Programming model that optimizes the total profit. Use
x as the number of wood-framed windows and y as the number of aluminium-framed windows.
Solution:
4.b. [7 points] Use the graphical method to solve the model. How many units of each
product should be produced? What is the maximum profit?
Solution:
CSE 101 Final Exam Page 9 of 22
NOTE: For questions 4.c to 4.e., consider the following linear programming
max 3x+ 2y
s.t.
x+ y ≤ 1600 (1)
2x+ y ≤ 2400 (2)
x+ 2y ≤ 2800 (3)
x, y ≥ 0 (4)
4.c. [6 points] Set up the initial simplex tableau and do the first iteration of the simplex
algorithm.
Solution:
CSE 101 Final Exam Page 10 of 22
4.d. [3 points] The following tableau is the optimal tableau.
1.What are the values of the decision variables (x and y)?
2.What are the values of the slack variables s1, s2, s3?
3.What is the maximum value of the objective function?
4.Give an interpretation of the slack variables s1, s2, s3.
x y s1 s2 s3
y 0 1 2 −1 0 800
x 1 0 −1 1 0 800
s3 0 0 −3 1 1 400
z 0 0 1 1 0 4000
Solution:
4.e. [3 points] How would the maximum value of the objective function and the values of
x and y change if constraint (1) would change to x+ y ≤ 1700?
Solution:
CSE 101 Final Exam Page 11 of 22
5. Proofs [25 points]
5.a. [13 points] Prove: Bin Packing is NP-complete.
Use: Partition ∝ Bin Packing.
The [Bin Packing] problem: Given a finite set U of items, a size s(u) ∈ Z+ for each u ∈ U ,
a positive integer bin capacity B, and a positive integer K. Is there a partition of U into dis-
joint subsets U1, U2, . . . , UK such that the sum of the sizes of the items in each Ui is B or less?
The [Partition] problem: Given a list of n positive integers s1, s2, . . . , sn with σ =
∑n
i=1 si
and a positive integer z = σ/2. Does there exist a subset I ⊆ {1, . . . , n} such that∑
i∈I si =
∑
i 6∈I si = z?
Please use the proof structure as in lecture and homework:
Step 1: [3 points] Prove Bin Packing is in NP.
Solution:
Step 2: Select a known NP-Complete problem – Partition
Step 3: [4 points] Show how to compute a specific input for Bin Packing in polynomial
time, given an arbitrary input for Partition.
Solution:
CSE 101 Final Exam Page 12 of 22
Step 4: [6 points] Show Partition is reducible to Bin Packing
Solution:
CSE 101 Final Exam Page 13 of 22
5.b. [12 points] Approximation Proof for Scheduling. Consider the scheduling
problem on identical parallel processors. Let T1 denote the original job set and T2 be the
truncated job set. We get T2 by deleting all of the jobs that starts after the job that
determines the makespan in the LPT-order from T1.
1. [4 points] Consider the following list of jobs T1 = {A, B, C, D, E, F, G, H, I, J}, with
processing time {15, 10, 7, 1, 9, 10, 14, 3, 13, 5}, respectively. Draw the LPT schedule
of T1 on m = 3 processors using following Gantt-Chart. What is the makespan of
T1 with LPT (C
LPT
max (T1))? What is the optimal makespan (C
∗
max(T1))? What is the
corresponding truncated job list T2?
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 26 27 28 29 30 31
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 26 27 28 29 30 31
P3
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 26 27 28 29 30 31
CLPTmax (T1) =
C∗max(T1) =
The truncated job set T2 is :
(For grading convenience, please write letters in alphabetical order)
CSE 101 Final Exam Page 14 of 22
2. [8 points] Recall that in the proof for the LPT-approximation factor, we want to
find an upper bound on CLPTmax (T1)/C
∗
max(T1). In the proof, we claimed that it suf-
fices to find an upper bound of CLPTmax (T2)/C
∗
max(T2). Prove that the upper bound for
CLPTmax (T2)/C
∗
max(T2) must also be an upper bound for C
LPT
max (T1)/C
∗
max(T1). Reminder:
Only showing the statement is true for this previous (or any other specific) example is
not sufficient. You would need to formulate your proof on an arbitrary job set T1.
Solution:
CSE 101 Final Exam Page 15 of 22
6. Design Graph Algorithm [25 points]
Imagine you are a city planner and you have a map of a neighborhood given as a weighted
undirected graph G where the vertices are intersections and edges are two-way streets that
connect vertices. There is a subset of vertices H ⊆ V where there are houses. You are
looking to build an Disney’s World at one of the intersections (i.e. vertices) that has the
minimum sum of distances from all houses. (In other words, you are trying to locate a vertex
v such that
∑
h∈H disti(v, h) is minimized, where dist(v, h) is the minimum distance from v
to h.)
6.a. [15 points] Describe an algorithm that finds the location of the Disney’s World. For
full credit, your algorithm should run in O(k · (n log n+m)) or better. k denotes the number
of houses, n denotes the number of vertices, and m denotes the number of edges of G.
Solution:
CSE 101 Final Exam Page 16 of 22
6.b. [5 points] Explain why your algorithm works.
Solution:
6.c. [5 points] Analyze the runtime of the algorithm.
Solution:
CSE 101 Final Exam Page 17 of 22
7. Design Divide-and-Conquer Algorithm. [25 points]
You are given a perfect binary tree T with n leaves in which all the internal nodes have two
children and all leaf nodes are at the same level. Each leaf is labelled with a non-negative
integer, and each internal node is labelled with a mathematical operation either +a or ×b
for a or b a positive integer. Assume each mathematical operation above takes constant
time. You want to pick a leaf and apply the relevant operations one at a time going up
the tree. You would like to find the maximum value calculated in this way. In the example
below, the bold leaf gives the largest value of (5 + 3)× 2 = 16 (the calculation is evaluated
bottom-up) and your algorithm should return 16.
CSE 101 Final Exam Page 18 of 22
7.a. [15 points] Describe an algorithm to compute the largest value achievable this way.
For full credit your algorithm should run in time O(n) or better.
Solution:
CSE 101 Final Exam Page 19 of 22
7.b. [5 points] Explain why your algorithm works.
Solution:
7.c. [5 points] Analyze the runtime of the algorithm.
Solution:
CSE 101 Final Exam Page 20 of 22
8. BONUS: Design Dynamic Programming Algorithm
[25 points]
My friend Arth is a college student who is trying to make some extra money by doing medical
trials. He has a calendar of the n medical trials during an M day period. Each medical trial
Ti has the day it starts si, the day it ends ei, and the amount of money it pays pi. You are
not allowed to participate in two trials at the same time – if a trial ends on day j, you can
only start participating in other trials starting from day j+1 but cannot participate in trials
starting on day j. For example, in the following problem instance, number of medical trials
is n = 4, the day period is M = 20, and the trial details are listed below:
si ei pi
T1 1 2 20
T2 3 5 100
T3 6 16 50
T4 5 20 130
The optimal solution would be picking medical trials T1, T2, T3 which gives maximum profits
100 + 20 + 50 = 170.
Design a dynamic programming algorithm to help Arth choose which medical trials to select
in order to maximize the total pay. Your input is the length of time period M , a list of n
medical trials, T = [T1, T2, …, Tn], their corresponding starting day S = [s1, s2, …, sn], ending
day E = [e1, e2, …, en], and amount of money pays P = [p1, p2, …, pn]. Specifically, the trials
are sorted by their end date (from earliest to latest). Your algorithm should return the
maximum possible profit.
CSE 101 Final Exam Page 21 of 22
8.a. [15 points] Describe the algorithm. For full credit your algorithm should run in time
O(n2) or O(nM) or better.
Solution:
CSE 101 Final Exam Page 22 of 22
8.b. [5 points] Give a brief explanation why your algorithm works.
Solution:
8.c. [5 points] Analyze the runtime of the algorithm.
Solution: