Design a brute force algorithm to solve the shortest path

Assignment Help Computer Engineering

Reference no: EM133359993

Question: Let S be a set of points in a 2-dimensional plane. The convex hull of set S is the smallest convex set containing S. It is assumed that not all the points in S are on a straight line. The points in the convex hull can be viewed as fence posts that support a fence surrounding all the points in S. Let s1 and s2 be two points in the hull. A path from s1 to s2 is a sequence 1 of points in the hull. By viewing points in the hull as fence posts, we may consider a path as a sequence of posts holding a fence segment. The problem of finding shortest path around is to find the shortest path from s1 to s2 that cannot cross inside the fenced area, but it goes along the fence. From s1 to s2, there are two paths along the fence, going in the two directions. The problem is to find the shorter one.

1 Design a brute force algorithm to solve the shortest path around problem and analyze its efficiency.

2 Design a recursive divide-and-conquer algorithm of Θ(n log n) to solve the shortest path around problem, set up a recurrence to analyze the number of repetitions of the basic operation to compute the hull (for the best case), and determine the efficiency class. Use the Master Theorem to verify the efficiency class that you determine.

3 Implement the two algorithms and test them using data A2 Q2.txt. The file contains 30,000 points (pairs of x-y coordinates). Your programs will be graded by using this data file and two points s1 and s2 that are in the hull of the points in the file. Your programs are required to display the number of points on the path, the length of the path, and x-y coordinates of the points (in the order from s1 to s2 inclusive). C code

Reference no: EM133359993

Questions Cloud

What is the amount accrued for lighting and heating : What is the amount accrued for lighting and heating, and amount prepaid for insurance at the year ended 31 December 2016

Article-spirit in the discipline of christian spirituality : What is main relevance of the article "First Steps into the Discipline: On the 'spirit' in the Discipline of Christian Spirituality."

Calculate the net advantage to leasing : Calculate the net advantage to leasing (NAL) the restaurant equipment. It is assumed that the old equipment has no resale value whereas the new equipment would

Assertiveness cultural dimensions : United States related to the performance orientation and assertiveness cultural dimensions found in the result of the GLOBE Project?

Design a brute force algorithm to solve the shortest path : Design a brute force algorithm to solve the shortest path around problem and analyze its efficiency. Design a recursive divide-and-conquer algorithm

How does the cost of goods sold to total receipts : How does the cost of goods sold to total receipts ratio in that publication compare to the ratios on the 2015 IRS Schedule C

Describe and explain nyas journey everyday : Describe and explain Nyas journey everyday and How would you feel if you had such an essential responsibility like her

Evaluate an approach that makes use of divine command ethics : Articulate, explain, and evaluate in each case an approach that makes use of divine command ethics.

Write a function product to compute the product of arbitrary : Write a function product to compute the product of arbitrary two integers. Take care of the sign. product(2,~3) > ~6 Write a function delnthc to delete

User Account

All Pages