COMP 465: Assignment 3
Winter 2022
Submission through Moodle is due by March 27th at 23:55
1. (20 pts) Short answer questions. For each question answer TRUE/FALSE. If you answer TRUE
provide a brief justification consisting of at most 3 short sentences (for majority of these questions,
one short sentence suffices). If you answer FALSE provide a small counter-example. Long and
complicated justifications as well as unnecessarily large and complicated counter-examples will lose
marks. Guesses without justification receive 0 marks.
Note: for some of the false statements below it might be hard to find a counter-example. You are
encouraged to give it your best shot, but if you notice that you are spending disproportionate amount
of time, you are encouraged to consult the web. If you find a counter-example on the web you must
understand it, internalize it, and write it up from memory. In addition, you must cite the resource
that you used (this won’t cost you any mark deductions), and you are still responsible for correctness
of the example (i.e., you can’t blame the source if it ultimately turns out incorrect – there is plenty
of wrong information on the web).
(a) An undirected graph with n vertices and at most n k edges has at least k connected components.
(b) Undirected graph G = (V,E) is called k-regular if degree of every vertex is exactly k. Girth of
the graph is the length of a shortest cycle in G. For example, the simple cycle with 5 vertices is
a 2-regular graph of girth 5. We claim that there is no 3-regular graph of girth 5 on 10 vertices.
(c) Suppose we run DFS on a directed graph G = (V,E) and we find a vertex with discovery time
1 and finishing time 2|V |. Then the entire graph must be strongly connected.
(d) We are given a weighted graph and a shortest path from s to t. If all edge weights in the graph
are multiplied by a positive constant, the given path remains shortest from s to t with respect
to the new weights.
(e) Suppose that we have computed an MST. If the weight of each edge in the graph is increased
by 1, the computed spanning tree remains minimum with respect to the new weights.
(f) Let P be a shortest path from s to t in a directed graph G with respect to edge weights w. If we
increase the weight of each edge by 1 then P is still the shortest path from s to t with respect
to the new edge weights.
(g) The shortest-paths tree computed by Dijkstra is necessarily an MST.
(h) In a weighted directed graph with positive weights, Dijkstra might call the update() procedure
(aka Relax() procedure, see CLRS 24.3) on the same edge more than once.
(i) Maximum flow in a network with integral capacities is necessarily integral.
(j) Ford-Fulkerson method runs in polynomial time assuming that capacities are positive integers.
2. (20 pts) Dr. Luzin wants to throw a party and is deciding whom to invite. He has n mathematicians
to choose from, and for each mathematician i, he has Friends[i], which is a linked list of i’s friends
among the n mathematicians. Dr. Luzin wants to pick as many people as possible subject to the
constraint that each invited mathematician has at least 10 of their friends at the party. Give an
efficient greedy algorithm that takes as input the list of n mathematicians and the lists of their
friends, and outputs the largest possible set of party invitees. Assume that friendship is symmetric.
(a) (3 pts) State this problem as a graph problem: what is the input graph G = (V,E) That is,
what are the vertices What are the edges What is the set of invitees in graph-theoretic terms
(is it a subset of edges or vertices and with what properties)
(b) (5 pts) Describe your greedy algorithm in plain English. In what sense is your algorithm greedy
(c) (5 pts) Give a formal proof of correctness for your algorithm.
(d) (5 pts) Describe your algorithm in pseudocode.
(e) (2 pt) State and justify the running time of your algorithm.
3. (20 pts) Given a weighted undirected graph G = (V,E) with weight function w : E → R and an
edge e ∈ E, the goal is to compute a minimum spanning tree subject to it containing e. Design an
efficient algorithm for this task.
(a) Describe your algorithm in plain English. You may use algorithms from class and textbook, but
make sure to state them precisely. If you are modifying an algorithm from class or textbook,
state details of your modification clearly.
(b) Describe your algorithm completely in pseudocode. If you are using an algorithm from class as
a subroutine, provide pseudocode for it as well. More space is provided on the next page.
(c) Briefly argue that the algorithm is correct.
(d) Justify the runtime of your algorithm. If you are using any abstract data types, state assump-
tions on their implementation necessary to achieve the stated runtime.
4. (20 pts) Design an efficient algorithm for the following problem:
Input: Undirected graph G = (V,E) in adjacency lists representation with unit edge costs. Vertices
s, t ∈ V .
Output: The number of distinct shortest paths from s to t.
(a) Briefly describe your algorithm in plain English.
(b) Describe your algorithm in pseudocode.
(c) Formally prove correctness of your algorithm.
(d) State and justify the running time of your algorithm.
5. (20 pts) Let G = (V,E) be a simple undirected graph. Recall that a subgraph H = (W,F ) of G is
called spanning if V = W and F E. Recall that a graph is called bipartite if its set of vertices can
be partitioned into two blocks such that all edges have exactly one endpoint in each block.
Given G = (V,E) with n = |V | vertices and m = |E| edges, we wish to find a spanning bipartite
subgraph with at least m/2 edges. Consider the following algorithm:
Initially, color vertices of V with two colors, red and blue, arbitrarily. Call a vertex v bad if v has
more neighbors of its own color than of the opposite color. Call an edge {u, v} monochromatic
if u and v have the same color; otherwise, call {u, v} a bichromatic edge. The algorithm can be
summarized as: while there exists a bad vertex, pick an arbitrary bad vertex and swap its color end
while.
Answer the following:
(a) Count the spanning subgraphs of G. Your answer should be a simple formula in terms of basic
parameters of G. Provide a brief justification (at most 1 sentence).
(b) Write down pseudocode for the above algorithm. Show low level implementation details. For
example, what data structure do use to maintain coloring How do you decide if a vertex is
bad or good
(c) Let A be a set of bichromatic edges in G at any point during the algorithm. Prove that (V,A)
is a spanning bipartite subgraph of G.
(d) Prove: if there are no bad vertices then there are at least m/2 bichromatic edges.
(e) Prove that the following statement is false: “The number of bad vertices decreases in each
iteration of the while loop.” Give an example where in a single iteration of the while loop the
number of bad vertices increases by 10.
(f) Prove that the algorithm terminates in at most m rounds.
(g) Combine the previous parts to prove correctness of the algorithm.
(h) State the running time of the algorithm and briefly justify it.
