算法分析代写|COMP 3804/MATH 3804 Assignment 3

本次加拿大代写是一个算法分析的assignment

Question 1:[5 points]

Dijkstra’s algorithm is not applicable for negatively weighted edges. So, why don’t we just ”scale
everything up” by adding to each edge-weight: one plus the absolute value of the globally smallest
(negative) weight. This way, all weights are positive. Does the algorithm, when applied to the
modified graph, correctly compute the shortest path in the orginal graph? If so, give a proof; if
not, give a counter-example.

Question 2:[20 points]

Let us assume that we have a directed graph G =(V,E) with jV j = n nodes of which there are
k starting nodes from which we would like to know their shortest path distances to a common
destination node (many-to-one problem).

• We could solve the problem by applying Dijkstra’s algorithm k times, ones for each of the k
starting nodes. What is the time complexity (stated in terms of n and k)?

• Alternately, we could start at the destination node and somehow go backwards. Describe
how this would work, i.e., how would we modify Dijkstra’s algorithm and/or its input to
achieve this? Then, state the time complexity of this solution to our original problem. (Do
not forget to argue why the algorithm, as modified, is correct!)

Question 3:[15 points]

Suppose we want to compute the shortest path tree from node, A, using Bellman-Ford for the
graph shown below in Figure 1. Show how Bellman-Ford would work on this graphs as input.

Question 4:[15 points]

Let n be the number of vertices of a given triangulation of a convex polygon.

• How many triangles does the triangulation consist of? Prove your statement by induction
on n.

• Consider now the simplest algorithm for computing weighted shortest paths, as described
in class which places the same number of Steinerpoints on each edge of the triangulation.
Assume that we place, say 7 Steinerpoints, on each edge of the triangulation. Precisely, how
many edges does the algorithm add? Argue!


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


blank

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

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


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

blank

发表评论