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.

1. (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.

1. (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.

1. (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.

1. (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).

1. (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 =

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 (2ⁿ) 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,

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 V₀ and V₁ (i.e., V₀ [ V₁ = V ), so that every edge in E connects a node in V₀ and a node in V₁. For example, the graph shown below is bipartite; this can be seen by taking V₀ to be the nodes on the left and V₁ to be the nodes on the right.

1

2 6

3 ₇

4 8

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

1. 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.)

1. 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 (V₀; V₁) so that V₀ [ V₁ = V , and every edge in E connects a node in V₀ and a node in V₁; 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 P₁ on the map is de ned as follows: let p₁ = (i; j) be the highest point on the map

(i.e. p₁ = (i; j) is such that H[i; j] = maxfH[i; j] : 1 i; j ng); then P₁ consists of p₁ and all points that can be reached from p₁ by only going down. The second highest peak P₂ on the map is de ned as follows: let p₂ be the highest point not contained in P₁; P₂ consists of p₂ and all points not in P₁ that can be reached from p₂ by going down. In general, the i-th highest peak P_i is de ned as: p_i is the highest point not in P₁ [ : : : [ P_{i 1}, and P_i consists of p_i and all points that are not in P₁ [ : : : [ P_{i 1}, and can be reached from p_i by going down.

Design an algorithm running in time O(n² log n) which lists the sizes of the peaks in order from the highest peak to the lowest. More precisely your algorithm should output jP₁ j; jP₂j; : : : ; jP_tj, 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(n² log n).