联系方式

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

您当前位置:首页 >> Python编程Python编程

日期:2022-11-30 02:48

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.


版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp