2021/8/15 Submit Exam4 | Gradescope
https://www.gradescope.com/courses/270292/assignments/1414323/submissions/new 1/4
0/5 Questions Answered
TIME REMAINING
� hr �� mins
Exam4
Q1 P vs NP
10 Points
a) Suppose we know that problem X is NP-complete.
We want to show that problem Y is NP-complete. What might we do
about this?
You will receive credit even for very short answers that use correct
keywords, but I’d like you to include some explanation for full credit. A
few lines should suffice.
Enter your answer here
b) Does anything change if we know that X is NP-hard, instead of NP-
complete?
Enter your answer here
Q2 MST — Provide short but convincing
answers
20 Points
a) Prim
Alex has implemented Prim’s algorithm and wants to run it on a graph
where some of the weights are negative. Joe suggests adding a large
number to every weight, so that they all become positive, but Alex is
2021/8/15 Submit Exam4 | Gradescope
https://www.gradescope.com/courses/270292/assignments/1414323/submissions/new 2/4
worried that the MST structure will change.
What do you tell them? (Suppose that you’re their TA).
Enter your answer here
b) Kruskal
Did the analysis of Kruskal’s algorithm (shown in class) need an
assumption about the representation of the graph?
In other words, does anything change if the graph is represented as
an adjacency list or adjacency matrix? Explain.
Enter your answer here
Q3 SSSP — Provide short but convincing
answers
20 Points
a) Dijkstra
Consider the set of directed graphs with vertices and edges,
containing precisely one negative edge weight but no negative cycles.
If we run standard Dijkstra on such a graph, in the worst case how
many vertices might end up with an incorrect score? Explain.
Enter your answer here
b) Bellman-Ford
Let be a weighted graph without negative cycles. We
run BFS on starting at vertex , and we observe that vertex v is
levels underneath in the BFS tree. In other words we can get from
to v using only edges.
Can we conclude that we actually don’t need to relax edges leading
V E
G = {V ,E}
G S k
S
S k
2021/8/15 Submit Exam4 | Gradescope
https://www.gradescope.com/courses/270292/assignments/1414323/submissions/new 3/4
directly into , after the -th iteration of Bellman-Ford? (using as the
source). Explain.
Enter your answer here
Q4 Catching an agent
25 Points
Let be a connected graph.
You are able to run around on at some fixed speed, and are chasing
an agent who can also run at the same speed. At any point in time,
your special satellite tells you exactly where the agent is, so you
always know what direction to move in, towards the agent. The
problem is, you can never catch up to the agent unless you somehow
corner them.
Unavoidably you must ask for help: in the middle of each edge of
there is a mercenary guard, who can catch the agent if they try to pass
through. Each guard can’t move, and also charges a fee for their
services. (The fees are not all the same).
You must decide who you will hire, before the chase begins.
State how how many guards you hire, and how to minimize the total
cost of hiring them.
Try to justify your claims. You may use concepts from class without
reproving, but you should still justify using such concepts, or explain
what needs modification, if applicable.
Enter your answer here
Q5 Min-weight path
25 Points
v k S
G = {V ,E}
G
G
2021/8/15 Submit Exam4 | Gradescope
https://www.gradescope.com/courses/270292/assignments/1414323/submissions/new 4/4
Let be a complete undirected graph with positive edge
weights, a source vertex and a target vertex . Recall, “complete”
means all possible edges are present.
Every edge is colored either red or blue. There are red edges and
blue edges.
A path in is defined as valid if it uses at most one red edge.
a) What is the time complexity of deciding if a valid path from to
exists?
Enter your answer here
b) How do you find a min-weight valid path from to , assuming at
least one valid path exists? What is the time complexity?
Enter your answer here
Submit & View Submission
G = {V ,E}
S T
R
B
G
S T
S T
https://www.gradescope.com/courses/270292/assignments/1414323/submissions/84959231