Description
1. What is the running time of DFS if the graph (G = (V, E), where there are |V | nodes and |E| edges) is
given as an adjacency list and adjacency matrix? Justify your running time.
2. Draw the parenthesis structure of the DFS of bottom left figure (start from u, assume that DFS considers
vertices in alphabetical order) and see the example parenthesis structure as is shown in the bottom right.
3. Bipartiteness. Given a undirected graph G = (V, E), it is bipartite if there exist U and W such that
U ∪ W = V , U ∩ W = ∅, and every edge has one endpoint each in U and W.
(a) Prove: G is bipartite only if G has no odd cycle. (Hint: proof by contradiction)
(b) In fact, G is bipartite if and only if G has no odd cycle. Suppose this is given, consider the Algorithm
1 and briefly describe why it is correct.
(c) Analyze the time complexity (worst-case, big-O) of the algorithm, in terms of |V | and |E|. (Hint:
can we check that there is no edge inside any layer in O(|E|)? Why?)
Algorithm 1 Testing bipartiteness of graphs
Do BFS starting at any node u
Let L0, L1, L2, . . . , Lk be layers in the resulting breadth-first tree (L0 = {u}, Li
, i = 1, 2, . . . , k contains the
vertices at distance i from u)
if There is no edge inside any layer Li then
Declare G to be bipartite, and U = L0 ∪ L2 ∪ L4 ∪ . . . , W = L1 ∪ L3 ∪ L5 ∪ . . . are the bipartition
else
Declare G to be non-bipartite
end if
4. You’re helping a group of ethnographers analyze some oral history data they’ve collected by interviewing
members of a village to learn about the lives of people who’ve lived there over the past two hundred
years. From these interviews, they’ve learned about a set of n people (all of them now deceased), whom
we’ll denote P1, P2, . . . , Pn.
They’ve also collected facts about when these people lived relative to one
another. Each fact has one of the following two forms:
(a) For some i and j, person Pi died before person Pj was born; or
(b) for some i and j, the life spans of Pi and Pj overlapped at least partially.
Naturally, they’re not sure that all these facts are correct; memories are not so good, and a lot of this
was passed down by word of mouth. So what they’d like you to determine is whether the data they’ve
collected is at least internally consistent, in the sense that there could have existed a set of people for
which all the facts they’ve learned simultaneously hold.
The original problem asks you to give an efficient algorithm to either produce proposed dates of birth
and death for each of the n people so that all the facts hold true, or report (correctly) that no such
dates can exist — that is, the facts collected by the ethnographers are not internally consistent. Since
topological sort will be taught next week, now let’s do make it simple. You only need to give an
efficient algorithm to determine whether the data is internally consistent.
Hints: Let’s say there are totally m recorded facts, and your algorithm should run in O(m+n). It should
1
be useful to turn the data into a graph. If each node represents an event (birth or death of someone),
what is the total number of nodes? How to define the edges, directed or undirected? What makes the
data inconsistent? What is the key structure to check in the graph?
