|
|
How much space can I use? It should be proportional to the number of elements N. For Part 1, a a single parent-link array st[] should suffice. For Part 2, you will need an array of vertex marks, say mark[]. For Part 3, you'll need to add an array of weights, say wt[].
Do I need to submit code for all three parts? No, if you succeed in getting Part 3 to work, only submit code for this part. However, we recommend that you keep working copies of your solutions to Parts 1 and 2 around in case you don't get Part 3 to work. In this case, submit the highest numbered part that functions correctly.
What should my program do with self-loops, e.g., 3 3 50? It should discard the edge because there is already a better path from node 3 to itself: the empty path has infinite capacity.
Could you clarify the statement: "you cannot waste time following pointers all the way to the root if there is an LCA that is much closer to the two vertices"? Imagine that the path between p and q is small, say 10, but the path from p to the root is huge, say 1 million. Your code should only follow roughly 10 pointers (20 or 30 would be OK too). If p and q are not connected, then you do need to follow both pointers all of the way to their roots.
Could you clarify the statement: "you cannot waste time re-initializing all the vertex marks"? You are free to initialize all of the vertex marks once at the beginning of your program. However, you cannot march through the entire array and re-initialize all of the vertex marks after each iteration. The amount of work spent re-initializing the marks should be proportional to the number of marks set in that iteration.
Which paths should I count when computing the "average of all path lengths"? For simplicity, only count the paths that you would be printing out if N were small. For the example in the assignment, the average path length is 3.25 = (3 + 1 + 4 + 5) / 4.
When I insert an edge p-q (or equivalently q-p), I can do it by either reversing the path from p to its root or the path from q to its root. Which should I choose? The decision is arbitrary. A good strategy would be to reverse whichever path is shorter.
|
|
Input Format: We will test your programs by running "a.out 10 < input10.txt", where input10.txt is a text file consisting of integers separated by white space. It should not matter whether the integers are separated by a single space, multiple spaces, or even newlines. You may use the program generator.c to generate sample inputs.
Output Format: Follow the output format in the assignment using printf() with the "%4d" or "%8d" formatting option (or some other reasonable value). Do not use tabs since these will appear different (and ragged) on different systems.
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
|
|
Besides any problem specific information which is listed in each week's assignment or checklist, you should use this file to give the reader a high-level explanation of your source code and point to anything unusual or notable about your program (such as extra credit or known bugs).
|
|