CMPSC 465 Data Structures & Algorithms
Fall 2021 Antonio Blanca and David Koslicki HW 6
Due October 5, 10:00 pm
Instructions: You are encouraged to solve the problem sets on your own, or in groups of three to five
people, but you must write your solutions strictly by yourself. You must explicitly acknowledge in your
write-up all your collaborators, as well as any books, papers, web pages, etc. you got ideas from.
Formatting: Each part of each problem should begin on a new page. Each page should be clearly labeled
with the problem number and the problem part. The pages of your homework submissions must be in order.
When submitting in Gradescope, make sure that you assign pages to problems from the rubric. You risk
receiving no credit for it if you do not adhere to these guidelines.
Late homework will not be accepted. Please, do not ask for extensions since we will provide solutions
shortly after the due date. Remember that we will drop your lowest two scores.
Important: Brief but precise description of algorithms is required. Pseudocode is not required, but you
may provide it if you think it helps your exposition. Pseudocode alone will not receive any credits. Do not
forget to provide the running time analysis of all your algorithms.
This homework is due Tuesday, October 5, at 10:00 pm electronically. You need to submit it via Gradescope
(Class code 6PERPR). Please ask on Piazza about any details concerning Gradescope.
Extra credit. Five extra credits points will be added to your homework score this time if you use Latex to
typeset your solutions.
1. (20 pts.) Processing the Graph
(a) Prove or disprove the following statement: if {u,v} 2 E is an edge in an undirected graph G = (V,E),
and during depth-first search the post-visit numbers of u,v 2V satisfy post(u)< post(v), then v is an
ancestor of u in the DFS tree.
(b) You are given a tree T = (V,E) (in adjacency list format), along with a designated root node r 2 V .
Recall that u is said to be an ancestor of v in the rooted tree if the path from r to v in T passes through
u. You wish to preprocess the tree so that queries of the form “is u an ancestor of v?” can be answered
in constant O(1) time. The preprocessing itself should take linear time. How can this be done?
2. (20 pts.) One-way Streets
The police department in the city of Comtopia has made all streets one-way. The mayor contends that there
is still a way to drive legally from any intersection in the city to any other intersection, but the opposition is
not convinced. A computer program is needed to determine whether the mayor is right. However, the city
elections are coming up soon, and there is just enough time to run a linear-time algorithm.
(a) Formulate this problem graph-theoretically, and explain why it can indeed be solved in linear time (in
terms of the number of roads and intersections).
CMPSC 465, Fall 2021, HW 6 1
(b) Suppose it now turns out that the mayor’s original claim is false. She next claims something weaker: if
you start driving from town hall, navigating one-way streets, then no matter where you reach, there is
always a way to drive legally back to the town hall. Formulate this weaker property in a graph-theoretic
setting, and carefully show how it too can be checked in linear time.
3. (20 pts.)
Give an efficient algorithm which takes as input a directed graph G = (V,E), and determines whether or not
there is a vertex s 2V from which all other vertices are reachable.
4. (20 pts.) BFS on Directed Graph
Consider a directed graph G = (V,E). Depth first search allows us to label edges as tree, forward, back and
cross edges. We can make similar definitions for breadth first search on a directed graph:
1. A BFS tree edge is an edge that is present in the BFS tree.
2. A BFS forward edge leads from a node to a non-child descendant in the BFS tree.
3. A BFS back edge leads to an ancestor in the BFS tree.
4. All other edges are BFS cross edges.
(a) Explain why it is impossible to have BFS forward edges.
(b) Give an efficient algorithm that classifies all edges in G as BFS tree edges, back edges, or cross edges.
5. (20 pts.) 2SAT
In the 2SAT problem, you are given a set of clauses, where each clause is the disjunction (OR) of two literals
(a literal is a Boolean variable or the negation of a Boolean variable). You are looking for a way to assign a
value true or false to each of the variables so that all clauses are satisfied – that is, there is at least one true
literal in each clause. For example, here’s an instance of 2SAT with five clauses and four variables:
(x1 _ x̂2)^ (x̂1 _ x̂3)^ (x1 _ x2)^ (x̂3 _ x4)^ (x̂1 _ x4).
This instance has a satisfying assignment: set x1, x2, x3, and x4 to true, false, false, and true, respectively.
Given an instance f of 2SAT with n variables and m clauses, construct a directed graph Gf = (V,E) as
follows:
• Gf has 2n nodes, one for each variable and one for its negation.
• Gf has 2m edges: for each clause (a _b ) of f (where a and b are literals), Gf has an edge from the
negation of a to b , and one from the negation of b to a .
(a) Show that if Gf has a strongly connected component containing both x and its negation x̂ for some
variable x, then f has no satisfying assignment.
(b) Now show the converse of (a): namely, that if none of Gf ’s strongly connected components contain
both a literal and its negation, then the instance f must be satisfiable. (Hint: Assign values to the
variables as follows: repeatedly pick a sink strongly connected component of Gf . Assign value true
to all literals in the sink, assign false to their negations, and delete all of these. Show that this ends up
discovering a satisfying assignment.)
(c) Conclude that there is a linear-time algorithm for solving 2SAT.
CMPSC 465, Fall 2021, HW 6 2