讲解CS701-801、c/c++编程调试、Python/c++，Java辅导、讲解course material
- 首页 >> 其他 CS701-801 - Spring 2019 - Assignment #2
Assigned: April 12th, 2019
Due: April 26th, 2019
No late submissions.
Collaboration policy: The goal of homework is to give you practice in
mastering the course material. Consequently, you are encouraged to collaborate
with others. In fact, students who form study groups generally do
better on exams than do students who work alone. However, the assignment
is individual. That is, you must write up each problem solution and/or code
any programming assignment without external assistance, even if you collaborate
with others for discussions. If you are unable to solve a problem, it is
your responsibility to get help from the instructor before the assignment is
due. You are asked to identify your collaborators. If you did not work
with anyone, you must write “Collaborators: none.” If you obtain a
solution through research (e.g., on the web), acknowledge your source, but
write up the solution in your own words. It is a violation of this policy
to submit a problem solution that you cannot orally explain
to the instructor. No other student may use your solutions; this includes
your writing, code, tests, documentation, etc. It is a violation of this policy
to permit anyone other than the instructor and yourself read-access to the
location where you keep your solutions.
1Submission Guidelines: You have to submit your work on Blackboard
by the due date. For each of the programming assignments you must use the
header template provided in Blackboard. Make sure that you identify yourself
in the header, and any collaborators. If none, write “none”. Your answers
to questions that do not require coding must be included in this header
as well. Your code must follow customary formatting standards, as posted
in Blackboard. Format will also be part of your grade. To complete your
submission, you have to upload to Blackboard the source file and nothing
else. The submission will not be accepted in any other format.
Style and Correctness: Keep in mind that your goal is to communicate.
Full credit will be given only to the correct solution which is described
clearly. Convoluted and obtuse descriptions might receive low marks, even
when they are correct. Also, aim for concise solutions, as it will save you
time spent on write-ups, and also help you conceptualize the key idea of the
problem.
2Assignment 2
Grading Rubric:
Program
characteristic Program feature Credit
possible Coding questions
Design
30% Algorithm 30%
Functionality
30%
Program runs
without errors 20%
Correct result given 10%
Input
15%
User friendly,
typos, spacing 10%
Values read in
correctly 5%
Output
15%
Output provided 10%
Proper spelling,
spacing, user friendly 5%
Format
10%
Documentation: name,
collaborators, header, etc. 5%
Clarity: comments,
indentation, etc. 5%
TOTAL 100%
1a(25) 1b(25) 2(10) 3(10) 4(10) 5(20) TOTAL(100)
3Assignment:
The intended usage of a data structure is crucial to choose the most ef-
ficient one. Hence, good general-purpose data structures minimize assumptions
about input characteristics. However, many times data queries can be
sped up significantly designing application-specific data structures if input
information is available.
Take for instance the segment intersection decision problem. That is,
given a set of segments, decide whether there exists in the set at least one pair
of segments that intersect. As we learned, we can solve this problem using
a sweeping technique that is common to computational-geometry algorithms
(Chapter 33.2). This algorithm runs in O(n log n) time using Heapsort to
sort the segments and a self-adjusting BST to maintain the sweeping line
status.
The implementation of the sweeping mentioned above is quite efficient
taking into account that finding all intersections is known to be in ?(n
2
).
However, a natural question is whether it is possible to decide intersection
in o(n log n) using input information. For instance, the sweeping algorithm
studied assumes that all segments are available from start (off-line). Thus,
information such as maximum or minimum coordinates of segment end points
is easily computable in O(n). Then, one could design an early-stopping
algorithm that checks first if the range of coordinates has the same order of
magnitude as n, and if so decides intersection using the sweeping algorithm
with a o(n log n) implementation, or otherwise use the standard O(n log n)
implementation.
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 coordinates
are different and integer. Your task is the following.
1. (a) (25 points) Implement the sweeping algorithm to decide intersection
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) (25 points) Implement the sweeping algorithm to decide intersection
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
4that 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.)
Write a method that does the following for an input set (10 points) 2.
segments where all endpoint coordinates are different integers. n of
-coordinates. Let y -coordinates and the range of x Find the range of
decide intersection n 10 n < u < . If 2 } min y ? max , y min x ? max x{ = max u
calling the method in Part 1b. Else, decide intersection calling the
method in Part 1a.
Write a program that does the following for an input value (10 points) 3.
. n
non-vertical segments where all end- n Create a “smooth” set of ?
. Recall n 10 n < u < point coordinates are different integers and 2
that the sweeping algorithm stops after finding the first intersection.
So, define the set so that only a few intersect at the end
range to attain a good evaluation of worst-case running x of the
time.
non-vertical segments based on the n Create a “sparse” set of ?
. n 100 u > smooth set but changing only one segment so that
Make sure this modified segment does not intersect any of the
other segments to avoid impact on running time due to new intersections.
Call the method in Part 2 with each of these sets and display the ?
running time of each in nanoseconds.
Run your program and fill the table below (adjust the (10 points) 4.
as needed according to your platform to obtain at least 5 n values of
measurements).
= 10 n nanoseconds
2 = 10 n
3 = 10 n
4 = 10 n
5 = 10 n
6
Smooth set
Sparse set
55. (20 points) What is the best function of n and/or u fitting your
measurements? Notice that you are evaluating rate of growth, you are
not being asked which one is faster. Are the results consistent with
the query time of the data structures and algorithms used? Justify
explaining the running time of each.
6
Assigned: April 12th, 2019
Due: April 26th, 2019
No late submissions.
Collaboration policy: The goal of homework is to give you practice in
mastering the course material. Consequently, you are encouraged to collaborate
with others. In fact, students who form study groups generally do
better on exams than do students who work alone. However, the assignment
is individual. That is, you must write up each problem solution and/or code
any programming assignment without external assistance, even if you collaborate
with others for discussions. If you are unable to solve a problem, it is
your responsibility to get help from the instructor before the assignment is
due. You are asked to identify your collaborators. If you did not work
with anyone, you must write “Collaborators: none.” If you obtain a
solution through research (e.g., on the web), acknowledge your source, but
write up the solution in your own words. It is a violation of this policy
to submit a problem solution that you cannot orally explain
to the instructor. No other student may use your solutions; this includes
your writing, code, tests, documentation, etc. It is a violation of this policy
to permit anyone other than the instructor and yourself read-access to the
location where you keep your solutions.
1Submission Guidelines: You have to submit your work on Blackboard
by the due date. For each of the programming assignments you must use the
header template provided in Blackboard. Make sure that you identify yourself
in the header, and any collaborators. If none, write “none”. Your answers
to questions that do not require coding must be included in this header
as well. Your code must follow customary formatting standards, as posted
in Blackboard. Format will also be part of your grade. To complete your
submission, you have to upload to Blackboard the source file and nothing
else. The submission will not be accepted in any other format.
Style and Correctness: Keep in mind that your goal is to communicate.
Full credit will be given only to the correct solution which is described
clearly. Convoluted and obtuse descriptions might receive low marks, even
when they are correct. Also, aim for concise solutions, as it will save you
time spent on write-ups, and also help you conceptualize the key idea of the
problem.
2Assignment 2
Grading Rubric:
Program
characteristic Program feature Credit
possible Coding questions
Design
30% Algorithm 30%
Functionality
30%
Program runs
without errors 20%
Correct result given 10%
Input
15%
User friendly,
typos, spacing 10%
Values read in
correctly 5%
Output
15%
Output provided 10%
Proper spelling,
spacing, user friendly 5%
Format
10%
Documentation: name,
collaborators, header, etc. 5%
Clarity: comments,
indentation, etc. 5%
TOTAL 100%
1a(25) 1b(25) 2(10) 3(10) 4(10) 5(20) TOTAL(100)
3Assignment:
The intended usage of a data structure is crucial to choose the most ef-
ficient one. Hence, good general-purpose data structures minimize assumptions
about input characteristics. However, many times data queries can be
sped up significantly designing application-specific data structures if input
information is available.
Take for instance the segment intersection decision problem. That is,
given a set of segments, decide whether there exists in the set at least one pair
of segments that intersect. As we learned, we can solve this problem using
a sweeping technique that is common to computational-geometry algorithms
(Chapter 33.2). This algorithm runs in O(n log n) time using Heapsort to
sort the segments and a self-adjusting BST to maintain the sweeping line
status.
The implementation of the sweeping mentioned above is quite efficient
taking into account that finding all intersections is known to be in ?(n
2
).
However, a natural question is whether it is possible to decide intersection
in o(n log n) using input information. For instance, the sweeping algorithm
studied assumes that all segments are available from start (off-line). Thus,
information such as maximum or minimum coordinates of segment end points
is easily computable in O(n). Then, one could design an early-stopping
algorithm that checks first if the range of coordinates has the same order of
magnitude as n, and if so decides intersection using the sweeping algorithm
with a o(n log n) implementation, or otherwise use the standard O(n log n)
implementation.
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 coordinates
are different and integer. Your task is the following.
1. (a) (25 points) Implement the sweeping algorithm to decide intersection
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) (25 points) Implement the sweeping algorithm to decide intersection
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
4that 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.)
Write a method that does the following for an input set (10 points) 2.
segments where all endpoint coordinates are different integers. n of
-coordinates. Let y -coordinates and the range of x Find the range of
decide intersection n 10 n < u < . If 2 } min y ? max , y min x ? max x{ = max u
calling the method in Part 1b. Else, decide intersection calling the
method in Part 1a.
Write a program that does the following for an input value (10 points) 3.
. n
non-vertical segments where all end- n Create a “smooth” set of ?
. Recall n 10 n < u < point coordinates are different integers and 2
that the sweeping algorithm stops after finding the first intersection.
So, define the set so that only a few intersect at the end
range to attain a good evaluation of worst-case running x of the
time.
non-vertical segments based on the n Create a “sparse” set of ?
. n 100 u > smooth set but changing only one segment so that
Make sure this modified segment does not intersect any of the
other segments to avoid impact on running time due to new intersections.
Call the method in Part 2 with each of these sets and display the ?
running time of each in nanoseconds.
Run your program and fill the table below (adjust the (10 points) 4.
as needed according to your platform to obtain at least 5 n values of
measurements).
= 10 n nanoseconds
2 = 10 n
3 = 10 n
4 = 10 n
5 = 10 n
6
Smooth set
Sparse set
55. (20 points) What is the best function of n and/or u fitting your
measurements? Notice that you are evaluating rate of growth, you are
not being asked which one is faster. Are the results consistent with
the query time of the data structures and algorithms used? Justify
explaining the running time of each.
6