[SOLVED] Ece368 programming assignment #3 in programming assignment #2 (pa2), you implemented a program involving tree traversal(s) to compute the packing

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

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)

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

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

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
”,
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
”.
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)
”,
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)
”,
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):

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.

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.