本次美国代写是关于Python算法分析相关的assignment

Instructions:

• This homework is due by 11:59PM Pacific Time on Thursday, November 18th. You will receive a one-time grace period allowing you to submit a homework assignment up to two days late. Subsequent assignments submitted up to two days late will incur a 20% penalty. Assignments submitted more than two days late will not be graded and will receive a score of 0.

• You must submit your written solutions as a single .pdf file on Canvas with your name at the top. Typesetting your written solutions using LATEX is strongly encouraged. You must submit your programming solutions for Question 3 as a single .cpp, .java, or .py file depending on your choice of language.

• You are welcome and encouraged to discuss the problems in groups of up to three people, but you must write up and submit your own solutions and code. You must also write the names of everyone in your group on the top of your submission.

• The primary resources for this class are the lectures, lecture slides, the CLRS and Erickson algorithms textbooks, the teaching staff, your (up to two) collaborators, and the class Piazza forum. We strongly encourage you only to use these resources. If you do use another resource, make sure to cite it and explain why you needed it.

• Scoring: The total score is 50 points, with the possibility of up to 5 extra credit points.

Question 1 (Minimum Spanning Trees and Shortest Paths, 18 points.) In this problem, you will run each of Kruskal’s Algorithm, Dijkstra’s Algorithm, and Prim’s Algorithm for computing minimum spanning trees (it computes the same thing as Kruskal’s Algorithm but looks nearly identical to Dijkstra’s Algorithm) on the graph G in Figure 1, taking s = v1 as the source vertex for the latter two algorithms. Pseudocode for a version of Dijkstra’s Algorithm slightly different from the one we saw in class and for Prim’s Algorithm appears below.

Note that the pseudocode for Dijkstra’s Algorithm and Prim’s Algorithm is nearly identical. The only substantive difference between the two algorithms (which is very important) is that in Dijkstra’s Algorithm the priority of a vertex v in Q is the distance of v from s using only edges with at least one endpoint in S whereas in Prim’s Algorithm it’s the lowest weight of an edge connecting v to some vertex in S.

This version of Dijkstra’s Algorithm is very similar to the one we saw in class. The only difference is that now instead of just computing distances δ(v,s) between each vertex v and s, it’s additionally storing the predecessor vertex v.pred of each vertex v. Recursively following the predecessor pointers v.pred of a vertex v back to s allows for easily computing the shortest path between s and v (not just its length). The set of all n − 1 edges {{u.pred,u} : u ∈ V \ {s}} to predecessor vertices output by

Dijkstra’s Algorithm (respectively, Prim’s Algorithm) forms a minimum spanning tree (respectively, shortest-paths tree with source vertex s).

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

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

E-mail: itcsdx@outlook.com  微信:itcsdx

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