算法代写 | Assignment Two

Question 1 (25 points)

A complete graph is an undirected graph G = (V, E) where there is an edge between any pair of nodes. Given a unit square in a 2D plane with its four corner coordinates are: (0, 0) – the most left bottom coordinate, (0, 1) – the most left top coordinate, (1, 1) – the most top right coordinate, and (1, 0) the most right bottom coordinate. We randomly choose n nodes within this square. Let node vi have a coordinate (xi, yi), where the values of both xi 0 and yi 0 are randomly drawn from an interval [0, 1], where xi and yi are random real numbers uniformly distributed between 0 and 1, 1 i n.

Let K(V ) = (V, E) be a complete graph with V = {vi | 1 i n}, the weight  (or cost) assigned to each edge (vi, vj) E is the Euclidean distance between nodes vi

a randomly generated complete graph. Denote by L(n) the weighted sum of edges of a

minimum spanning tree (MST) of a randomly generated complete graph K(V ).

Write code using one language such as C, C++, Java, or Python program that does the following tasks.

• Calculate the average weighted sum L(n) of MSTs of p randomly generated com- plete graphs with V = n, which is the sum of p MST costs divided by p, where p randomly generated complete graphs with each having n nodes need to be con- structed and p 50, using Kruskal’s algorithms when n = 100, 500, 1,000, and 5,000, respectively (10 points).
• Observe the changing trend of the value of L(n) with the growth of n, and explain why this happens. (2 points)
• Generate a randomly connected graph G of n nodes in a unit square as follows: choose n nodes randomly in the square where each node is represented by a coor- dinate (xi, yi) with 0 xi, yi 1, then choose two nodes randomly (e.g., node u is represented by coordinate (xi, yi) and node v is represented by coordinate (xj, yj)

Give the actual average running times of both Kruskal’s and Prim’s algo- rithms for finding MSTs in q randomly generated connected graphs with q = 50, when n = 100, 500, 1, 000, and 5,000, (10 points)with i = j), add an edge (u, v) into G, and assign the edge (u, v) a weight, which is the Euclidean distance between them. This edge addition procedure continues until the graph becomes connected.

• Observe the running time trends of both algorithms with the growth of the value of n in Part , and explain why there is such a difference between the running times of these two Notice that you should NOT include the graph generation time in your running time calculation.(3 points)

Your program should have the following properties.

1. Do not read any Write one line of output for each n, and at most 5 extra lines of explanatory output.
2. Store the graph as a symmetric matrix (a complete graph) or linked list represen- tations (a connected graph)
3. The minimum priority queue will be employed in the implementation of Prim’s algorithm, and the disjoint set data structures will be adopted in the implemen- tation of Kruskal’s algorithm and testing whether a graph is connected. You can implement these two data structures by yourself, or make use of them from your program language library if they do
4. To measure the running time of an algorithm, refer to a timing procedure in the exercise of the 2nd

What to submit:

Upload your file named as mst.c or mst.java containing the program to Wattle.

You also need to submit a report in the PDF format that contains the source code and its outputs, and the answers to part (i), part (ii), and part (iii) of the question.

Question 2 (15 points for COMP3600 and 10 points for COMP6466).

Q2.(a) You are given a string of n characters c1c2 . . . cn, which is a corrupted text doc- ument, in which all punctuation have vanished. You need to reconstruct the document, using the following dictionary that is in the form of Boolean function b(·):

For any string b(s) =     true       if s is a valid word, f alse     otherwise,

assuming that testing whether a string s is a valid word takes O(1).

• Devise an O(n2) time dynamic programming algorithm to determine whether a string c1c2 . . . cn can be reconstructed as a sequence of valid

(8 points for COMP3600 and 5 points for COMP6466)

• Analyze that the running time of your algorithm indeed is O(n2). (2 points)

Q2.(b)
Given an undirected, connected, weighted graph G = (V, E) with n = V nodes and m = E edges, assume that each edge is assigned a positive weight. There are only K distinct weights on its edges and K is a positive integer constant, i.e., for each edge e E, its weight is one of the values in w1, w2, w3, . . . , wK , where wj > 0 with 1  j   K. Devise an O(n + m) time algorithm to find a minimum spanning tree in G. (5 points for COMP3600 and 3 points for COMP6466)

Question 3 (10 points for COMP3600 and 8 points for COMP6466)

Given a social network that is represented by a directed graph G = (V, E) where V is the set of people and E is the set of people trust relationships, there is one directed edge (u, v) E from node u to node v if person u trusts person v with a certain degree trust, and this trust is measured by a value pu,v in the range between 0 to 1. The larger the trust value pu,v is, the higher the trustiness of u on v is. Notice that this trust relationship is not necessarily symmetric. In other words, if person a V fully trusts person b V , e.g., pa,b = 1, person b may not have any trust on person a, e.g., pb,a = 0.

Devise an efficient algorithm for finding a most trustable path P in G from a person s V to another person t  V  if path does exist such that the trust  value of P is maximized, where the trust value of a path Q consisting of nodes

Question 4 (7 points for COMP6466 only)

Given a communication network represented by an undirected, weighted graph G(V, E) and a non-negative integer delay bound L > 0, assume that for each  edge e E, the communication cost and communication delay on it are c(e) and d(e), respectively, where d(e) is a non-negative integer, a delay-constrained shortest path problem in G from a source node s  V  to a destination node t  V is to find a simple path (each node and each edge appear in the path at most once) such that the total cost of the edges in path P is minimized (i.e., the value of   eP  c(e) is m),inimized), while the accumulative delay

1. (a) Devise an efficient algorithm in terms of running time for this delay-constrained shortest path problem. (3 points)
2. (b) Analyze the time complexity of your algorithm. (2 points)
3. (c) For each edge e E in G, if its delay d(e) is a real number, instead of a non-negative integer, is your proposed algorithm in part (a) still applicable to the problem under this setting? If not, explain how to modify the proposed algorithm for this case briefly? (2 points)

E-mail: [email protected]  微信:dmxyzl003

E-mail: [email protected]  微信:itcsdx