java代写/数据结构代写/算法代写: CSCB63 Assignment 2

1. [10 marks] This question is about the fact that there can be exponentially many shortest paths in a
graph. But proving that sentence involves annoying technicalities that distract from the core idea. So
here is a more convenient and still without-loss-of-generality version.
Prove that for every natural number n, there is an undirected graph of bn + c vertices such that for
some pair of vertices s and t in the graph, there are 2
shortest paths from s to t.
The constants b and c are up to you.
2. [18 marks] Given a directed graph G = (V, E), the strongly connected components graph GSCC of G
is the directed graph defined by V
SCC = {C | C is a SCC of G} and ESCC = {(Ci
, Cj ) | ∃(u, v) ∈
E where u ∈ Ci
, v ∈ Cj}. We can relax the definition of strongly connected by saying that G is
nearly strongly connected if for each pair of vertices s, t ∈ V , either there exists a path from s to t or
a path from t to s.
Answer the following questions to design an algorithm to recognize whether a graph G is nearly
strongly connected.
(a) [3 marks] Prove that GSCC is a directed acyclic graph (known as a DAG).
(b) [4 marks] Given a DAG G = (V, E), prove that G is nearly strongly connected iff there exists
an ordering of the vertices v1, v2, . . . , vn such that for all 1 ≤ j < n, (vj , vj+1) ∈ E. (c) [3 marks] Prove that if directed graph G = (V, E) is nearly strongly connected then there exists a vertex x ∈ V such that every vertex in V is reachable from x. (d) [4 marks] Design an algorithm that tests whether a directed graph is nearly strongly connected. You may use the results from (a) to (c). (e) [4 marks] Prove your algorithm from part (d) is correct and give it’s complexity. 3. [10 marks] 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 → R, 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 . 4. [12 marks] (Like textbook exercise 22.2-7.) There are two types of professional wrestlers: “babyfaces” (“good guys”) and “heels” (“bad guys”). Between any pair of professional wrestlers, there may or may not be a rivalry. Implement an algorithm that takes a group of wrestlers and a list of pairs of wrestlers for which there are rivalries, and computes whether it is possible to designate some of the wrestlers as babyfaces and the others as heels, such that each rivalry is between a babyface and a heel. For simplicity, if there are n wrestlers, they are identified by the integers from 0 to n − 1. So your method signature is public bool bipartable(int numWrestlers, Rival[] rivalries) where the Rival class is just a pair of int’s: 1 public class Rival { public int x, y; // there is a rivalry between wrestlers #x and #y ... } The starter code and the test program are on Blackboard:,, You will add your own code to only and submit it. If you wish to work in Python, a Python version will be up before reading week. Package declaration All files declare “package bp;” for best results with IDEs. Please try not to change it. This means if you use the command line, you need to: put the files under subdirectory bp. Then there are several ways to compile and run. Here is one: outside bp, javac bp/*.java java bp.Run There are other ways. What works for you is good.


电子邮件地址不会被公开。 必填项已用*标注