Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
Given a collection of n shapes on the plane, a valid traversal from shape A to shape B is a sequence of shapes starting at A and ending at B such that every two consecutive shapes overlap. The cost of a traversal is the sum of the areas of the individual shapes in the traversal. Suppose we only have two types of shapes: squares and circles. Your task is to design an algorithm to find the minimum cost traversal from A to B subject to the constraint that we are not allowed to use consecutive squares in the traversal. Remember to: a) Design an algorithm that solves the problem. b) Briefly argue the correctness of your algorithm. c) Analyse the running time of your algorithm. You can assume that there is routine that for a given shape computes its area in O(1) time and another routine that tests if two shapes overlap in O(1) time. The algorithm needs to run in O(n^2) time.

Given a collection of n shapes on the plane, a valid traversal from shape A to shape B is a sequence of shapes starting at A and ending at B such that every two consecutive shapes overlap. The cost of a traversal is the sum of the areas of the individual shapes in the traversal. Suppose we only have two types of shapes: squares and circles. Your task is to design an algorithm to find the minimum cost traversal from A to B subject to the constraint that we are not allowed to use consecutive squares in the traversal. Remember to: a) Design an algorithm that solves the problem. b) Briefly argue the correctness of your algorithm. c) Analyse the running time of your algorithm. You can assume that there is routine that for a given shape computes its area in O(1) time and another routine that tests if two shapes overlap in O(1) time. The algorithm needs to run in O(n^2) time.

icon
Related questions
Question

Given a collection of n shapes on the plane, a valid traversal from shape A to shape B is a sequence of shapes starting at A and ending at B such that every two consecutive shapes overlap. The cost of a traversal is the sum of the areas of the individual shapes in the traversal. Suppose we only have two types of shapes: squares and circles. Your task is to design an algorithm to find the minimum cost traversal from A to B subject to the constraint that we are not allowed to use consecutive squares in the traversal.

Remember to:
a) Design an algorithm that solves the problem.
b) Briefly argue the correctness of your algorithm.
c) Analyse the running time of your algorithm.

You can assume that there is routine that for a given shape computes its area in O(1) time and another routine that tests if two shapes overlap in O(1) time. The algorithm needs to run in O(n^2) time.

Expert Solution
steps

Step by step

Solved in 4 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Similar questions