Problem 1
There are n basketball teams in the world. The ranking of these teams from the previous year is available. This year, some of these n teams played against each other and the winner of each game was determined. There were m games in total. The International Basketball Association wants to introduce a new performance criterion, called “domination factor”, defined as follows: Team i is said to “dominate” team j if we can find a chain of games such that j was beaten by a team that was beaten by a team that was beaten by a team ... that was beaten by i (observe that, according to this definition, domination can be bi-directional, i.e., i and j can dominate each other). Then, for each team i, the domination factor zi is defined as the rank of the best team (that is, the highest ranked team according to last year’s rankings) that is dominated by team i.
(a) Describe an O(m + n) time algorithm to compute the domination factor for all the n teams. (Hint: Use Depth-First-Search)
(b) Prove that your algorithm is correct.
Problem 2
Prove or disprove the following statements:
(a) Let G = (V,E) be a directed graph. For any uv ∈ E, if some run of Depth-First-Search (DFS) on G results in v.f u.f, then uv must be on a cycle.
(b) Consider any run of DFS on a directed graph G = (V,E). For any edge uv ∈ E, if there is a path from v to u in G, then uv cannot be a cross edge.
Problem 3 - Removed
This problem was removed because Dijkstra’s algorithm has not yet been taught.
Problem 4
Please upload evidence of completion of course evaluation (a screenshot of the confirmation page will suffice). Note: This is 20% of assignment grade.
