600.488 Homework Assignment 1

Due: Wednesday, February 3, 1999

50 Points

  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.
  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.