CSE 101 Final Exam Page 1 of 21
1. SSSP [12 points]
A
B
C
D
E F
5
4
8
1
7
2
4
5
1
1.a. [4 points] Find the topological sorting of the vertices of the above graph using Kahn’s algorithm.
Use the tabular method as we did in lecture.
Solution:
A
B
C
D
E
F
CSE 101 Final Exam Page 2 of 21
A
B
C
D
E F
5
4
8
1
7
2
4
5
1
1.b. [4 points] Using Dijkstra’s algorithm, find the single-source-shortest-paths (SSSP) solution start-
ing 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 corre-
sponding weights, c(u, v).
Solution:
CSE 101 Final Exam Page 3 of 21
A
B
C
D
E F
5
4
8
1
7
2
4
5
1
1.c. [4 points] Using Bellman/Ford’s algorithm, find the single-source-shortest-paths (SSSP) solu-
tion starting at vertex A to all other vertices of the above graph. Relax the edges in lexicographic order:
(A,B), (A,C), (A,D), (B,C), (B,E), (C,D), (C,F), (D,F), (F,E) , and complete the following table:
Solution:
A B C D E F
Initialization
Phase 1
Phase 2
Phase 3
Phase 4
CSE 101 Final Exam Page 4 of 21
2. Knapsack problem [12 points]
Consider the Knapsack Problem: a set of 5 items each with a value and a weight is given in the following
table. The capacity of the knapsack is 13.:
A B C D E
Values 30 40 50 80 100
Weights 2 3 4 5 9
2.a. [2 points] Apply the Largest-Relative-Value heuristic to find a feasible solution.
Solution:
The problem continues on the next page.
CSE 101 Final Exam Page 5 of 21
Now assume that the first three “levels” of the Branch-and-Bound tree have been completed:
E is out, D is in, and C is in.
A B C D E
Values 30 40 50 80 100
Weights 2 3 4 5 9
The current lower bound LB2 is 160.
2.b. [10 points] Carry out the last 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.
The Knapsack (Branch and Bound) algorithm is on the last page of the exam, if needed.
Solution:
in out
in
out in
out
CSE 101 Final Exam Page 6 of 21
3. Scheduling [12 points] Parts (a) and (b) concern the following 5 jobs, which have to be
scheduled on a single processor.
jobs A B C D E F G H
processing times 5 8 14 8 6 10 7 11
due dates 6 20 27 31 32 19 16 15
3.a. [6 points] Schedule the job according to Moore’s algorithm. Box the total number of late jobs.
Solution:
CSE 101 Final Exam Page 7 of 21
Part (c) concerns the same 8 jobs, which have to be scheduled on three parallel and identical processors.
jobs A B C D E F G H
processing times 5 8 14 8 6 10 7 11
3.b. [3 points] Schedule the jobs so that the makespan is minimized (no preemptions allowed).
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
3.c. [3 points] Schedule the jobs so that the sum of completion times is minimized (no preemptions
allowed).
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 8 of 21
4. APSP [12 points] Using Floyd-Warshall’s algorithm, find the all-pairs-shortest-paths of the
below graph. You may use the following page for scratch work.
A
B
C
5
−3
24
Solution:
u = A A B C
A 0
B 0
C 0
u = B A B C
A 0
B 0
C 0
u = C A B C
A 0
B 0
C 0
CSE 101 Final Exam Page 9 of 21
5. Traveling Salesperson Problem [12 points] Recall the Traveling Salesperson Prob-
lem: Given a list of cities and the distances between each pair of cities, find the shortest possible route
that visits each city exactly once and returns to the origin city.
The following problem instance has a starting city (O) and 6 cities to be visited, where each edge-weight
indicates the distance between each city.
O
A
B C
DE
F
12
9
10
12
1210
9
11
8
3
7
6 11
5.a. [4 points] Build the Minimum Spanning Tree using Prim’s algorithm.
Solution:
CSE 101 Final Exam Page 10 of 21
O
A
B C
DE
F
12
9
10
12
1210
9
11
8
3
7
6 11
5.b. [4 points] Using your answer from part (a), double the edges of your MST and build an Euler Cycle.
Break ties in alphabetical order. Clearly indicate the final path, and box the total distance.
Solution:
CSE 101 Final Exam Page 11 of 21
O
A
B C
DE
F
12
9
10
12
1210
9
11
8
3
7
6 11
O A B C D E F
O 0 12 19 21 12 10 13
A 0 9 18 17 9 7
B 0 10 17 9 6
C 0 12 11 11
D 0 8 11
E 0 3
F 0
Shortest-paths matrix (symmetric)
5.c. [4 points] Take shortcuts in your answer from part (b) to generate a solution to the Traveling
Salesperson problem. Clearly indicate the final path, and box the total distance.
Solution:
CSE 101 Final Exam Page 12 of 21
6. Algorithms and Proofs [20 points]
6.a. [6 points] Recall the Bin-packing problem: Given n items with weights w1, . . . , wn, pack the items
into bins of capacity C such that the total number of bins used is minimized.
Prove that the worst-case number of bins for Next Fit is (2− 1
n
)-times the optimal number of bins.
Solution:
CSE 101 Final Exam Page 13 of 21
6.b. [1 point] What is a prerequisite for using Dijkstra’s algorithm on a directed graph?
Solution:
6.c. [2 points] What is the advantage with respect to the runtime of Dijkstra’s algorithm in comparison
to Bellman/Ford’s algorithm?
Solution:
6.d. [3 points] Why is Dijkstra’s algorithm correct, i.e., why does it compute the shortest paths from a
single-source?
Solution:
CSE 101 Final Exam Page 14 of 21
6.e. [8 points] Subset Sum: Given a list of n positive integers s1, s2, . . . , sn and a positive integer z.
Does there exist a subset I ⊆ {1, . . . , n} such that
∑
i∈I si = z?
Zero Subset Sum: Given a list of n integers s1, s2, . . . , sn. Does there exist a subset I ⊆ {1, . . . , n}
such that
∑
i∈I si = 0?
Given that Subset-Sum is NP-complete, prove that Zero Subset Sum is also NP-Complete.
Solution:
CSE 101 Final Exam Page 15 of 21
7. Design a Graph Algorithm [20 points]
A map of a subway system is given by an undirected graph G. Each
edge of this graph is given a color to designate which of several
subway lines that edge is a part of.
You may assume that all of the edges in a given line are connected.
In particular, it is possible to get from any station on one line to
any other station on the same line without changing lines.
7.a. [12 points] Design a linear time algorithm that, given two vertices of this graph, returns the minimum
number of times that one would need to change trains in order to get from one vertex to the other.
Solution:
CSE 101 Final Exam Page 16 of 21
7.b. [8 points] Prove correctness of your algorithm.
Solution:
CSE 101 Final Exam Page 17 of 21
8. Design a Dynamic Program [20 points]
Given two strings, we may delete, insert, or replace symbols in one word until the two are the same. For
example, one way to transform the word “APPLE” into the word “PHONE” is:
APPLE → PPLE → PHLE → PHOE → PHONE (4 operations)
In this problem, we solve the following problem: Let s = s1s2…sn and t = t1t2…tm be two strings.
Assuming that all the symbols are uppercase letters from the Latin alphabet, what is the minimum number
of operations you need to transform string s to string t?
Let fi,k be the minimum number of operations needed to transform string s1s2…si to string t1t2…tk. Then
the solution to our question will be given by fn,m.
8.a. [12 points] Find a dynamic programming formula to solve the problem.
Solution:
CSE 101 Final Exam Page 18 of 21
8.b. [8 points] Implement your dynamic programming formula from part (a) on the following problem
instance:
s = s1s2s3s4 = RAIN, t = x1x2x3x4 = LAND
Solution:
j = 1 j = 2 j = 3 j = 4
i = 1
i = 2
i = 3
i = 4
CSE 101 Final Exam Page 19 of 21
BONUS: [20 points]
You are given a string S = s1s2 · · · sn of length n and an integer k (1 ≤ k ≤ 10). Each sj can be one of
the ten digits {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Problem: Find the length of the longest substring t = sisi+1 · · · si+m of the string s, such that t has
exactly k distinct characters.
For example, s = 7191010, k = 2. The answer is 4 (last four characters of s).
Another example: s = 8449454, k = 2. The answer is 4 (string 4494).
8.a. [12 points] Develop an algorithm that solves this problem.
Solution:
CSE 101 Final Exam Page 20 of 21
8.b. [8 points] Prove the time complexity of your algorithm.
Solution:
CSE 101 Final Exam Page 21 of 21
Algorithm Reference Page
Knapsack (Branch and Bound):
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: 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.