COMP 3711 – Design and Analysis of Algorithms
2022 Fall Semester – Written Assignment 4
Distributed: November 14, 2022
Due: November 30, 2022, 23:59
Your solution should contain
(i) your name, (ii) your student ID #, and (iii) your email address
at the top of its first page.
Some Notes:
Please write clearly and briefly. In particular, your solutions should be written or printed on clean
white paper with no watermarks, i.e., student society paper is not allowed.
Please also follow the guidelines on doing your own work and avoiding plagiarism as described on
the class home page. You must acknowledge individuals who assisted you, or sources where you found
solutions. Failure to do so will be considered plagiarism.
The term Documented Pseudocode means that your pseudocode must contain documentation, i.e.,
comments, inside the pseudocode, briefly explaining what each part does.
Many questions ask you to explain things, e.g., what an algorithm is doing, why it is correct, etc. To
receive full points, the explanation must also be understandable as well as correct.
Please make a copy of your assignment before submitting it. If we can’t find your submission, we will
ask you to resubmit the copy.
Submit a SOFTCOPY of your assignment to Canvas by the deadline. If your submission is a scan of
a handwritten solution, make sure that it is of high enough resolution to be easily read. At least 300dpi
and possibly denser.
Question 1 (20%): Cycle Detection
Let G(V,E) be a undirected graph, not necessarily connected. The degree of a vertex is equal to
the number of neighbors of that vertex in G. Assume that there are no nodes with degree 0.
a) (10%) Prove that if every vertex of G has an even degree, every vertex of G appears in
some cycle.
Hint: Explore the graph to remove one cycle at a time as well as the vertices on that
cycle. Argue that this can be repeated until no vertex is left.
b) (10%) Based on part (a), design an O(V+E) algorithm that returns TRUE if G contains
a cycle, and FALSE otherwise. In case of TRUE, your algorithm should output all
nodes that are part of some cycle (you are not required to output the individual cycles,
if there are multiple). Your algorithm should be not be recursive, and should not be
based on DFS.
Hint: A vertex of degree 1 cannot appear on any cycle and hence can be deleted.
Question 2 (20%): All Pairs Shortest Paths
Assume an undirected connected graph G(V,E), where all edges have the same weight w where w > 0.
Give an O(VE) algorithm for computing the shortest distance between all pairs of nodes.
Question 3 (30%): Currency Exchange
Let x1,..xn a set of n currencies. You are given a nxn matrix M that contains the exchange rates
for pairs of currencies (xi,xj), e.g., (HK$,US$) = 0.13 means that we can exchange HK$ 1 for
US$ 0.13. Similarly, (US$, HK$) = 7.85 means that we can exchange US$ 1 for HK$ 7.85.
The exchange rates for some pairs of currencies may be missing. By taking advantage of
exchange rates, a trader can earn profit. For instance, in addition to the above assume the
following exchange rates: (US$, EUR) = 1 and (EUR, $HK) = 7.9. One can start with HK$
1,000, exchange to US$ 130, then exchange to EUR 130, and finally exchange back to HK$
1,027 (130x7.9), for a profit of HK$ 27. Design an algorithm, which given M, it detects if there
are any profit opportunities. The output should be TRUE or FALSE. TRUE implies that there
is an opportunity, and FALSE that there is not. In case of TRUE, you do not have to output any
of the profit opportunities.
Hint: Convert the problem to a problem of detecting whether there is a negative cycle in a
directed graph.
Question 4 (30%): Maximum Flow
Let A be a n × m matrix of non-negative real numbers such that the sum of the entries in every row and
in every column is an integer. Prove that there is an n × m matrix B of non-negative integers with the
same sums as in A, in every row and every column.