CSE 101 Final Exam Page 1 of 25
1. Knapsack problem [15 points]
Consider the Knapsack Problem: a subset of the following 4 items are to be put into a knapsack of weight
capacity 5 such that the value of the items in the knapsack is maximized:
A B C D
values 30 24 48 42
weights 2 1 3 2
1.a. [3 points] Apply the largest-relative-value heuristic to this instance to find a feasible solution.
Solution:
1.b. [12 points] Solve the problem with Branch-and-Bound. Solution box continues on next page if needed.
Use the solution value of the Largest-Relative-Value-Heuristic as the first Best Lower Bound, LB1.
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: no capacity left or its Upper Bound is ≤ the Best Lower Bound.
5. Number each vertex in the order they are constructed.
Solution:
CSE 101 Final Exam Page 2 of 25
Solution box continued from previous page.
Solution:
CSE 101 Final Exam Page 3 of 25
2. Scheduling [8 points] The following 7 jobs have to be scheduled on three parallel and
identical processors.
jobs A B C D E F G
processing times 9 3 7 9 2 8 1
2.a. [4 points] Schedule the jobs with preemption according to McNaughton’s algorithm in the given
Gantt-Chart.
Solution:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
P3
2.b. [4 points] Schedule the jobs without preemption according to the LPT algorithm in the given
Gantt-Chart.
Solution:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
P1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
P2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
P3
CSE 101 Final Exam Page 4 of 25
3. Graph Algorithms [24 points]
Parts (a) concerns the following directed graph:
A
B
C
D
E
F
2
4
3
1
2
1
3
1
4
2
2
3.a. [12 points] Using Dijkstra’s algorithm, find the single-source-shortest-paths solution starting at
vertex A to all other vertices of the above graph. Solution box continues on next page if needed.
Solution:
CSE 101 Final Exam Page 5 of 25
Solution box continued from previous page.
Solution:
CSE 101 Final Exam Page 6 of 25
Parts (b) concerns the following directed graph:
A
B
CD
E
6
9 1
4
2
3
1
3.b. [12 points] Using Floyd-Warshall’s algorithm, find the all-pairs-shortest-paths of the above graph.
You may use the following page for scratch work.
Solution:
u = A A B C D E
A 0
B 0
C 0
D 0
E 0
u = B A B C D E
A 0
B 0
C 0
D 0
E 0
u = C A B C D E
A 0
B 0
C 0
D 0
E 0
u = D A B C D E
A 0
B 0
C 0
D 0
E 0
u = E A B C D E
A 0
B 0
C 0
D 0
E 0
CSE 101 Final Exam Page 7 of 25
You may use this page as scratch work for the previous problem.
Solution:
CSE 101 Final Exam Page 8 of 25
4. NP Completeness [10 points]
Recall that the NP-complete Subset-Sum problem asks, given a set of non-negative integers S and a
target K, whether S has a subset S ′ with
∑
i∈S′ i = k.
The Average-Sum problem asks, given just a set of non-negative integers S, whether S has a subset S ′
where ∑
i∈S′
i =
1
|S|
∑
i∈S
i
where |S| is the number of elements in S. The Average-Sum problem is similar to the Subset-Sum
problem, except now the target value is always the average value in S.
Given that the Subset-Sum problem is NP-complete, prove that the Average-Sum problem is also
NP-complete. Solution box continues on next page if needed.
Solution:
CSE 101 Final Exam Page 9 of 25
Solution box continued from previous page.
Solution:
CSE 101 Final Exam Page 10 of 25
5. Linear Programming [22 points]
A bakery sells buns for burgers (B) and hotdogs (H). Profit is $4 for each burger bun (B) and $5 for each
hotdog bun (H).
Flour (F ) and water (W ) are main ingredients in the production of bread. Suppose that there are only 10
units of flour and 42 units of water available.
• Each burger bun needs 1 units of flour and 3 units of water.
• Each hotdog bun needs 1 units of flour and 7 units of water.
Our goal is to maximize the profit of the bakery according to these constraints.
5.a. [4 points] Formulate the mathematical program.
Solution:
CSE 101 Final Exam Page 11 of 25
5.b. [6 points] Solve the problem graphically.
Solution:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 B
H
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CSE 101 Final Exam Page 12 of 25
5.c. [6 points]
i. How do you choose the Pivot-Element in the Simplex Algorithm?
Solution:
ii. When does the Simplex Algorithm terminate?
Solution:
CSE 101 Final Exam Page 13 of 25
5.d. [6 points] Give an interpretation of the optimal Simplex table:
B H F W
B 1 0 7/4 −1/4 7
A 0 1 −3/4 1/4 3
0 0 13/4 1/4 43
i. What is the optimal production program?
Solution:
ii. What is the optimal total value?
Solution:
iii. How would the production program and the profit change if there would be one more unit of flour
were available?
Solution:
CSE 101 Final Exam Page 14 of 25
6. Algorithms and Proofs [30 points]
6.a. [7 points] Consider the problem of scheduling n jobs J1, …, Jn on one processor with processing times
pj and deadlines dj. Prove why in Moore’s algorithm it is always optimal to move — among those jobs
that come until the first job has a delay — the job with the largest processing time to the end.
Solution:
CSE 101 Final Exam Page 15 of 25
6.b. [7 points] Give a proof (by Mathematical Induction) that the following algorithm correctly finds
log2(n) (given n is a power of 2):
procedure logCalc(n: a positive power of 2)
1. if n = 1
2. return 0
3. else
4. return 1 + logCalc(n/2)
Solution:
CSE 101 Final Exam Page 16 of 25
6.c. [8 points] There are n jobs with processing times p1, . . . , pn and m processors to be scheduled ac-
cording to Largest Processing Time. Suppose that the kth job is that which determines CLPTmax , and let
sLPTk denote the work done on the processor on which job k is loaded before loading job k. Explain why
sLPTk ≤
∑n
j=1 pj
m
−
pk
m
Solution:
CSE 101 Final Exam Page 17 of 25
6.d. [8 points] The following questions concern the Single-Source-Shortest-Paths problem:
i. Why is Dijkstra is optimal?
Solution:
ii. Describe a problem instance where Dijkstra fails and Bellman/Ford should be used.
Solution:
iii. How can Bellman / Ford be used to detect negative cycles in a graph?
Solution:
CSE 101 Final Exam Page 18 of 25
7. Design B&B for Bin Packing [20 points] Recall the Bin Packing problem: Given
k distinct items with weights w1, . . . , wk, pack the items into bins of capacity C such that the total number
of bins used is minimized. This problem can be solved with Branch and Bound. For this, we need to define
the lower and upper bounds within each node that dictate how we traverse the graph.
7.a. [10 points] Describe a method for finding the Upper Bound to be used within each node of the Branch
and Bound tree.
Solution:
7.b. [10 points] Describe a method for finding the Lower Bound to be used within each node of the Branch
and Bound tree.
Solution:
CSE 101 Final Exam Page 19 of 25
8. Design a Dynamic Program [20 points]
A word x = x1 · · · xN is a palindrome if it reads the same backward as forward; i.e.,
x1x2 · · ·xN−1xN = xNxN−1 · · ·x2x1
Given a word which is not a palindrome, we may insert letters so that the word becomes a palindrome.
Some insertions are less efficient than others: for example, the word “BATHTUB” can be made into a
palindrome by rather clumsily adding 6 letters to form “BUTBHTATHBTUB”, or more efficiently, by
adding 2 letters: “BAUTHTUAB”.
In this problem, we solve the following problem: Given a word x = x1x2 · · · xN , what is the minimum
number of characters that need to be inserted to make it a palindrome?
Let fi,j be the minimum number of characters that need to be inserted to make x = xi . . . xj into a
palindrome (where i ≤ j). Then the solution to our question will be given by f1,N .
8.a. [8 points] Find a dynamic programming formula for fi,j. Hint: Consider cases on whether xi = xj
or xi 6= xj
Solution:
CSE 101 Final Exam Page 20 of 25
8.b. [6 points] Implement your dynamic programming formula from part (a) on the following problem
instance:
x = x1x2x3x4x5x6 = SIZZLE
Solution:
j = 1 j = 2 j = 3 j = 4 j = 5 j = 6
i = 1
i = 2
i = 3
i = 4
i = 5
i = 6
CSE 101 Final Exam Page 21 of 25
8.c. [6 points] Provide a time analysis of your algorithm.
Solution:
CSE 101 Final Exam Page 22 of 25
9. Design a Graph Algorithm [20 points] Consider a connected weighted directed graph
G = (V,E,w). Define the fatness of a path P to be the maximum weight of any edge in P . Give an efficient
algorithm that, given such a graph and two vertices u, v ∈ V , finds the minimum possible fatness of a path
from u to v in G. Full points given for algorithms with time complexity O((|V |+ |E|) log |E|) or better.
9.a. [10 points] Provide a high-level description of your algorithm. (Save time analysis for next part)
Solution:
CSE 101 Final Exam Page 23 of 25
9.b. [10 points] Provide a time analysis of your algorithm.
Solution:
CSE 101 Final Exam Page 24 of 25
BONUS: Capacitated Vehicle Routing Problem [10 points] You have been
hired by a coffee roasting company to manage their delivery vehicle routing. The company has five
customers, A,B,C,D,E, and each customer requires the same amount of coffee to be delivered. The
company only has one truck, and the truck only has the storage capacity for 3 deliveries before needing to
return to the depot. The truck can make multiple trips from the depot. Our goal is to find a list of routes
for the truck so that
1. each route begins and ends at the depot,
2. each customer is visited exactly once,
3. the storage capacity of the vehicle is not exceeded.
minimize the total distance traveled by the truck. The following graph illustrates the distances between
each customer and the depot, while the table gives the shortest distance between nodes (where “O” denotes
the depot):
depot
3
A
2
B
4
C
2
D
3
E
5
6
4
4
2
O A B C D E
O 0 3 2 4 2 3
A 0 5 7 5 2
B 0 6 4 5
C 0 4 7
D 0 4
E 0
Solve the CVRP using the Parallel savings algorithm. Solution box continues on next page if needed.
Solution:
CSE 101 Final Exam Page 25 of 25
Solution box continued from previous page.
Solution: