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+ (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