CSCB63 Assignment 2 - Winter 2020 (Python代写,北美程序代写,加拿大程序代写,University of Toronto代写,CSCB63代写)

A unicyclic graph is a connected graph with exactly one simple cycle.

微信: biyeprodaixie 欢迎联系咨询

本次CS代写的主要涉及如下领域: Python代写,北美程序代写,加拿大程序代写,University of Toronto代写,CSCB63代写

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.



→ R

|  |            | |

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.

  1. 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.
    1. 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
    1. Consider now that the traffic on roads is really directed, in that one direction will have different congestion rates than the opposite direction (and further that some roads are one-way). We can pose the same problem as in part (a) but now each road segment has a direction. Can you use your algorithm from part (a) to solve this problem? You may assume that the set R now contains directed road segments (a one way road will be represented by one item in R and a two way road by two items in R each of which have a different congestion factor). If yes, give a careful explanation of why it works and whether the complexity remains unchanged. If no, give an example that illustrates how the algorithm would fail.
  1. Your friend claims that the algorithm for strongly connected components would be simpler if it used the original (instead of the transpose) graph in the second depth-first search and scanned the vertices in order of increasing finishing times. Does this simpler algorithm always produce correct results? Give a proof for your answer.
  2. Programming question to be uploaded to MarkUs soon.