Name (printed):
Student PID:
CSE 101
Final Exam
Design and Analysis of Algorithms
UC San Diego
Summer Session II 2021
Date: 09/04/21
Time limit: 180 Minutes
Question 1 2 3 4 5 6 7 8 Total Bonus question
Points 12 11 10 12 30 25 25 25 150 25
This exam contains 18 pages, plus this cover page.
Please write your name and PID at the top of this page, and please read and sign the academic integrity
acknowledgement below.
Academic integrity is expected of all students at all times, whether in the presence or absence of members
of the faculty. Understanding this, I declare I shall not give, use, or receive unauthorized aid in this
examination.
Signature of student:
I consent to being recorded during the course of the examination which may be used in case of Academic
Integrity violation.
Signature of student:
CSE 101 Final Exam Page 1 of 18
1. Knapsack [12 points]
A set of 4 items each with a value and a weight is given in the following table. The capacity of the knapsack
is 11 and each item can be taken at most once:
A B C D
Values 20 40 70 90
Weights 2 3 4 5
1.a. [2 points] Apply the Largest-Relative-Value heuristic to find a feasible solution.
1.b. [10 points] Solve the problem with Branch-and-Bound. Use the solution value of the Largest-
Relative-Value heuristic as the first Best Upper Bound, UB1. Give the items and the total value of the
items. 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.
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.
6.The vertex with the Best Lower Bound is an optimal solution.
CSE 101 Final Exam Page 2 of 18
CSE 101 Final Exam Page 3 of 18
2. Capacitated Vehicle Routing Planning [11 points]
Consider the following graph on the left. The depot is marked with O. The distances of the direct routes
to get from one place to another on the respective route is shown at each edge. On the right, the distances
of the shortest paths from one place to another place are displayed.
O
A
C
B
D E
F
6
9
4
6
3 55 7 1
4
2
O A B C D E F
O 0 6 15 4 10 12 13
A 0 9 3 9 11 12
B 0 11 5 7 4
C 0 6 8 9
D 0 2 3
E 0 1
F 0
There are Q = 15 units per truck available and the demands of the customers are:
A B C D E F
4 6 6 7 2 4
2.a. [2 points] Calculate the total length of the tour planning if only round trips are used.
2.b. [2 points] Complete the table with the Savings values sA,D and sD,F .
O A B C D E F
O – – – – – – –
A – – 12 7 7 7
B – – – 8 20 20 24
C – – – – 8 8 8
D – – – – – 20
E – – – – – – 24
F – – – – – – –
CSE 101 Final Exam Page 4 of 18
2.c. [7 points] Apply the Savings heuristic for the Capacitated Vehicle Routing Planning. Hints:
�Use the savings values in descending order. Break ties lexicographically.
�A tour can be closed when the demands of the remaining customers are larger than the remaining
capacity. You can delete in that case all of the savings values with at least one customer that is already
planned on that tour.
Show all your work, especially which Savings values you chose and when a tour can be closed
and then answer the following questions:
�Which tours did you generate?
�What are the total demands, savings and distances of each tour?
CSE 101 Final Exam Page 5 of 18
3. Travelling Salesperson Problem [10 points]
You are given a graph where the vertices represent cities and the edges between cities represent the distances
between the connected cities.
J G
E
D
F
H
O
CB
8
3
9
4
101
5 3
7 4
7
5
2
8
2
3 6
3.a. [4 points] Determine the Minimum Spanning Tree (MST) using the algorithm of Prim with start-
ing node O. Break ties using alphabetical order.
J G
E
D
F
H
O
CB
3.b. [6 points] Determine a round trip that starts and ends in node O, and is generated with the
MST-heuristic. Make sure to show the intermediate steps, and calculate the lengths of both,
�the intermediate round trip (an Euler circuit without shortcuts) and
�final round trip (an Euler cycle with shortcuts).
Hint: Break ties in lexicographic order, e.g. when you have the choice to select either (F,E) or (F,G),
you should at first choose (F,E).
J G
E
D
F
H
O
CB
CSE 101 Final Exam Page 6 of 18
4. Linear Programming [12 points]
max 2x + 3y
s.t.
x + y ≤ 20 (1)
2x + y ≤ 18 (2)
x + 2y ≤ 24 (3)
x, y ≥ 0 (4)
4.a. [5 points] Fill in the initial Simplex Tableau and perform the first Simplex step.
x y s1 s2 s3
s1
s2
s3
x y s1 s2 s3
CSE 101 Final Exam Page 7 of 18
The following tableau is the optimal tableau.
x y s1 s2 s3
s1 0 0 1 −1/3 −1/3 6
x 1 0 0 2/3 −1/3 4
y 0 1 0 −1/3 2/3 10
z 0 0 0 1/3 4/3 38
4.b. [1 point] What are the optimal values of the decision variables (x and y) and what is the maximum
value of the objective function?
4.c. [3 points] Give an interpretation of the final values of the slack variables.
4.d. [3 points] How would the maximum value of the objective function and the values of x and y
change if constraint (2) would change to 2x + y ≤ 24?
CSE 101 Final Exam Page 8 of 18
5. Proofs [30 points]
5.a. [8 points] Prove that Bin Packing is NP-complete and use P || Cmax.
[Bin Packing]: 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 disjoint subsets U1, U2, . . . , UK such
that the sum of the sizes of the items in each Ui is B or less?
[Parallel processor scheduling (with m processors): P || Cmax] Given an arbitrary large number m
parallel and identical processors, n jobs with positive integer processing times p1, p2, . . . , pn and a number
z. Does there exit a schedule with makespan not more than z (preemptions not allowed)?
Please use the proof structure that we used in the homework questions.
Step 1: Prove Bin Packing is in NP.
Step 2: Select a known NP-Complete problem: P || Cmax.
Step 3: Show how to compute (in polynomial time) a specific input for Bin Packing given an arbitrary
input for P || Cmax.
Step 4: With your construction in Step 3, show P || Cmax is reducible to Bin Packing.
CSE 101 Final Exam Page 9 of 18
5.b. [5 points] 1. Argue why a solution to Bin Packing that uses only 2 bins might implicitly solve a
Partition problem. 2. How can that observation help to prove that there cannot be a polynomial time
approximation algorithm for Bin Packing with an approximation ratio strictly less than 3
2
(assuming
P 6=NP)?
5.c. [7 points] Dijkstra’s algorithm for SSSP. Draw a weighted directed connected graph with 4 vertices
A, B, C, D that has no negative cycles where Dijkstra’s algorithm doesn’t work. Explain why Dijkstra’s
algorithm cannot be applied to that graph.
CSE 101 Final Exam Page 10 of 18
5.d. [10 points] Optimality of Greedy Algorithms. We want to prove that SPT is optimal for 1 ||
∑
Cj
(please find below a formal description of the problem).
(i) If in the schedule T = (T1, T2, . . . , Tn) there exist jobs Ta and Tb with a < b but pa > pb, then this is
an inversion. Fill in the completion times Cj of the schedule T = (1, 2, 3, 4, 5). What is the sum of the
completion times? Find the inversion (Ta, Tb) between jobs Ta and Tb in the schedule T .
j 1 2 3 4 5
pj 10 20 40 30 50
Cj
Sum of completion times:
Inversion:
(ii) Show for the example from part (i) that removing an inversion by swapping the two jobs can only
decrease the sum of the completion times.
(iii) Prove with the observation from (ii) that SPT is optimal for 1 ||
∑
Cj. Assume that T is an optimal
schedule that has inversions and prove explicitly:
�If there is an inversion in the schedule T , then there are two adjacent jobs a and b with completion
times Ca and Cb at positions i and i + 1 that are inverted.
�Let sa and sb be the original start times of jobs Ta and Tb, respectively. Let s
new
a and s
new
b be the start
times of jobs Ta and Tb, respectively, after we removed that inversion, i.e. swapped these two jobs.
Why is Cnewa + C
new
b ≤ Ca + Cb correct?
Remember that the scheduling problem 1 ||
∑
Cj is defined as follows: We are initially given a set J =
{J1, J2, . . . , Jn} of jobs. Each job Jj has associated with it an integer processing time (job length) pj ≥ 1. Given
some permutation π of J , say π(J) = T = (T1, T2, . . . , Tn) with corresponding processing times (t1, t2, . . . , tn), the
jobs are placed sequentially as follows. The initial job T1 in the list T begins at time 0 and finishes at time t1. In
general, Tj+1 begins as soon as Tj is completed. This procedure results in a unique placement (or schedule) of the
jobs. We define the sum of the completion times as τ(T ) =
∑n
j=1Cj . A natural goal is for a given job set J , to
find those permutations T = π(J) which minimize the sum of the completion times τ(T ). The SPT-permutation
(SPT) is a permutation where t1 ≤ t2 ≤ . . . ≤ tn.
CSE 101 Final Exam Page 11 of 18
6. Design your own algorithm: Graph [25 points]
Alice and Bob are stranded on opposite sides of a big island. The map of the island is given by a directed
graph where each edge in the graph takes 1 hour to traverse. Each hour each of the two travellers can
either traverse an edge or stay where they are. Give an algorithm that given the map of that island along
with the initial location of Alice and Bob computes the minimum amount of time required for them to
meet at the same location.
6.a. [15 points] Describe your algorithm. For full credit, your algorithm should run in linear time
O(n + m) or better, where m and n denote the number of edges and vertices, respectively.
CSE 101 Final Exam Page 12 of 18
6.b. [5 points] Give a brief explanation why your algorithm works.
6.c. [5 points] Analyze the runtime of the algorithm.
CSE 101 Final Exam Page 13 of 18
7. Design your own algorithm: Divide-and-Conquer [25 points]
Given an array of non-zero integers (A[1], . . . , A[n]), with the property that A[1] > 0 and A[n] < 0. Design
a Divide-and-Conquer algorithm that finds an index i such that A[i] > 0 and A[i + 1] < 0. Note that if
there are multiple indices with this property, your algorithm only needs to find one of these.
For example, if your input is (10, 8,−4, 3, 3,−6), then your algorithm should return 2 OR 5, since we have
A[2] = 8 > 0, A[3] = −4 < 0 and A[5] = 3 > 0, A[6] = −6 < 0.
7.a. [15 points] Describe your algorithm. For full credit your algorithm should run in time O(log n) or
better.
CSE 101 Final Exam Page 14 of 18
7.b. [5 points] Give a brief explanation why your algorithm works.
7.c. [5 points] Analyze the runtime of the algorithm.
CSE 101 Final Exam Page 15 of 18
8. Design your own algorithm: Dynamic Programming [25 points]
A subsequence of a string is a new string generated from the original string with some characters (can
be none) deleted without changing the relative order of the remaining characters. For example, ”aday”
is a subsequence of ”gadwaya”. A common subsequence of two strings is a subsequence that is common
to both strings. Given two strings s1 and s2 of lengths m and n, return the length of their Longest
common subsequence. If there is no common subsequence, return 0. Let L(m,n) be the length of the
Longest common subsequence ending at positions m for the string s1[1 . . .m] and at position n for the
string s2[1 . . . n].
8.a. [15 points] Describe your Dynamic Programming algorithm. Work out explicitly the Dynamic
Programming solution for the strings s1 = gadwaya (m = 7) and s2 = amday (n = 5). For full credit your
algorithm should have runtime O(mn) or better.
- g a d w a y a
- 0 0 0 0 0 0 0 0
a 0
m 0
d 0
a 0
y 0
CSE 101 Final Exam Page 16 of 18
8.b. [5 points] Give a brief explanation why your algorithm works.
8.c. [5 points] Analyze the runtime of the algorithm.
CSE 101 Final Exam Page 17 of 18
9. Bonus Questions: Design a graph algorithm and
Assignment revisited [25 points]
The critical cost of a path from s to v is equal to the maximum length of one of its edges. Design an
algorithm to compute for any vertex v ∈ V the smallest critical cost of any s− v-path.
9.a. [8 points] Describe your algorithm. For full credit your algorithm should have runtime O(mn) or
better, where m and n denote the number of edges and vertices, respectively.
9.b. [4 points] Give a brief explanation why your algorithm works.
9.c. [3 points] Analyze the runtime of the algorithm.
CSE 101 Final Exam Page 18 of 18
Let’s now look at the Branch-And-Bound-strategy to solve minimization problems such as the Assignment-
problem. The procedure we had so far uses a row-min-strategy to compute lower bounds. The reasoning
behind it is that each agent (e.g. A,B,C,D) needs to perform exactly one of the tasks (e.g. T1, T2, T3, T4).
A column-min-strategy would obviously be as well possible.
9.d. [2 points] What is the meaning of a lower bound for a minimization problem such as the
Assignment-problem?
9.e. [2 points] What is (similar to the row-min-strategy) the idea behind a column-min-strategy to
compute lower bounds for the Assignment-problem?
9.f. [2 points] When is a lower bound for a minimization problem better than another lower bound?
Reason your answer.
9.g. [4 points] Find a problem instance with 2 agents A,B and two tasks T1, T2 where the lower bound
calculated by a column-min-strategy is better than the lower bound calculated by a row-min-strategy.