Description
Instructions:
In this class, assume we’re always using min-heap data structure for Dijkstra’s. Report runtime
accordingly.
In the algorithm design problems: use the algorithms from class, such as DFS, BFS, Dijkstra’s,
SCC (connected components), etc., as a black-box subroutine for your algorithm. So say what you
are giving as input, then what algorithm you are running, and what’s the output you’re taking from
it. You can use Explore (subroutine of DFS) as one of the black-box algorithms.
Here’s an example:
I take the input graph G, I first find the vertex with largest degree, call it v
∗.
I take the complement of the graph G, call it G. Run Dijkstra’s algorithm on G with
s = v
∗ and then I get the array dist[v] of the shortest path lengths from s to every
other vertex in the graph G. I square each of these distances and return this new array.
We don’t want you to go into the details of these algorithms and tinker with it, just use it as a
black-box as showed with Dijkstra’s algorithm above.
CS 3510 – HW 3. Due: 03/05/2020 Name: 2
Make sure to explain your algorithm in words, no pseudocode. Explain why it works
and stay and justify its running time.
Problem 1 [DPV] Problem 3.11 (edge on a cycle)
Design a linear time algorithm which takes as input an undirected graph G and a particular edge e
in it, and determines whether G has a cycle containing e.
CS 3510 – HW 3. Due: 03/05/2020 Name: 3
Problem 2 [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):
CS 3510 – HW 3. Due: 03/05/2020 Name: 4
Problem 3 [DPV] Problem 4.20 (building a new road)
There is a network of roads G = (V, E) connecting a set of cities V . Each road has an associated
length `e…
CS 3510 – HW 3. Due: 03/05/2020 Name: 5
Problem 4 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.
