SOLVED ECE368 Programming Assignment #3

This assignment covers learning objective 1: An understanding of basic data structures, including stacks, queues, and trees; learning objective 5: An ability to design and implement appropriate data structures and algorithms for engineering applications. In programming assignment #2 (PA2), you implemented a program involving tree traversal(s) to compute the packing of rectangles, represented by a strictly binary tree. In that assignment, you assume that the given binary tree represents only one possible packing. H 3 V 1 2 (a) A binary tree (b) The corresponding packing 1 V 2 3 H H 3 V 1 2 (c) Re-rooting at V1 V V 1 H 3 2 1 V 2 3 H (5,4) (7,7) (3,3) (12,10) This assignment is a continuation of PA2 in some sense. However, this assignment is also different from PA2. In PA2, you assume that the given binary tree represents only one possible packing. In this assignment, you will learn that for a given binary tree with n leaf nodes (i.e., n rectangles), it can simultaneously represent 2n− 3 possible packing solutions, one of which is the solution you computed in PA2. Let us consider the 3-rectangle example shown in PA2 and redrawn here. Recall that the dimensions (width, height) of the three rectangles 1, 2, and 3 are (4,5), (7,7), and (3,3), respectively. The smallest room (shown in (b)) containing the three rectangles is of dimensions (12,10). (c) shows another binary tree representation that can be obtained from the representation in (a). This representation in (c) is obtained by re-locating the root node of the tree in (a) on the edge V1. We call the re-location of the root node as re-rooting. When we re-root V1, 1 is kept as the left node of V, as in the original tree. The parent node of V would now be the right child node of V in the re-rooted representation, and the original right child node of V now becomes the right child node of H, the original parent node of V. H 3 V 1 2 (d) Re-rooting at V2 V V H 2 3 1 1 V 2 3 H Essentially, we kept the V1 edge. Hence, we made the original parent node of V the new right child of V. As V is the right child of the original parent node, we made the original right child of V the new right child of the original parent node. (d) shows the binary tree representation obtained by re-rooting the edge V2. Here, we kept the V2 edge. Therefore, we made ECE36800  the original parent node of V the new left child of V. As V is the right child of the original parent node, we made the original left child of V the new right child of the original parent node. The representation in (c) still requires a room of dimensions (12,10) to pack all rectangles. However, the representation in (d) requires a smaller room of dimensions (12,7). In other words, the representation is (d) is more optimal than the representations in (a) and (c). Note that while this re-rooting operation may look similar, it is actually different from the rotation operations that are used to balance the height of a binary search tree. The preceding example demonstrates how you may re-root a strictly binary tree representation at edges that are separated from the original root node by just one edge. Now, we shall show you how to re-root at edges that are farther away from the original root node. H H H V V V V 1 2 3 4 5 6 8 7 (a) (b) (c) (d) V H H V H V V 1 2 3 4 5 6 8 7 (a) Re-rooting at VV V H H V H V V 1 2 3 4 5 6 7 8 (b) Re-rooting at VH H H V V H V V 1 2 3 4 5 6 8 7 (c) Re-rooting at HV V H V V H V 4 1 2 3 5 6 8 7 (d) Re-rooting at V4 H Consider the second example in PA2, as shown in the upper left corner of the preceding figure. We want to re-position at the root node on the edge V4 (d). First, note that the path from the V4 to the root node includes the edge HV (c), V H (b), and VV (a). Here, we do not consider the right branch of the root node. Let Re-Root(T, e) denote the new tree obtained by re-rooting at edge e of a given tree T, where e is one edge away from the root node of T. Let T be the tree representation in the upper left corner of the preceding figure. The following new tree representation corresponding to the operation of re-rooting at V4: Re-Root(Re-Root(Re-Root(Re-Root(T,VV) | {z } (a) ,V H) | {z } (b) ,HV) | {z } (c) ,V4) | {z } (d) ECE36800  The binary tree in (a) is re-rooted to form the binary tree in (b), which is re-rooted to form the binary tree in (c), which is then re-rooted to form the binary tree in (d). In other words, to re-root at an edge, it is necessary to first re-root at the edges from the root node (except for the edge immediately after the root node) to the edge of interest. Given a strictly binary tree of n > 1 leaf nodes (i.e., rectangles), there are 2n − 1 nodes altogether. Therefore, there are 2n − 2 edges altogether. Among these edges, we do not re-root the two edges right below the root nodes (as the re-rooting operation cannot be applied when there is no parent node). Therefore, other than the given representation, there are 2n − 4 representations that can be derived from re-rooting. Altogether, there are 2n−3 strictly binary tree representations for a given strictly binary tree representation. Therefore, there are 3 representations in the first example and 13 representations in the second example. When there are n = 2 leaf nodes, there is only one representation available. When there is n = 1 leaf node, there is only one representation available; no re-rooting is possible because there are no edges. Since you may have already found the solution of the explicit representation of a given strictly binary tree, this assignment asks you to find the solutions of the representations that can be derived from re-rooting as defined earlier. Given a binary tree representation of n ≥ 1 leaf nodes, you will write a program to find for each of the available re-rooted representations, the width and height of the smallest rectangular room to enclose all rectangles for that re-rooted representation. Again, when n = 1 or 2, there are no re-rooted representations available. When n > 2, there are 2n−4 re-rooted representations. H H H V V V V 1 2 3 4 5 6 8 7 (a) (e) V H H V H V V 1 2 3 4 5 6 8 7 (a) Re-rooting at VV (e) Re-rooting at V8 V H H V H V V 1 2 3 4 5 6 8 7 The key to this assignment is to again recognize that it takes tree traversal to perform the computation. Take a look at the preceding figure, where (a) is re-rooting at VV (as in the earlier example) and (e) is re-rooting at V8. In both cases, the smallest rectangular rooms for the root node V and its child node H can be computed with the rectangular rooms computed in the original tree on the left. It is not necessary to really re-root the tree, i.e., updates the pointers to construct different trees. What is again important is to figure out the necessary information to pass along as you traverse the tree. Deliverables: In this assignment, you are to develop your own include files and source files, gcc -O3 -std=c99 -Wall -Wshadow -Wvla -pedantic *.c -o pa3 ECE36800   Again, if you supply a Makefile, we will use the command ‘‘make pa3’’ to generate the executable pa3. The executable pa3 would be invoked as follows: ./pa3 in file out file1 out file2 out file3 As in PA2, the executable loads the binary tree from in file and produces three output files out file1, out file2, and out file2. You should model your main function after the main function in PA2. However, the input file in file is of the same format as the first output file of PA2. In other words, the input file is obtained by performing a post-order traversal of the strictly binary tree. Therefore, given a post-order traversal, you have to re-construct the corresponding strictly binary tree. (In PA2, you have to re-construct the corresponding strictly binary tree when you are given its pre-order traversal.) The first two output files are of the same format as the input file of PA2, a pre-order traversal of a strictly binary tree representing a packing. Please refer to the description file of PA2 for a description of the formats of in file, out file1, and out file2. Again, the format of in file of PA3 is the same as the format of out file1 of PA2. The format of out file1 and out file2 of PA3 is the same as the format of in file of PA2. The strictly binary tree of the packing for the first output file out file1 is obtained as follows: Starting from the root node, you alternately visit the left and right edges down the tree until you come to a leaf node. The first output file should contain the strictly binary tree of the packing that is obtained by re-rooting at the last edge of this path. Of course, to re-root at this last edge, it is necessary to perform re-rooting at corresponding edges along the way (except for the left edge of the root node). As a result, for the 3-rectangle example shown earlier, the corresponding re-rooted strictly binary tree is the same as the given strictly binary tree, as no re-rooting can be performed. On the other hand, for the 8-rectangle example, the given strictly binary tree should be re-rooted at the edge H1. The pre-order printing of the re-rooted strictly binary tree for the these two examples are in 3lr.pr and 8lr.pr. The strictly binary tree of the packing for the second output file out file2 is obtained as follows: Starting from the root node, you alternately visit the right and left edges down the tree until you come to a leaf node. The second output file should contain the strictly binary tree of the packing that is obtained by re-rooting at the last edge of this path. Again, to re-root at this last edge, it is necessary to perform re-rooting at corresponding edges along the way (except for the right edge of the root node). As a result, for the 3-rectangle example shown earlier, the corresponding re-rooted strictly binary tree is obtained by re-rooting at the edge V1. For the 8-rectangle example, the given strictly binary tree should be re-rooted at the edge V6. Of course, to obtain this, we have to re-root at edge VV and then V6. The pre-order printing of the re-rooted strictly binary tree for the these two examples are in 3rl.pr and 8rl.pr. We now provide the details of the output file out file3. Format of third output file ECE36800  argv[4] out file3 contains the name of the file that pa3 would use to store the dimensions of the smallest rectangular room that encloses all rectangular blocks for each re-rooted representation. The file is divided into lines, and each line corresponds to a node in the given strictly binary tree, and the nodes are printed in a pre-order traversal fashion. Recall that the re-rooting is defined based on an edge in the given strictly binary tree. Therefore, each node, except the root node, can uniquely identify the edge that connects the node to its parent node in the given strictly binary tree. There are therefore at most three nodes that each does not correspond to an edge that could be re-rooted. The root node does not have a parent edge. If the given strictly binary tree has n ≥ 2 leaf nodes, the left child node or right child node also does not correspond to an edge that could be re-rooted. If such a node is a leaf node, which is a rectangular block, we print to the output file with the format "%d\n", where the int is the label of the rectangular block. If it is a non-leaf node, we print a character (followed by a newline character): "%c\n". The character is either ’V’ or ’H’, representing either a vertical cutline or a horizontal cutline, respectively. For the other lines in the output file, each of them corresponds to an edge (connecting the node to its parent node) that could represent a re-rooted topology. If the node is a leaf node, we print to the output file with the format "%d(%d,%d)\n", where the first int is the label of the rectangular block, the second int and the third int are respectively the width and height of the smallest rectangular room enclosing all rectangular blocks for this re-rooted representation. If the node is a non-leaf node, we print to the output file with the format "%c(%d,%d)\n", where the first char is either ’V’ or ’H’ representing the cutline of the non-leaf node, and the two int’s are respectively the width and height of the smallest rectangular room enclosing all rectangular blocks for this re-rooted representation. For the 3-rectangle example, the following is the expected third output file (3.rdim): H 3 V 1(12,10) 2(12,7) Note that the first three lines correspond to the root node, left of root node, and the right of root node, all of which do not have re-rooted representations. For the 8-rectangle example, the following is the expected third output file (8.rdim): ECE36800  H H V(11,15) 2(12,14) 5(14,15) 1(11,15) V V(13,11) H(13,11) 3(13,14) V(12,16) 7(13,16) 4(15,13) 6(13,11) 8(11,15) The first, second, and the seventh lines correspond to the root node, left of root node, and right of root node, all of which do not have re-rooted representations. Submission: The assignment requires the submission (through Brightspace) of a zip file called pa3.zip that contains the source code (.c and .h files). You can create your zip file as follows: zip pa3.zip *.c *.h Your zip file should not contain a folder. You may also include a Makefile in the zip file. In that case, you can create your zip as follows: zip pa3.zip *.c *.h Makefile Grading The grade depends on the correctness of your program and the efficiency of your program. The first output file accounts for 25 points, and the second output file accounts for 25 points, and the third output file accounts for 50 points of the entire grade. Any output files that do not follow the formats specified in this assignment will be considered to be wrong. It is important that your program can accept any legitimate filenames as input or output files. Even if you cannot produce all output files correctly, you should still write the main function such that it produces as many correct output files as possible. If you do not the algorithm to produce the necessary information required to generate an output file, you should leave the output file as an empty file. ECE36800  It is important all the files that have been opened are closed and all the memory that have been allocated are freed before the program exits. Any memory leaks or errors will result in 50% penalty. What you are given We provide the post-order traversals of the 3-rectangle and 8-rectangle examples in 3.po and 8.po, respectively. We also provide the three output files of the 3-rectangle (3lr.pr, 3rl.pr, and 3.rdim, respectively) and 8-rectangle examples (8lr.pr, 8rl.pr, and 8.rdim, respectively. We also provide the post-order traversals of 100-rectangle, 500-rectangle, and 1000-rectangle examples in 100.po, 500.po, and 1K.po, respectively. ECE36800