|
|
What should I do if many lines separate a query pair? Output only one such line.
Where can I get a PostScript viewer for Windows? Go to the Ghostscript home page. Download and install AFPL Ghostscript 7.04, then download and install GSView 4.2.
Do I need to use the search tree approach described in the assignment? No. However, if you use another method, be sure to provide a good justification in your readme.txt.
What is meant by the external path length? See Sedgewick Definition 5.6.
|
|
Input and output. Here are a number of sample input files. We also encourage you to create your own (possibly pathological) inputs to help test your program. We'll consider awarding extra credit if you submit inputs that cause your program (and other students' programs) problems. The input should be very small, and it should expose a potential flaw that other programs are likely to have. We'll post these input files for other students to use.
Reference solutions. For reference, we provide executable code for our solution in Windows, Solaris, and OS X. Because of degenerate cases (and varying ways to deal with them), we cannot guarantee that our solutions are always accurate. If you discover any potential bugs, please let us know.
|
|
We will compile your program with "gcc *.c" so you are free to organize your program as you see fit. As usual, we encourage and reward sound design principles.
Here is a template readme.txt file. It should contain the following information:
Unix users may find the shell script timeit.csh useful for computing a table of CPU times.
|
|
|
|
Can you get logarithmic query times in the worst case? Yes. This was first discovered at Princeton by Dobkin and Lipton. They designed an algorithm that achieves O(log N) query time with O(N^2) space and preprocessing time. They also showed that if binary decisions are used to locate the query points, then you can't do better than log N time per query.
Quadratic space seems excessive. Can you do better? Yes, there are several more complicated algorithms that achieve the logarithmic query time in only linear space. The first such method was discovered at Princeton by Lipton and Tarjan. Chazelle (another Princeton professor) created something called a "hive graph" that also solves the problem in this bound. A simpler algorithm using persistent search trees discovered by Sarnak and Tarjan is the focus of a COS 423 lecture. The preprocessing step uses O(N) space and O(N log N) time; queries take O(log N) time.