600.488 Homework Assignment 1
Due: Wednesday, February 3, 1999
50 Points

Sort the following list of functions of
n, so that whenever f
is before g, then f=O(g). Functions that are
Theta(*) of one
another should be listed together.
 n
 2^{n}
 7
 log n
 2^{(3log n)}
 n^{(0.1)}
 (log n)^{2}
 log log n
 2^{(log n)}
 n^{2 }
 n^{(log 3)}
 2^{(log log n)}

Show that if f(n) is O(d(n)) and g(n) is O(e(n)),
then f(n) + g(n)
is O(d(n) + e(n)).

Describe three different ways to represent a twodimensional point.
For each representation, describe a short method for determining if
this point is above or below the xaxis.

Suppose you are given
two polygonal chains, A and B, each represented as a
sequence of twodimensional points.
Suppose further that the sequence of points in both A and B
are ordered
by increasing xcoordinates, as shown below.
Describe an efficient method for determining if the chains A
and B ever cross each other (i.e., intersect).
What is the running time of your method?

Suppose you are given a polygonal chain, A, as in the previous
problem, i.e., a chain whose points are ordered by
xcoordinates.
Suppose futher that A is already in your computer's main
memory and you know that A is represented using an array.
Describe a very fast method for determining if a given vertical line,
L, intersects A, and if so, exactly where it intersects
A.
What is the running time of your method?
Goodrich's Home Page.