2023年11月25日

算法分析 | COMP 3804/MATH 3804 Design and Analysis of Algorithms I Assignment 3

本次加拿大代写是一个关于算法分析相关的Assignment

Hand in your assignments on, or before Nov 14th 23:59. No late assignment will be accepted. Your assignment should be submitted online on Brightspace as a single .pdf file. The filename should contain your name and student number. No late assignments will be accepted.You can type your assignment or you can upload a scanned copy of it. Please, use a good image capturing device. Make sure that your upload is clearly readable. If it is difficult to read, it will not be graded. Whenever you are designing an algorithm you must address the three questions we are typically posing (correctness, complexity and improvement potential). The faster your algorithm, the better your mark.

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 |V | = 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!

Question 5:[15 points]

Consider the graph given in Figure 3 above.

• Run DFS on the graph and classify each edge as being either: Tree edge, Forward edge, Back edge, or Cross edge. Show and argue: the algorithm execution, pre(v) and post(v) time intervals and the edge-classification. (An edge type may or may not appear in a particular graph.)

• Find a topological order of the nodes or argue that no such order can exist.