COMP 258: Fall 1999
Homeworks
COMP258, Fall 1999: Homeworks
Problem set #1: Go surfing. due Aug 30.
Find an on-line source of geographic data for this area, or for the area you come from. (Examples can range from MapQuest to the US Geological Survey or Census.) Consider the type and format of the data you find:
- What questions can you answer using this data?
- What questions can a computer answer using this data?
Send me an email with a link and a one or two paragraph answer, and we’ll make these available on the web pages.
Answers (here) can point to sources
of data for interesting projects.
Problem Set #2, Due Weds, Sept 15.
Do two of the following three problems, and hand in your solutions either in class or anytime before midnight at my office sn333. Collaboration is permitted; good scholarship requires that collaborations be acknowledged.
- For the recursive selection procedure of Douglas and Peucker, analyze the expected running time under the assumption that whenever a fragment of a polygonal line is split, the splitting vertex is chosen with equal probability from the interior points of the fragment.
- Design an algorithm and data structure for line simplification that, given a tolerance, will produce a polygonal line that meets that tolerance. Ideally, the data structure should have linear size and the algorithm should produce a line with k segments in O(k) time.
- Consider the problem of simplifying either a river represented by two lines for its two banks, or a set of contour lines. Design an algorithm (at least at the pseudocode level, but if you want to implement it, then I’ll provide data) that will simplify, but guarantee that the simplified curves do not intersect.