Assignment #3 This is the third assignment from winter 2010 term
This preview shows half of the first page. to view the full 2 pages of the document.
CS 341, Winter 2010
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:
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). 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
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
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).
You're Reading a Preview
Unlock to view full version