Reference no: EM13872458
The problem of computing a set of equivalent elements arises in many applications. Recall that an equivalence relation defined on a set of elements is a relation that is reflexive, symmetric and transitive. One application of an equivalence relation appears when designing VLSI chips. When manufacturing chips material is laided down in layers. If material is placed in two overlapping regions of the chip within the same layer, the two regions have the same electrical properties.
In this problem, you will be given a data file containing a set of points defining a collection of rectangular regions. Each region will be consist of four nonnegative integer values that represent the lower-left and upper-right corners of a rectangle. Your task is to determine which rectangles overlap and then compute an equivalence relation that assigns the rectangles to equivalence classes. For simplicity we will assume that all the rectangle resides in the same layer of the chip. The following example illustrates the problem.
Contents of the data file:
|
0
|
5
|
3
|
6
|
<=
|
region
|
0
|
|
2
|
7
|
8
|
9
|
<=
|
region
|
1
|
|
2
|
2
|
4
|
8
|
<=
|
region
|
2
|
|
1
|
0
|
7
|
1
|
|
.
|
|
|
5
|
0
|
6
|
3
|
|
.
|
|
|
7
|
5
|
10
|
8
|
|
.
|
|
|
8
|
2
|
18
|
3
|
|
|
|
|
12
|
0
|
14
|
6
|
|
|
|
|
16
|
1
|
17
|
6
|
|
|
|
|
13
|
4
|
17
|
5
|
|
|
|
|
12
|
8
|
14
|
10
|
|
|
|
|
11
|
8
|
17
|
9
|
|
|
|
|
15
|
7
|
18
|
10
|
<=
|
region
|
12
|
Assume the regions are numbered in the order they appear in the data file from 0 to N-1. Use the union-find algorithm and the general tree class defined in section 6.2 of your textbook to locate the equivalence classes. Your program should read the data file, compute the equivalence classes, and display a table on the screen of the form:
Eqivalence Class Regions
1 { 0, 1, 2, 5 }
2 { 3, 4 }
3 { 10, 11, 12 }
4 { 6, 7, 9, 8 }
The equivalence classes can be numbered in any order and the regions within the sets can be displayed in any order. At minimum, your solution should have classes for a data point, rectangle, and the union-find operation. You may create any additional classes that you need to implement your solution. On the assigned due date, submit all source files (.cpp and .h) needed to compile your solution. We will test your solution be executing the command: project2 < datafile so make sure to name your executable file project2 and read data from cin.
Attachment:- cp.zip
|
Curvature radius r of the point trajectory
: Find how the curvature radius R of the point's trajectory and the total acceleration w depend on the distance covered s.
|
|
Stratsim simulation marketing strategy
: Paper about 6 pages about StratSim Marketing Simulation Game.( 1 pages for each decision period)
|
|
General fund statement of revenues, expenditures, and change
: Prepare the county, General Fund statement of revenues, expenditures, and changes in fund balance for the year ended December 31, 2012. Consider the proceeds from the sale and leaseback of an office building as a special item.
|
|
Ball straight up into the air
: A person sitting in an enclosed train car, moving at constant velocity, throws a ball straight up into the air in her reference frame.
|
|
Problem of computing a set of equivalent elements
: The problem of computing a set of equivalent elements arises in many applications. Recall that an equivalence relation defined on a set of elements is a relation that is reflexive, symmetric and transitive.
|
|
Compute the cost of the inventory on december
: Compute the cost of the inventory on December 31, 2014, assuming that the ending inventory at retail is $286,200. Compute the cost of the inventory on December 31, 2014, assuming that the ending inventory at retail is $351,000.
|
|
What bid price should you set for the contract
: Your company has been approached to bid on a contract to sell 3,600 voice recognition (VR) computer keyboards a year for four years. Due to technological improvements, beyond that time they will be outdated and no sales will be possible. The tax rate..
|
|
Integrate the article with marketing theories and concepts
: integrate the article with marketing theories and concepts in your own words , you can write about how pepsi can use the marketing mix to help the product. three-page review
|
|
Normal force from the plane
: A mass m slides down a frictionless plane that is inclined at angle θ. Show, using the method in Section 5.3, that the normal force from the plane is the familiar mg cos θ.
|