Algorithms and Analysis HW

CS277 – Homework 2Total points: 80
1. (10 points) Consider two functions:
f (n) = 1 if n is even else 0
g(n) = f (n + 1)
Prove or disprove: (f (n) = O(g(n))) ∨ (g(n) = O(f (n)))
Hint: ∨ is the disjunction operator (or-statement). Consider how to prove or disprove a disjunction statement.
2. The following algorithm finds a longest length path in a directed acyclic graph (DAG):
1 Function LongestLengthDAGPath(G := (V, E)):
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// G is an unweighted DAG
for u ∈ V do
u.d := 0
u.π := NIL
T := Compute topologically sorted ordering of vertices in G
// Iterate over vertices in topological order
foreach u ∈ T do
foreach v ∈ Adj[u] do
if v.d ≤ u.d + 1 then
v.d := u.d + 1
v.π := u
Find u ∈ V with maximum u.d
p := []
x := u
while x ̸= NIL do
Prepend x to p
x := x.π
return p
(a) (10 points) Give a tight bound on the worst case runtime of this algorithm. Prove your
bound using summations.
You may assume: basic arithmetic, inequality checking, and array slicing operations run
in constant time; p is a linked list, so we can prepend to it in constant time; and Adj is
an adjacency list.
1
(b) (8 points) If we removed the step that topologically sorts the input graph and instead
iterated over the vertices in an arbitrary order, would this algorithm still be correct? If
yes, explain why. If no, find a counterexample.
3. An electric utilities company connects all houses in a neighborhood to a power facility using
cables. Each cable has parallel wiring allowing electricity to travel in both directions. Houses
can be directly connected to each other or to the facility. The current web of connections uses
the least amount of cable to ensure that each house is connected to the facility.
(a) (4 points) Explain how to represent this web of connections as a graph. Specify the vertices, edges, whether it’s unweighted or weighted (and if weighted, what are the weights),
and whether it’s directed or undirected.
(b) (10 points) A tree was cut down between two houses, allowing the utilities company to
potentially add a connection between them. The company doesn’t want to maintain
unnecessary connections as they present a hazard in storms.
Give pseudocode for a o(E lg V ) algorithm (where V is the number of vertices and E is
the number of edges) to find a new web of connections that uses the least amount of cable.
You may remove existing connections but you may not add any new connections beyond
the one currently proposed.
Your algorithm may not use a Fibonacci heap.
(c) (4 points) Give a tight bound on the worst case running time of your algorithm if there
are V vertices and E edges. Explain your bound.
(d) (6 points) Justify your algorithm’s correctness. You don’t need a formal proof, but you
should logically explain why your algorithm finds the web of connections that uses the
least amount of cable while connecting every house to the facility.
4. Consider an unweighted, directed graph G = (V, E) with k strongly connected components
(SCCs). Assume that |V | ≥ 1.
(a) (4 points) If we add one edge to G, what is the minimum amount that we can decrease
the number of SCCs by? Explain your answer.
(b) (4 points) If we add one edge to G, what is the maximum amount that we can decrease
the number of SCCs by? Explain your answer.
(c) (10 points) Give an efficient algorithm that takes as input a directed, unweighted graph.
It should return one new edge that, when added to the graph, would maximally decrease
the number of SCCs (if such an edge exists).
Hint: Your algorithm may call any algorithm given in the textbook, homework assignments, or readings.
Note: In order to be considered efficient, your algorithm must do better than the brute
force approach of simply checking every edge that could be added.
(d) (10 points) Consider the following algorithm:
Page 2
1 Function FindEdgesToAdd(G):
2
3
4
5
6
7
8
// G is a directed, unweighted graph
S := {}
while G is not strongly connected do
Find edge e that if added to G would maximally reduce the number of SCCs in G;
if there are multiple, pick one arbitrarily
Add e to G’s edges
S := S ∪ {e}
return S
Will this algorithm find the smallest set of edges needed to make G strongly connected,
assuming that line 5 correctly finds an edge that maximally decreases the current number
of SCCs? If yes, explain why. If no, give a counterexample.
Page 3