This

**preview**shows half of the first page. to view the full**2 pages of the document.**CS 341, Winter 2010

Timothy Chan

Assignment 3 (due March 9 Tuesday noon)

Please read http://www.student.cs.uwaterloo.ca/~cs341/policies.html ļ¬rst for general instructions

and http://www.student.cs.uwaterloo.ca/~cs341/prog.html for programming guidelines.

1. [27 marks]Programming question. Implement the O(n)-time algorithm for the āintersectionā problem

from Assignment 2, Question 4(c). (See the model solutions.)

The input to your programs is given in the following format, where the xiās and yiās are all integers:

n1n2

x1y1

.

.

.

xn1yn1

x0

1y0

1

.

.

.

x0

n2y0

n2

Here, n1denotes the size of the increasing set Aand n2denotes the size of the decreasing set B. The

i-th point of Ahas coordinates (xi, yi), and the i-th point of Bhas coordinates (x0

i, y0

i). You may

assume no two x-coordinates and no two y-coordinates are the same; you may assume that the input

is valid (i.e., Ais indeed increasing and Bis decreasing, but the points are not pre-sorted) and an

intersection exists.

The output to your program should have just one line in the following format:

i j k `

This means that an intersection exists between the edge (xi, yi)(xj, yj) of Aand the edge (x0

k, y0

k)(x0

`, y0

`)

of B. Do not include any other information or text in the output.

Note: donāt use the linear-time selection algorithm from class (it is too messy to implement!). Either

use the randomized quick-select algorithm, or more simply, avoid selecting the median element in an

array and instead pick a randomly chosen element in the array. (It can be shown that with the latter

strategy, the expected runtime is still O(n).) A random index can be generated using rand() or

drand48() from stdlib in C++, or java.util.Random in Java.

Another Note: the y-coordinate of the intersection of an edge (xi, yi)(xj, yj) with a vertical line x=

xmis given by the formula yi+ (xmāxi)(yjāyi)/(xjāxi). Alternatively, we can actually check

whether a point (xm, ym) is above the edge (xi, yi)(xj, yj), without division, by checking whether

(ymāyi)(xjāxi)>(xmāxi)(yjāyi) (assuming xi< xj).

(a) [22 marks] Hand in a printed copy of your program and electronically submit the source ļ¬le,

named a3.cpp or a3.java.

(b) [5 marks] Do experiments to test if your O(n) algorithm indeed beats a sorting-based O(nlog n)

algorithm (e.g., Assignment 2, Question 4(a)) for suļ¬ciently large input sizes in practice. For

this purpose, you do not need to give a full implementation of the algorithm from A2Q4(a).

Just compare the runtime of your O(n) algorithm against the runtime of a call to an O(nlog n)

sorting algorithm to sort the x-coordinates of the input points (you may use the library sorting

subroutines, e.g., qsort() from stdlib in C++, or Arrays.sort from java.util.Arrays).

1

###### You're Reading a Preview

Unlock to view full version