Prüfer Codes

This assignment is due by the start of class, Wednesday 24 April, and has two parts: a mathematics part and a programming part.

Mathematics part

Problem 116 in the text

Programming part

Implement a program which takes a single line on stdin which is a space-separated Prüfer code and prints out to stdout a sorted list of edges of the tree having that Prüfer code. (Edit: To clarify, the lines should be sorted, as below, and the vertices in each line should be sorted.) The format for the output lines is one edge per line with a space separating the two vertices, with the lower-numbered vertex first. For example, here is an example input (coming into the program on stdin):

8 4 8 8 1 4

and here is the corresponding output (printed on stdout):

1 4
1 7
2 8
3 4
4 8
5 8
6 8

If the input is stored in the file input.txt, then the following command (assuming your program is named maketree) should create this output.txt file:

./maketree <input.txt >output.txt

The only output your program should print is the edges of the tree, as noted above. You may assume that the vertex labels start at 1. You may also assume that the biggest possible vertex label is 9.

I will test your program on a variety of inputs to test its validity (and I encourage you to do the same). Your program should come with only source code (no binaries). Your program should be adequately documented, must be your own work, and should include references to any resources you used in developing your program. I will grade the program based on several things:

1. Correctness: Is the program correct? Is the approach general? Is it decently efficient in memory and time? 2. Style: Is the code adequately documented and formatted? 3. Specification conformance: Does it conform to the input/output specification? Do you have a README file that documents how to compile (if needed) and run the program?

To submit this assignment, turn the answers to the mathematics question in during class. To turn in the program, email me a zip or tarball file by the start of class which includes your program and a file named README that gives a command to compile your program (if needed) and run your program.

Please come talk with me or email me if you have questions about the mathematics or about how to get your program to work according to the specs.

Page Tools