# Python算法分析代写 | Analysis of Algorithms Homework 3

Instructions:

• This homework is due by 11:59PM Paciﬁc 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 ﬁle 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 ﬁle 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 staﬀ, 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 diﬀerent 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 diﬀerence 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 diﬀerence 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).

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