Data Structure for Solving Programming Problems Concerning Segments in a Sequence

There are many practical programming problems that involve finding the longest segment in a given sequence or largest rectangle in a given plane. Few of the solutions that text books on programming propose for these problems are easy enough to be understood by most computer science students. This paper therefore proposes new data structure, P-segment tables, for systematicaly solving programming problems concerning segments or rectangles. It gives a condition and an algorithm for making a P-segment table in O(n) time and space, and then it solves ten sample problems uniformly by using the methods proposed here. The problem set includes problems from programming text books and programming methodology literatures. We have conducted a survey through class exercises, examinations, and questionnaires in order to find out whether the programming method based on P-segment tables can easily be understood, is applicable to various problems, and is favorable for students. The survey methods and ..