CS 340 Advanced Data Structures and Algorithm Design

(Top) The inputs, N with its costs, server s = 0, and T = 5. In each vertex in the above picture, its label/index is given along with its tag. (Bottom) The resulting tagging of the vertices in N and after tagging N, value 6 is returned. Notice that vertex 3 is not tagged as there is no edge incident on 3 that has a cost to tag at most 5. 

In this problem we will presume N is represented as an adjacency list, this will be relevant mainly for part (b).

 

a) [4 marks] Given a weighted connected graph N = (V, E), a server vertex s E V, and an integer T, design an algorithm that solves the above problem. Present your algorithm as pseudocode, it must take at most 0(m + n) worst-case time. Please include 1-3 sentences before your pseudocode, in your own words, briefly describing what your algorithm does. To receive full marks, your pseudocode must be clear and has to be correct.

 

b) [2 marks] Compute the worst-case time complexity of your algorithm as a function of the number n of vertices and number m of edges in N. You must explain how you computed the time complexity, and give the time complexity of the algorithm using Big Theta notation.

 

c) [1 mark] Describe an instance of the above problem and its solution, akin to the above example, where every single vertex, except s, has tag oo and the value returned equals 1. Provide 2-3 sentences, in your own words, summarizing your example briefly and how this occurs.

 

d) [1 mark] Like in the above example, notice that there will be instances where not all the vertices in the graphs are tagged with an integer; however, there are instances where all the vertices are tagged with an integer. Give a value for T that guarantees (it may depend on information in N), for any network N as described above, where every vertex will be tagged with an integer. Do not just write oo, I am looking for an actual expression for T. Provide a couple sentences of why your value for T will work, given any input graph N.