Homework Assignment #6 Solution

Question 1. (30 marks) Consider the following graph G:







Note: the nodes of G in alphabetical order are m, n, o, p, q, r, s, t, u, v, w, x, y, z.




(10 marks) Draw the Breadth-First Search tree generated by executing the BFS algorithm on the above graph G under the following assumptions: (i) The BFS starts at node p and (ii) the graph G is given by adjacency lists that are in alphabetic order, so the BFS explores edges in lexicographic order whenever there is a choice (e.g., edge (p; o) is explored before edge (p; s)). Show the d[a] value for every node a discovered by this BFS.



(10 marks) Draw the Depth-First Search forest generated by executing the DFS algorithm on the above graph G under the following assumptions: (i) the for loop of the DFS procedure considers the nodes in alphabetical order (so the DFS starts at node m) and (ii) the graph G is given by adjacency lists that are in alphabetic order, so the DFS explores edges in lexicographic order whenever there is a choice (e.g., edge (m; q) is explored before edge (m; x)). Show the d[a] and f[a] values for every node a of the graph G, as computed by this DFS.



(3 marks) Given an edge (a; b) in a graph and the corresponding d[a], d[b], f[a], and f[b] assigned to nodes a and b by some DFS of this graph, how do we know if this edge is a back edge with respect to this DFS? Justify your answer.



(3 marks) Prove that graph G has no cycles. To do so use your DFS of graph G and an appropriate theorem (which is given in the textbook and was shown in the course).



(4 marks) List the nodes of the graph G in the topological sort order given by the DFS of G in part (b) (when executing the Topological-Sort algorithm described in the textbook and covered in a tutorial).






Question 2. (20 marks) We have n elements f1; : : : ; ng, and we are given as input a 2-dimensional array

D of the pairwise distances between them: D[i; j] is the distances between i and j. The distance of any




element to itself is 0 (i.e. D[i; i] = 0), and, moreover, the distances are symmetric: D[i; j] = D[j; i] for




every i and j. We would like to partition the n elements into two disjoint sets S and S that are as far apart as possible.




; f g




More precisely, given a set S 1; : : : ; n , de ne the distance between S and its complement S =







f1; : : : ; ng n S as d(S; S) = mini2S;j2S D[i; j], i.e. the minimum distance between a point in S and a point






in S. In this question your goal is to design an e cient algorithm to nd a partition S and S such that the






distance d(S; S) between S and S is the largest among all the ways to partition the elements f1; : : : ; ng






into two sets. That is, your algorithm should nd a partition S and S such that the following holds:






d(S; S) = maxfd(R; R) : ; R f1; : : : ; ng; R = f1; : : : ; ng n Rg:

Note that a \brute force" algorithm to do so would be very expensive. One way to do it is as follows:




(1) enumerate every possible partition S and S of f1; : : : ; ng,

(2) for each partition S and S nd the smallest edge between S and S | this gives you d(S; S), and




(3) nd the partition S and S with the largest d(S; S).




Since there are (2n) partitions of f1; : : : ; ng, this algorithm works in exponential time. Your algorithm should be much more e cient than this.




a. (10 marks) Let G be the complete graph with vertices f1; : : : ng, with the weight of edge e = (i; j) given by w(e) = D[i; j]. Let T be a minimum spanning tree of G end let e = (i; j) be an edge of e. T e (the tree T with the edge e removed) has two connected components: let S be the vertices in one of them,








and S the vertices in the other. Prove that d(S; S) = w(e) = D[i; j].
b. (8 marks)


Use part (a) to derive an e cient algorithm to nd a partition S and S such that the




distance d(S; S) between S and S is the largest among all the ways to partition the elements f1; : : : ; ng into two sets, as described above. Describe your algorithm in clear and concise English, and prove that it is correct.




c. (2 marks) What is the worst-case time complexity of your algorithm? Justify your answer.







[The questions below will not be corrected/graded. They are given here as interesting problems that use material that you learned in class.]




Question 3. (0 marks) Let G = (V; E) be an undirected graph. G is bipartite if the set of nodes V can be partitioned into two subsets V0 and V1 (i.e., V0 [ V1 = V ), so that every edge in E connects a node in V0 and a node in V1. For example, the graph shown below is bipartite; this can be seen by taking V0 to be the nodes on the left and V1 to be the nodes on the right.







1







2 6




3 7







4 8

















Prove that if G is bipartite then it has no simple cycle of odd length. Hint: Give a proof by contradiction.



Prove that if G has no simple cycle of odd length (i.e., every simple cycle of G has even length) then G is bipartite. (Hint: Suppose every simple cycle of G has even length. Perform a BFS starting at any node s. Assume for now that G is connected, so that the BFS reaches all nodes; you can remove this assumption later on. Use the distance of each node from s to partition the set of nodes into two sets, and prove that no edge connects two nodes placed in the same set.)



Describe an algorithm that takes as input an undirected graph G = (V; E) in adjacency list form. If G is bipartite, then the algorithm returns a pair of sets of nodes (V0; V1) so that V0 [ V1 = V , and every edge in E connects a node in V0 and a node in V1; if G is not bipartite, then the algorithm returns the



string \not bipartite". Your algorithm should run in O(n + m) time, where n = jV j and m = jEj. Explain why your algorithm is correct and justify its running time. (Hint: Use parts (a) and (b).)

Question 4. (0 marks) In this question the goal is to nd all the \peaks" in a topographical map. The input map is given as a 2-dimensional array H of size n n, where H[i; j] is the height of the point (i; j). We say that a point (k; `) is adjacent to a point (i; j) if ji kj 1 and jj `j 1. We say that a point q can be reached from a point p by going down if it is possible to start from p and eventually reach q by moving from one point to an adjacent point of the same or smaller height. (Note: staying on the same height also counts as going \down" according to this de nition.)

The highest peak P1 on the map is de ned as follows: let p1 = (i; j) be the highest point on the map

(i.e. p1 = (i; j) is such that H[i; j] = maxfH[i; j] : 1 i; j ng); then P1 consists of p1 and all points that can be reached from p1 by only going down. The second highest peak P2 on the map is de ned as follows: let p2 be the highest point not contained in P1; P2 consists of p2 and all points not in P1 that can be reached from p2 by going down. In general, the i-th highest peak Pi is de ned as: pi is the highest point not in P1 [ : : : [ Pi 1, and Pi consists of pi and all points that are not in P1 [ : : : [ Pi 1, and can be reached from pi by going down.




Design an algorithm running in time O(n2 log n) which lists the sizes of the peaks in order from the highest peak to the lowest. More precisely your algorithm should output jP1 j; jP2j; : : : ; jPtj, where t is the total number of peaks. Describe your algorithm in clear and concise English, explain why it is correct, and prove that its complexity is O(n2 log n).