600.488 Homework Assignment 1

1. 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ⁿ
   • 7
   • log n
   • 2^{(3log n)}
   • n^(0.1)
   • (log n)²
   • log log n
   • 2^{(log n)}
   • n²
   • n^{(log 3)}
   • 2^{(log log n)}
2. 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)).
3. Describe three different ways to represent a two-dimensional point. For each representation, describe a short method for determining if this point is above or below the x-axis.
4. Suppose you are given two polygonal chains, A and B, each represented as a sequence of two-dimensional points. Suppose further that the sequence of points in both A and B are ordered by increasing x-coordinates, 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?

   

5. Suppose you are given a polygonal chain, A, as in the previous problem, i.e., a chain whose points are ordered by x-coordinates. 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.