代做CS701-801、c/c++编程调试、Python/c++，Java代写、代做course material

日期：2019-04-28 08:48

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.

1

Submission 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.

2

Assignment 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)

3

Assignment:

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

4

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.)

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

5

5. (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