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
