CSE 101 Midterm Exam Page 1 of 11
1. SSSP [22 points]
A
B
C
D
E
F
5
4
8
1
7
2
4
5
1
1.a. [5 points] Find the topological sorting of the vertices of the above graph.
CSE 101 Midterm Exam Page 2 of 11
1.b. [7 points] Using Bellman’s algorithm, find the single-source-shortest-paths (SSSP) solution
starting at vertex A to all other vertices of the above graph. Use the solution tree like we did in the
lectures. Note in each node of the tree the distance value to the source A. Also note on the edges (u, v)
the corresponding weights, c(u, v).
procedure initialize(G)
1. d[s] = 0
2. for all (v ∈ V \ {s}) do d[v] =∞
procedure relax(u, v)
1. if d[v] > d[u] + c(u, v) then d[v] = d[u] + c(u, v)
procedure Bellman(G, s)
1. initialize(G,s)
2. V ∗ = topSort(G)
3. while (V ∗ 6= ∅):
4. choose u ∈ V ∗ that is next in the topological order and delete u from V ∗
5. for all (u, v) ∈ E do relax(u, v)
CSE 101 Midterm Exam Page 3 of 11
1.c. [5 points] Prove the correctness Bellman’s algorithm in solving the SSSP problem.
CSE 101 Midterm Exam Page 4 of 11
1.d. [5 points] Let n be the number of vertices of G, m be the number of edges of G. Perform a
time-analysis of Bellman’s algorithm.
CSE 101 Midterm Exam Page 5 of 11
2. Properties of SSSP Algorithms [8 points] The following questions concern
Bellman/Ford, Dijkstra, and Bellman algorithms.
Each question can have multiple answers!
2.a. [2 points] This algorithm uses the Initialize and Relax function:
© Bellman / Ford
© Dijkstra
© Bellman
© none of the above
2.b. [2 points] In each phase, this algorithm relaxes ALL edges with starting vertices u where dist(u)
has changed (in the previous phase):
© Bellman / Ford
© Dijkstra
© Bellman
© none of the above
2.c. [2 points] In this algorithm, the the distance value of a vertex can be changed multiple times.
© Bellman / Ford
© Dijkstra
© Bellman
© none of the above
2.d. [2 points] This algorithm requires that the graph is acyclic.
© Bellman / Ford
© Dijkstra
© Bellman
© none of the above
CSE 101 Midterm Exam Page 6 of 11
3. Linear Programming I [10 points] Consider the following linear programming prob-
lem:
maximize 30x + 40y subject to
x ≤ 8 (1)
y ≤ 16 (2)
2x + y ≤ 24 (3)
x, y ≥ 0
.
3.a. [2 points] Construct the initial tableau for performing the Simplex algorithm:
s1
s2
s3
x y s1 s2 s3 −−
8
16
24
0
3.b. [8 points] Perform the first step of the Simplex algorithm.
x y s1 s2 s3 −−
CSE 101 Midterm Exam Page 7 of 11
4. Linear Programming II [20 points] A company produces two belts (A and B). The
profit is $4 for each produced belt of type A and $3 for each produced belt B. x = number of belts of type
A, y = number of belts of type B. How many belts of type A and type B need to be produced to achieve
maximum profit? Constraints:
(1) Capacity: Both machines can (together) produce a maximum of 1000 belts per day. An A-belt needs
twice as much production time as a B-belt.
(2) Leather: The leather delivery only allows the production of 800 belts per day (A and B together).
(3) A-Buckles: A-belts and B-belts use different belt buckles. There are 400 belt buckles for belts of
type A available per day.
(4) B-Buckles: There are 700 belt buckles for belts of type B available per day.
4.a. [5 points] Formulate this optimization problem as a linear programming model and specify
explicitly the slope of the objective function.
CSE 101 Midterm Exam Page 8 of 11
4.b. [5 points] Use the graphical method to solve this model (Hint: draw the constraints and objective
function).
(0, 0)
4.c. [2 points] What is the maximum profit and how many type A- and type B-belts should the
company produce on a daily basis to achieve this profit?
CSE 101 Midterm Exam Page 9 of 11
Consider the following part of the optimal simplex tableau (the slack variables s1, s2, s3, s4 represent the
unused capacity of the respective restrictions machine capacity, leather delivery, belt buckles A and belt
buckles B):
x y s1 s2 s3 s4
x 1 0 1 −1 0 0
y 0 1 −1 2 0 0
s3 0 0 −1 1 1 0
s4 0 0 1 −2 0 1
0 0 1 2 0 0
4.d. [2 points] How will the production program and profit change if the leather delivery is expanded
such that it is possible to produce 1 more belt?
4.e. [5 points] How does the production program and profit change when the machine capacity is
expanded to produce one more belt? What would be the maximum gain in profit achievable by expanding
the machine capacity?
4.f. [1 point] How would the production program and profit change if one additional belt buckle of
type B would be available?
CSE 101 Midterm Exam Page 10 of 11
5. BONUS: Graph Theory [10 points] Consider the following graph:
A
B
C
DEF
G
H
I
5.a. [5 points] Perform a depth-first-search (DFS), starting at vertex A, on the above graph. Use the
solution tree like we did in the lectures, enumerating the vertices in the order they are detected. Also note
on the edges (u, v) the corresponding weights, c(u, v).
CSE 101 Midterm Exam Page 11 of 11
5.b. [5 points] Prove the correctness of DFS.