首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- 代写comp9012、辅导python程序语言 2023-01-23
- Comp9414: Artificial Intelligence Assi... 2023-01-05
- Comp9444 Assignment 1 Neural Networks ... 2023-01-05
- Final Assignment - Apply All Your Skil... 2023-01-05
- Data7202 Statistical Methods For Data ... 2023-01-04
- Comp307/Aiml420 Assignment 4: Planning... 2023-01-04
- Comp3170 Assignment 3 Moonlit Forest 2023-01-04
- Cs 179: Introduction To Graphical Mode... 2023-01-04
- Computer Vision Assignment 3: Deep L... 2023-01-03
- C++ Implementation Of Graph Algorithms 2023-01-03
- Computer Vision Assignment 3: Deep Le... 2023-01-03
- Cs 179: Introduction To Graphical Mode... 2023-01-03
- Comp Sci 3306, Comp Sci 7306 Assignmen... 2023-01-03
- Comp Sci 3306, Comp Sci 7306 Assignmen... 2023-01-03
- C++编程设计辅导、辅导program程序 2022-12-22
- Mthm002代做、辅导java/Python编程 2022-12-22
- Buss6002代做、辅导python编程 2022-12-22
- Cmpen 431代写、辅导c/C++语言编程 2022-12-20
- 辅导program、辅导java/C++编程 2022-12-19
- 代写engf0004、Matlab编程设计辅导 2022-12-19