## Description

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.

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

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

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

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

e. (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 {1, . . . , n}, 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.

More precisely, given a set ∅ ⊂ S ⊂ {1, . . . , n}, define the distance between S and its complement S¯ =

{1, . . . , n} \ S as d(S, S¯) = mini∈S,j∈S¯ 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 efficient algorithm to find 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 {1, . . . , n}

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

d(S, S¯) = max{d(R, R¯) : ∅ ⊂ R ⊂ {1, . . . , n}, R¯ = {1, . . . , n} \ R}.

2

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 {1, . . . , n},

(2) for each partition S and S¯ find the smallest edge between S and S¯ — this gives you d(S, S¯), and

(3) find the partition S and S¯ with the largest d(S, S¯).

Since there are Θ(2n

) partitions of {1, . . . , n}, this algorithm works in exponential time. Your algorithm

should be much more efficient than this.

a. (10 marks) Let G be the complete graph with vertices {1, . . . n}, 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 efficient algorithm to find 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 {1, . . . , n}

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

3

4

5

6

7

8

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

contradiction.

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

c. 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 = |V | and m = |E|. Explain

why your algorithm is correct and justify its running time. (Hint: Use parts (a) and (b).)

3

Question 4. (0 marks) In this question the goal is to find 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 |i − k| ≤ 1 and |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 definition.)

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

(i.e. p1 = (i, j) is such that H[i, j] = max{H[i, j] : 1 ≤ i, j ≤ n}); 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 defined 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 defined 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(n

2

log n) which lists the sizes of the peaks in order from the highest

peak to the lowest. More precisely your algorithm should output |P1|, |P2|, . . . , |Pt

|, 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

2

log n).

4