CS180 Homework 2

CS180 Homework 2

1. An Eulerian cycle of a graph G is a path which starts and ends on the same vertex and traverses
every edge in the graph exactly once.
(a) We have seen that an undirected connected graph G = (V, E) such that all the vertices have
even degrees has an Eulerian cycle. Give an O(|E|) time algorithm to find it.
(b) A directed graph is strongly connected if every vertex is reachable from every other vertex.
Assume that for every vertex in a directed graph G = (V, E) its in-degree equals its out
degree, and G is strongly connected. Prove that G has an Eulerian cycle and give an O(E)
time algorithm to find it.
2. A celebrity among n persons is someone who is known by everyone but does not know anyone.
Equivalently, given a directed graph G = (V, E) with n vertices, a directed edge from vi
to vj
represents person i knows person j, a celebrity vertex is the vertex with no outgoing edge and
n − 1 incoming edges. In the class, we have seen an O(n) recursive algorithm that finds whether
celebrity exists or not and it does returns it. The graph G is represented by an n × n adjacency
matrix M, which is a (0, 1)-matrix such that M[i, j] = 1 if and only if there is a directed edge from
vi
to vj
. Give an iterative O(n) time algorithm to find the celebrity vertex in G, or output none if
no one is.
3. Given a undirected tree T, the diameter of a tree is the number of edges in the longest path in
the tree. Design an algorithm that find the diameter of the tree in O(n) time where n is number
of the nodes in the tree.
4. Let Kn = (V, E) be a complete undirected graph with n vertices (namely, every two vertices are
connected), and let n be an even number. A spanning tree of G is a connected subgraph of G that
contains all vertices in G and no cycles. Design a recursive algorithm that given the graph Kn
,
partitions the set of edges E into n/2 distinct subsets E1
, E2
, ..., En/2
, such that for every subset Ei
,
the subgraph Gi = (V, Ei
) is a spanning tree of Kn
.
(Hint: Solve the problem recursively by removing two nodes and their edges in Kn
. From the
output of recursive call, you get (n − 2)/2 spanning trees for Kn−2
. Extend those trees to be
spanning trees for Kn and then construct a new spanning tree to complete the job. PS: A collection
of sets S1
, . . . , Sk
is a partition of S, if each Si
is a subset of S, no two subsets have a non-empty
intersection, and the union of all the subsets is S.)
Æ Express your algorithm in a well-structured manner. Pseudo code in the textbook has good examples to follow. Avoid using a long continuous piece of text to describe your algorithm. Start
each problem on a NEW page. Unless specified, you should justify the time complexity of your
algorithm and why it works. For grading, we will take into account both the correctness and
the clarity. Your answers are supposed to be in a simple and understandable manner and sloppy
answers are expected to receiver fewer points.
Æ Homework assignments are due on Gradescope. Email attachments or paper submissions are NOT
acceptable.
1
Æ Raw photo is NOT acceptable. Upload your homework as a PDF scan by using a scanner or mobile
scanner app. Match each problem with your answer on Gradescope. Use dark pen or pencil and
your handwriting should be clear and legible.
Æ We recommend using LATEX, LYX or other word processing software for writing the homework. This
is NOT a requirement but it helps us to grade and give feedback.
2