Class Notes (1,100,000)
CA (650,000)
UW (20,000)
CS (1,000)
CS341 (20)
Lecture

# Assignment #3 This is the third assignment from winter 2010 term

Department
Computer Science
Course Code
CS341
Professor
Forbes Burkowski

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)
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+ (xmxi)(yjyi)/(xjxi). Alternatively, we can actually check
whether a point (xm, ym) is above the edge (xi, yi)(xj, yj), without division, by checking whether
(ymyi)(xjxi)>(xmxi)(yjyi) (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