Description
Problem 1 [DPV] Problem 3.15 (Computopia)
• Assume that the Town Hall sits at 1 single intersection.
• The mayor’s claim in (b) is the following: If you can get to another intersection, call it u, from
the Town Hall intersection, then you can get back to the Town Hall intersection from u.
• Note, linear time means O(n + m) where n = |V | and m = |E|.
Part (a):
Part (b):
Problem 2 Edge on MST
You are given a weighted graph G = (V, E) with positive weights, ci for all i ∈ E. Give a linear
time (O(|E| + |V |)) algorithm to decide if an input edge e = (u, v) ∈ E with weight ce is part of
some MST of G or not.
You should describe your algorithm in words (a list is okay); no pseudocode.