本次算法代写Algorithms可以使用C/C++/Java/Python等任意语言完成4个算法的任务，主要是以图算法求最优解为主。

### 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 *v _{i} *have a coordinate (

*x*), where the values of both

_{i}, y_{i}*x*

_{i}*≥*0 and

*y*

_{i}*≥*0 are randomly drawn from an interval [0, 1], where

*x*and

_{i}*y*are random real numbers uniformly distributed between 0 and 1, 1

_{i}*≤*

*i*

*≤*

*n*.

Let *K*(*V *) = (*V, **E*) be a complete graph with *V *= *{**v _{i} *

*|*1

*≤*

*i*

*≤*

*n*

*}*, the weight (or cost) assigned to each

__edge (__

__v___{i},

__v___{j}__)__

__∈__

__E____is th__e Euclidean distance between nodes

*v*

_{i}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 (*x*_{i},*y*) with 0_{i}*≤**x*_{i},*y*_{i}*≤*1, then choose two nodes randomly (e.g., node*u*is represented by coordinate (*x*_{i},*y*) and node_{i}*v*is represented by coordinate (*x*_{j},*y*)_{j}

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.**

- Do not read any Write one line of output for each
*n*, and at most 5 extra lines of explanatory output. - Store the graph as a symmetric matrix (a complete graph) or linked list represen- tations (a connected graph)
- 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
- 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 *c*_{1}*c*_{2} *. . . c _{n}*, 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 *s **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*(*n*^{2}) time dynamic programming algorithm to determine whether a string*c*_{1}*c*_{2}*. . . c*can be reconstructed as a sequence of valid_{n}

**(8 points for COMP3600 and 5 points for COMP6466)**

- Analyze that the running time of your algorithm indeed is
*O*(*n*^{2}). (**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

*w*

_{1}

*,*

*w*

_{2}

*, w*

_{3}

*,*

*. . . , w*, where

_{K}*w*0 with 1

_{j}>*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 *p _{u,v} *in the range between 0 to 1. The larger the trust value

*p*is, the higher the trustiness of

_{u,v}*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.,

*p*= 1, person

_{a,b}*b*may not have any trust on person

*a*, e.g.,

*p*= 0.

_{b,a}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 *P *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 *e**∈**P** **c*(*e*) is m),inimized), while the accumulative delay

- (a) Devise an efficient algorithm in terms of running time for this delay-constrained shortest path problem. (
**3 points**) - (b) Analyze the time complexity of your algorithm. (
**2 points**) - (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**)

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

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

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

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

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。