math代写|算法代写|algorithm代写 : 典型的一个算法代写题目
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
n
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: Bipart.java, Rival.java, Run.java. You will
add your own code to only Bipart.java 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.
How you can test If compilation is successful, you can use “java bp.Run” or IDE equivalents to run
my test program. This runs all tests sequentially, but aborts at the first failure. Failures are represented
by exceptions with error messages.
You can use “java bp.Run 0” to run just test #0, for example. See also the “main” method and its
comment in the file.
Marking scheme If your code looks like an attempt at a general algorithm (as opposed to an attempt
at customizing for my test cases), you get 4 marks to start. In addition:
• If your code compiles: 1 more mark per test passed. But watch this requirment:
I will give each test case 1 second only on the Mathlab server. Timing out is a failure. Each test
case is timed separately. Hint: A quadratic-time algorithm is likely to exceed the time limit.
• If your code does not compile: 0 more marks.
If your code does not look like an attempt at a general algorithm, 0 to 3 marks depending on how far
off it is.
2