算法代写|Algo Test Homework 6

这是一个美国的算法限时测试代写

Problem 1 (A path that visits all vertices)

Design an algorithm that takes as input a directed acyclic graph and returns true if there is a directed
path that visits all vertices, and returns false otherwise.

Problem 2 [DPV] 4.13 (cities and highways)

You are given a set of cities, along with the pattern of highways between them, in the form of an
undirected graph G = (V; E). Each stretch of highway e 2 E connects two of the cities, and you
know its length in miles, ‘e. You want to get from city s to city t. There’s one problem: your car
can only hold enough gas to cover L miles. There are gas stations in each city, but not between
cities. Therefore, you can only take a route if every one of its edges has length ‘e ≤ L.

(a) Given the limitation on your car’s fuel tank capacity, show how to determine in linear time
whether there is a feasible route from s to t.

(b) You are now planning to buy a new car, and you want to know the minimum fuel tank
capacity that is needed to travel from s to t. Give an O((jV j + jEj)logjV j) algorithm to determine
this. (Note: to solve part (b) you may modify known algorithms { if you do so, be sure to explain
your modifications in detail and how those modifications impact the known run time, if at all.)


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论