Date structures and analysis of algorithms (CS340a) Final Examination (Three Hour)
Problem 1. (10 marks) In big O notation for worst case, what is the time complexity of: a) mergsort.
b) finding summation of n numbers with n processors.
c) Maximum-Cost Spanning Tree.
d) Single-Source Longest Paths in a weighted directed graph with non-positive weights. e) All-pair shortest paths.
Problem 2. (5 marks) a). (4 marks) Prove, by using the definitions of O and Ω, the following: n = O (n − log2(n))
2n − n = Ω(2n)
Problem 3. (10 marks) (Short answer. Your answer should be yes or no. If the answer is no, explain why)
a) Dijkstra algorithm for Single-Source Shortest Paths works even if there are negative weights.
b) Dijkstra method for finding Single-Source Shortest Paths can be used to find the Single-Source Longest Paths assuming that all the weights are non-negative.
c) Minimum-Cost Spanning Tree for a graph will not change if all the weights are multiplied by a constant c.
d) Graphs G1 and G2 have the same transitive closure iff G1 = G2.
e) If 3SAT is not in P then Graph 3-coloring is in P .
Problem 4. (15 marks) A directed graph G = (V, E) is given in the figure.
a) Show an adjacency list presentation of the graph.
b) Find a DFS tree starting from vertex v using the adjacency list representation in a).
c) Show the shortest-path tree from v to all the other vertices.
d) Now assume that the same graph is undirected, show the minimum cost spanning tree of G.
Problem 5. (15 marks) Given a connected, undirected, weighted graph G = (V, E), define the cost of a spanning tree to be the maximum weight among the weights associated with the edges of the spanning tree.
Design an efficient algorithm to find the spanning tree of G which maximize above defined cost. What is the complexity of your algorithm.
1
Problem 6. (15 marks) Let G = (V,E) be a connected, undirected, weighted graph with non- negative weights. Let v be a vertex of G. Given a spanning tree T of G, denote by c(v,w) the summation of the weights along the simple path from v to w on T (c(v, v)=0)). We then define the cost of spanning tree T by
cost(T ) = max c(v, w). w∈V
Design an efficient algorithm to find the spanning tree of G which minimize this cost.
Problem 7. (15 marks)
Given n real numbers x1, x2, …xn. Let rank(xi) = |{xk|xk ≤ xi}| for 1 ≤ i ≤ n.
a) Given index i0, design an O(log(n)) time CREW algorithm to compute rank(xi0 ) with n pro- cessors.
b) Design an O(log(n)) time EREW algorithm to do the same with n processors.
c) Assume that x1, x2, …xn are all distinct, design an CREW O(log(n)) time sorting algorithm with n2/log(n) processors.
Problem 8. (15 marks)
a) Let G = (V, E) be an undirected graph such that, for any vertex v, degree d(v) (number of edges incident to v) is bounded by 3. Given such a graph and an integer k we want to determine if G contains a clique of size ≥ k. Show that this problem is in P . Dose this contradict to the fact that Clique Problem is NP − complete.
b) The composite numbers problem is define as follows:
Given an positive integer K, determine if there are integers m, n > 1 such that K = m · n.
There is an O(√K) time algorithm solving this problem. Is this problem in P? Why?
2