CSCB63 Assignment 2  Winter 2020
Due 11.59pm, Monday Feb. 24, 2020
Only a subset of the questions will be graded however you are responsible for all the material on this assignment.

A
unicyclic graph is a connected graph with exactly one simple cycle. Give an efficient algorithm that, given a connected undirected graph
G = (
V, E) (represented by its adjacency lists) and a weight function
w :
E , finds a unicyclic subgraph of
G of minimum weight spanning
G. Prove that your algorithm is correct and analyze its worst case time complexity as a function of
n =
V and
m =
E . Note: the cycle itself need not include all vertices in
V .
HINT: You may find it easier to first prove a claim about unicyclic subgraphs of G of minimum weight spanning G and then use that claim to design your algorithm.
 As GPS technology becomes more and more prevalent in the automotive market, real time routing and traffic reporting are becoming available. This question deals with determining a route of least traffic between any two locations. Consider a set of roads and intersections. Through GPS feedback, it’s possible to know exactly how many cars are on a particular segment of the road and how fast they are moving. This information can then be used to calculate a “congestion factor” for the road segment. We will say that a road segment is a section of the road that lies between two intersections (and does not contain any intermediate intersections).

Suppose that you are given a set of road segments
R, a set of intersections
I, and a congestion factor for each road segment. Describe an ADT and an algorithm to determine a minimal set of road segments
S R such that one can travel between any two intersections in
I as efficiently as possible. By efficiently, we mean that the maximum congestion factor is minimized. For example, to get between intersections
A and
B, there may be two routes, one which has roads with congestion factors 1, 1, 3, 2 and one which has congestion factors 1, 4. Your algorithm should select the route with congestion factors 1, 1, 3, 2 as the objective is to minimize the maximum congestion factor. We select that route, because if a congestion factor of 4 means that the traffic is stopped, then it will still be faster to take the route that is longer, but where the traffic is moving.

 Since the traffic is constantly changing we would like to be able to dynamically update the set of routes described in part (a). Suppose that a road segment’s congestion factor increases from 2 to 5. Explain how to update your set of routes. Let C(r) represent the congestion factor of road segment r. You need to consider each of the following scenarios:
 r ∈ S and C(r) is decreased
 r ∈ S and C(r) in increased
 r ƒ∈ S and C(r) is decreased
 r ƒ∈ S and C(r) is increased