Homework Help is Here – Start Your Trial Now!
Engineering
Computer Engineering
1. (a) Implement the sweeping algorithm to decide inter- section in a set of segments following the pseudocode in Chapte: 33. Sort the segments using Heapsort (Section 6.4) and maintain the sweeping status using a self-adjusting BST (e.g., RB trees (Chapter 13)).

1. (a) Implement the sweeping algorithm to decide inter- section in a set of segments following the pseudocode in Chapte: 33. Sort the segments using Heapsort (Section 6.4) and maintain the sweeping status using a self-adjusting BST (e.g., RB trees (Chapter 13)).

Computer Networking: A Top-Down Approach (7th Edition)
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
See similar textbooks
icon
Related questions
Question

Questions are attached

that all coordinates are different, you can maintain the sweep-line status using the y coordinate of the segment endpoint as the key. Remember that to achieve correctness you must use crossproducts. In other words, you have to follow the sweeping pseudocode in the book. No points for code implementing other algorithms. (You can reuse Heapsort, Radix Sort, BST, and/or vEB tree code if you have it.) 2. Write a method that does the following for an input set of n segments where all endpoint coordinates are different integers. Find the range of x-coordinates and the range of y-coordinates. Let u = max{max-xmin, Ymax - Ymin}. If 2n< u < 10n decide intersection calling the method in Part 15 Else, decide intersection calling the method in Part 1a. 3. Write a program that does the following for an input value n. • Create a "smooth" set of n non-vertical segments where all end- point coordinates are different integers and 2n< u < 10n. Recall that the sweeping algorithm stops after finding the first intersec- tion. So, define the set so that only a few intersect at the end of the range to attain a good evaluation of worst-case running time. • Create a "sparse" set of n non-vertical segments based on the smooth set but changing only one segment so that u > 100n. Make sure this modified segment does not intersect any of the other segments to avoid impact on running time due to new inter- sections. • Call the method in Part 2 with each of these sets and display the running time of each in nanoseconds.
Transcribed Image Text:that all coordinates are different, you can maintain the sweep-line status using the y coordinate of the segment endpoint as the key. Remember that to achieve correctness you must use crossproducts. In other words, you have to follow the sweeping pseudocode in the book. No points for code implementing other algorithms. (You can reuse Heapsort, Radix Sort, BST, and/or vEB tree code if you have it.) 2. Write a method that does the following for an input set of n segments where all endpoint coordinates are different integers. Find the range of x-coordinates and the range of y-coordinates. Let u = max{max-xmin, Ymax - Ymin}. If 2n< u < 10n decide intersection calling the method in Part 15 Else, decide intersection calling the method in Part 1a. 3. Write a program that does the following for an input value n. • Create a "smooth" set of n non-vertical segments where all end- point coordinates are different integers and 2n< u < 10n. Recall that the sweeping algorithm stops after finding the first intersec- tion. So, define the set so that only a few intersect at the end of the range to attain a good evaluation of worst-case running time. • Create a "sparse" set of n non-vertical segments based on the smooth set but changing only one segment so that u > 100n. Make sure this modified segment does not intersect any of the other segments to avoid impact on running time due to new inter- sections. • Call the method in Part 2 with each of these sets and display the running time of each in nanoseconds.
The purpose of this assignment is to implement the described strategy and compare efficiency experimentally drawing conclusions from the results obtained. To simplify the task, we will assume that all endpoint coordi- nates are different and integer. Your task is the following. 1. (a) Implement the sweeping algorithm to decide inter- section in a set of segments following the pseudocode in Chapter 33. Sort the segments using Heapsort (Section 6.4) and maintain the sweeping status using a self-adjusting BST (e.g., RB trees (Chapter 13)). (b) eta Implement the sweeping algorithm to decide intersec- tion in a set of segments following the pseudocode in Chapter 33. Sort the segments using Radix Sort (Section 8.3) and maintain the sweeping status using a van Emde Boas tree (Chapter 20). Given
Transcribed Image Text:The purpose of this assignment is to implement the described strategy and compare efficiency experimentally drawing conclusions from the results obtained. To simplify the task, we will assume that all endpoint coordi- nates are different and integer. Your task is the following. 1. (a) Implement the sweeping algorithm to decide inter- section in a set of segments following the pseudocode in Chapter 33. Sort the segments using Heapsort (Section 6.4) and maintain the sweeping status using a self-adjusting BST (e.g., RB trees (Chapter 13)). (b) eta Implement the sweeping algorithm to decide intersec- tion in a set of segments following the pseudocode in Chapter 33. Sort the segments using Radix Sort (Section 8.3) and maintain the sweeping status using a van Emde Boas tree (Chapter 20). Given
Expert Solution
steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY
SEE MORE TEXTBOOKS