CompSci 330 Design and Analysis of Algorithms

Assignment 2, Fall 2024 Duke University

TODO: Add your name(s) here

Due Date: Monday, September 16, 2024

How to Do Homework. We recommend the following three step process for homework to help
you learn and prepare for exams.
1. Give yourself 15-20 minutes per problem to try to solve on your own, without help or external
materials, as if you were taking an exam. Try to brainstorm and sketch the algorithm for
applied problems. Don’t try to type anything yet.
2. After a break, review your answers. Lookup resources or get help (from peers, office hours,
Ed discussion, etc.) about problems you weren’t sure about.
3. Rework the problems, fill in the details, and typeset your final solutions.

Typesetting and Submission. Your solutions should be typed and submitted as a single pdf on
Gradescope. Handwritten solutions or pdf files that cannot be opened will not be graded. LATEX1
is preferred but not required. You must mark the locations of your solutions to individual problems
on Gradescope as explained in the documentation. Any applied problems will request that you
submit code separately on Gradescope to be autograded.

Writing Expectations. If you are asked to provide an algorithm, you should clearly and unam-
biguously define every step of the procedure as a combination of precise sentences in plain English
or pseudocode. If you are asked to explain your algorithm, its runtime complexity, or argue for
its correctness, your written answers should be clear, concise, and should show your work. Do not
skip details but do not write paragraphs where a sentence suffices.

Collaboration and Internet. If you wish, you can work with a single partner (that is, in groups
of 2), in which case you should submit a single solution as a group on Gradescope. You can use
the internet, but looking up solutions or using LLMs is unlikely to help you prepare for exams. See
the homework webpage for more details.

Grading. Theory problems will be graded by TAs on an S/I/U scale. Applied problems typically
have a separate autograder where you can see your score. See the course policy webpage for details
about homework grading.

1
If you are new to LATEX, you can download it for free at latex-project.org or you can use the popular and free (for
a personal account) cloud-editor overleaf.com. We also recommend overleaf.com/learn for tutorials and reference.

1
Problem 1 (DAG Reachability). You are given a directed acyclic graph G = (V, E) with n
vertices and m edges, in which each node u ∈ V has an associated price pu which is a positive
integer. Define the array cost as follows: For each u ∈ V ,

cost[u] = price of the cheapest node reachable from u (including u itself).

For instance, in the graph below (with prices shown for each vertex), the cost values of the nodes
A, B, C, D, E, F are 2, 1, 4, 1, 4, 5, respectively.

2 6 4
A C E

B D F
3 1 5

Describe an algorithm that completes the entire cost array (i.e., for all vertices) in O(m + n) time.
Briefly explain the correctness of the algorithm and analyze its runtime complexity.

2
Problem 2 (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,
consider the following instance of 2SAT:

(x1 ∨ x2 ) ∧ (x1 ∨ x3 ) ∧ (x1 ∨ x2 ) ∨ (x3 ∨ x4 ) ∧ (x1 ∧ x4 ).

This instance has a satisfying assignment: set x1 , x2 , x3 , and x4 to True, False, False, and True,
respectively. For practice (do not submit), find another satisfying assignment for this instance, then
come up with another instance with four variables for which there is no satisfying assignment.
For this problem you will describe an efficient algorithm to solve 2SAT efficiently by reducing it
to the problem of finding the strongly connected components (SCCs) of a directed graph. Given
an instance I of 2SAT with n variables and m clauses, construct a directed graph GI = (V, E) as
follows.
• GI has 2n nodes, one for each variable and its negation.
• GI has 2m edges: for each clause (α ∨ β), (where α, β are literals), GI has an edge from
the negation of α to β, and one from the negation of β to α. For example, if the clause is
(x1 ∨ x2 ), then there is an edge from x1 = x1 to x2 and an edge from x2 to x1 .
Note that the clause (α ∨ β) is logically equivalent to the implications α ⇒ β and β ⇒ α. In this
sense, GI records all of the clauses in I by representing their equivalent implications as edges in
GI . For practice, consider drawing GI for the example instance above.
(a) Show that if GI has a SCC containing both x and x for some variable x, then I has no
satisfying assignment.
(b) Next show the converse of (a): namely, that if none of GI ’s SCCs contain both a literal and
its negation, then the instance I must be satisfiable. [Hint: Assign values to the variables
as follows: repeatedly pick a sink SCC (i.e., an SCC without edges leaving the SCC). Assign
value True to all literals in the sink, assign False to their negations, then delete these (the
literals and their negations) from GI . Show this results in a satisfying assignment.]
(c) Conclude that there is a O(m + n)-time algorithm for 2SAT.

3
Problem 3 (Transit Connections). The NotUnited airline company operates in locations num-
bered 1, 2, . . . , n and is based in location 1. NotUnited offers m connections between these locations.
These connections are specified by a list of tuples where (i, j) means that there is a connection from
location i to j. Connections are one way.
NotUnited wishes to add connections so that it is possible to reach all n − 1 additional operating
locations via a sequence of connections (possibly only one) starting from their base at location 1.
Describe an O(n + m) runtime algorithm to compute the minimum number of connections that the
company would need to add. If no new connections are necessary, return zero. Briefly explain the
correctness of the algorithm and analyze its runtime complexity.

4
Problem 4 (Applied). Bipartite graphs are a special class of undirected graphs of the form
G = (V, E) that have a 2-coloring, which is an assignment of either red or blue to each vertex
such that every edge has one red endpoint and one blue endpoint. Some problems can be solved
faster on bipartite graphs than general graphs. Thus, it is important to be able to determine when
a given graph is bipartite so that we can safely run algorithms tailored for bipartite graphs when
appropriate.
For this problem, you are given an undirected graph G = (V, E) whose vertices are valued 0 to
n − 1, where n = |V |. G may or may not be connected. We call a 2-coloring of a bipartite graph
as least-red if it colors the fewest possible vertices as red (and the rest blue). Your task is to
determine whether G is bipartite, and if so, return a least-red 2-coloring represented by a Boolean
array R[1..n], where R[i] is True if vertex i is red and False if vertex i is blue, for each i from 0 to
n − 1.

0 1 2 3 4 5

6 7 8 9 10

In the example bipartite graph above, one of two distinct least-red 2-colorings are shown: vertices
6, 7, 8, 9, 10 are red and vertices 0, 1, 2, 3, 4, 5 are blue.
You will need to design and implement an algorithm that, given G = (V, E), either reports no 2-
coloring exists (represented by returning None in Python or null in Java), or a least-red 2-coloring
in O(n + m) time (where n = |V | and m = |E|). G may have multiple least-red 2-colorings (how?),
in which case you may output any one of them.
Language-specific details follow. You can use whichever of Python or Java you prefer. You will
receive automatic feedback when submitting, and you can resubmit as many times as you like up
to the deadline.
• Python. You should submit a file called least red.py to the Gradescope item “Homework
2 - Applied (Python).” The file should define (at least) a top-level function least red that
takes in two inputs, an int n, which defines the number of vertices, and a list of tuples (i:int,
j:int) edges where (i,j) refers to an undirected edge from node i to node j, that returns
None if no 2-coloring of the graph exists, and otherwise returns a list of n bools that represents
a least-red coloring, where each i-th value is True if and only if vertex i is red in the coloring.
The function header is as follows
– def least red(n:int, edges:list[(int, int)]): -> list[bool]
• Java. You should submit a file called LeastRed.java to the Gradescope item “Homework 2
- Applied (Java)” The file should define (at least) a top level function leastRed that takes in
one 2D int array, edges, and either returns null if no 2-coloring exists, or otherwise returns
an ArrayList<Boolean> that represents a least-red coloring, where each i-th value is True if
and only if vertex i is red in the coloring. The header for the method is as follows

5
 – public ArrayList<Boolean> leastRed(int n, int[][] edges);
edges is a m × 2 2D int array, where edges[i] is the undirected edge from edges[i][0] to
edges[i][1].