5. (a) In class we saw how to use an interval tree to store a set...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
5. (a) In class we saw how to use an interval tree to store a set of intervals. Our interval tree had a search operation allowing us to search for an interval overlapping a given interval. In this question we want to produce an algorithm that given an unordered list of n intervals, determines in O(n log n) worst case time, whether it contains a pair of intervals that overlap. Do not use an interval tree for this algorithm. (b) Justify why your algorithm is correct and runs in the required time. We now extrapolate our interval problem to a set of rectangles whose edges are parallel to the x and y axes. Suppose R and R2 are rectangles whose edges are parallel to the x and y axes. Define what it means for R and R2 to overlap in terms of their left and right a coordinates and top and bottom y coordinates. (c) Describe an algorithm that, given an unordered list of n rectangles whose edges are parallel to the x and y axes and which are specified by their left and right x coordinates and top and bottom y coordinates, decides, in O(n log n) worst case time, whether it contains a pair of rectangles that overlap. Justify why your algorithm is correct and runs in the required time. Hint: Make use of both your answer to (a) and the interval tree we learned in class. 5. (a) In class we saw how to use an interval tree to store a set of intervals. Our interval tree had a search operation allowing us to search for an interval overlapping a given interval. In this question we want to produce an algorithm that given an unordered list of n intervals, determines in O(n log n) worst case time, whether it contains a pair of intervals that overlap. Do not use an interval tree for this algorithm. (b) Justify why your algorithm is correct and runs in the required time. We now extrapolate our interval problem to a set of rectangles whose edges are parallel to the x and y axes. Suppose R and R2 are rectangles whose edges are parallel to the x and y axes. Define what it means for R and R2 to overlap in terms of their left and right a coordinates and top and bottom y coordinates. (c) Describe an algorithm that, given an unordered list of n rectangles whose edges are parallel to the x and y axes and which are specified by their left and right x coordinates and top and bottom y coordinates, decides, in O(n log n) worst case time, whether it contains a pair of rectangles that overlap. Justify why your algorithm is correct and runs in the required time. Hint: Make use of both your answer to (a) and the interval tree we learned in class.
Expert Answer:
Related Book For
Posted Date:
Students also viewed these programming questions
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...
-
Jarvis Company produces a product that has a selling price of $20.00 and a variable cost of $15.00 per unit. The company's fixed costs are $50,000. What is the break-even point measured in sales...
-
What is meant by user-centred design?
-
Two drinking glasses, 1 and 2, are filled with water to the same depth. Glass 1 has twice the diameter of glass 2. (a) Is the weight of the water in glass 1 greater than, less than, or equal to the...
-
Describe the architecture of an expert system, and describe the roles of the various people involved in it.
-
The Assembly Department of Crackle Surge Protectors began September with no work in process inventory. During the month, production that cost $ 64,434 (direct materials, $ 12,954, and conversion...
-
3. A stunt man tries to run backward on a treadmill. The stuntman's velocity is 8m/s to the right and the treadmill is moving at a velocity of 9 m/s to the left. a. What is the resultant velocity of...
-
A sealed vessel contains a mixture of 956 g of trichloromethane chcl3 also called chloroform and 230 .g of ethanol ch3ch2oh.At 30-degree Celcius assume that their vapor pressures are 36.0 kpa and...
-
When a socket is created, which of the following Internet addresses is used? a. The address of the computer to which you want to connect b. The address of your computer c. The address of your ISP
-
Write a program to determine how many actors there are in the data set in Worked Example 19.2. Note that many actors are in multiple movies. The challenge in this assignment is that each movie has a...
-
Modify the generic Pair class so that both values have the same type.
-
Implement an iterator for the BinarySearchTree class that visits the nodes in sorted order. In the constructor, keep pushing left nodes on a stack until you reach null. In each call to next, deliver...
-
How can you communicate with a web server without using sockets?
-
Provide the benefits and downfalls of using social media to disseminate information to the masses. What are 3 risks associated with a lax social media program?
-
Define a traverse in Surveying?
-
You have just been telephoned by the chief accountant of a listed company client, Randerston plc, to tell you that there has been a computer breakdown and that some parts of the data concerning...
-
You have been asked by your audit partner to be senior in charge of the audit of a small public limited company. Unbeknown to the partner, you hold 1000 of the 100 000 shares in the company. Do you...
-
In Table 3.3 we suggested pressures against independence in respect of small audit firms and small auditees. To what extent do you believe that the IFAC Code and FRC Ethical Standard have been...
Study smarter with the SolutionInn App