ECE36800 Programming Assignment 3
Due Monday, October 19, 2020, 11:59pm
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.
You are required to implement a program to compute the signal delay of an RC (resistive-capacitive)
tree, represented by a strictly binary tree. In a strictly binary tree, a non-leaf node always has two child
nodes.
Delay model
Every tree edge in the binary tree is a wire with some resistance and some capacitance. Consider a tree
edge e = (u, v) of length le connecting a parent node u and to a child node v. The resistance and capacitance
of the wire are given by
Re = r ×le, Ce = c×le,
where r and c are per-unit-length resistance and per-unit-length capacitance, respectively. A first-order
model of the wire is given below:
If the child node v happens to be a leaf node, it has an additional capacitance value associated with it,
called the sink capacitance, denoted by cv. The corresponding circuit is given below:
The tree is driven at its root by a driver (or buffer) with a output resistance rd. Therefore, the corresponding
RC-tree of a binary tree is as follows:
ECE36800 Purdue University 1
c Cheng-Kok Koh
(a) A binary tree (b) The corresponding RC tree
In the preceding figure,
corresponds to the total capacitance at node i. Therefore,
Moreover, the driver output resistance rd is between a source node, denoted as src and the root of the binary
tree u. We can think of rd being the resistance of the edge (src,u).
Given an RC tree T, the following delay model gives an approximation of the delay from the source
node src to node j. Let Path(src, j) denote the path in the tree from node src to node j. Moreover, let
RPath(src,i)∩Path(src, j)
denote the total resistance along the path common to Path(src,i) and Path(src, j). The
delay from src to j is given by the following expression:
Under this model, the delays of nodes u, v, x, y, and z are:
This delay model has an unusual property. The delays of nodes along the path from the source to a sink
do not increase monotonically. For example, it is possible that tv is less than tz even though node z appears
at the end of the path from src to z, and node v appears in the middle of the path.
For the delay model to be properly defined for all nodes in a tree, you may assume that the resistance rd
is a strictly positive value.
Tree traversals
Using an appropriate tree-traversal algorithm, the delay of a single node can be computed in O(n) timecomplexity,
where n is the total number of nodes in the RC tree. In fact, the delays of all nodes can be
computed in O(n) time-complexity. In order to achieve that, it is important to analyze how ty and tz are
related tv, and how tv and tx are related to tu in the preceding example.
To be more precise,
in the preceding example.
While we may simplify the expression, but we would not do that here as the focus is to demonstrate the
relationship between the delays of different nodes in the tree.
Similarly,
as the respective sums of all capacitances at
all nodes in the subtrees rooted at x, y, z. Again, we have to ask the questions of what information is required
to compute the sum of capacitances at nodes in a subtree.
ECE36800 Purdue University 3
c Cheng-Kok Koh
This assignment is in fact about applying suitable tree traversal algorithms to pass and compute information
required to compute the delays.
Deliverables
In this assignment, you are required to develop your own include file(s) and source file(s), which can be
compiled with the following command:
gcc -std=c99 -pedantic -Wvla -Wall -Wshadow -O3 *.c -o pa3
It is recommended that while you are developing your program, you use the “-g” flag instead of the
“-O3” flag for compilation so that you can use a debugger if necessary. All declarations and definition of
data types and the functions associated with the data types should reside in the include file delay.h or
source file delay.c. The main function should reside in the file pa3.c.
The executable pa3 would be invoked as follows:
./pa3 input filename output filename1 output filename2 output filename3 output filename4
The executable loads the RC tree from a file whose filename is given as input filename (note that
the input filename can be any arbitrary valid filename; it is effectively the string stored as argv[1]),
prints the topology of the RC tree in pre-order to a file whose filename is given as output filename1
(effectively, argv[2]), calculates the delay of all nodes in the tree, and print to a file whose filename is
given as output filename2 (effectively, argv[3]) the delays of all leaf nodes.
Format of input file
The format of the input file specified by the input filename is as follows. The first line of the file
contains three numbers (in the format of "%le %le %le\n"), where the first double specifies the output
resistance at the source, rd (Ω), the second double specifies the per-unit-length resistance of a wire, r
(Ω/unit-length), and the third double specifies the per-unit-length capacitance of a wire, c (F/unit-length).
The rest of the file is divided into lines, and each line corresponds to a node in the binary tree. The order
in which the nodes are printed is based on a post-order traversal of the binary tree. If it is a leaf node (which
is a sink), it has been printed with the format "%d(%le)\n", where the int is the label of the sink, and the
double is the sink node capacitance (F). If it is a non-leaf node, it has been printed with the format "(%le
%le)\n", where the first double is the wire length to the left child and the second double is the wire length
to the right child.
Format of first output file
The first output file is a pre-order printing of the given RC tree. Each line corresponds to a node in the
binary tree. If it is a leaf node (which is a sink), you print the node with the format "%d(%le)\n", where
the int is the label of the sink, and the double is the sink node capacitance (F). If it is a non-leaf node, you
print with the format "(%le %le)\n", where the first double is the wire length to the left child and the
second double is the wire length to the right child.
Format of second output file
The second output file stores in the binary format the resistance and capacitance associated with each
node. The resistance associated with a node is the resistance of the edge that connects the node to its parent.
If the node is the root node, the resistance is the driver output resistance Rd since the driver can be viewed
as the “parent” node of the root node. The capacitance associated with a node is the total capacitance of all
capacitors directly connected to that node. For node v in the given example,
ECE36800 Purdue University 4
c Cheng-Kok Koh
For each non-leaf node, you write an int of value −1, followed by a double for the resistance associated
with the node and another double for the capacitance associated with the node. For a leaf node, you write
the label (int), followed by a double for the resistance associated with the node and another double for
the capacitance associated with the node. The file size of the second output file should be the number of
nodes multiplied by the sum of sizeof(int) and 2×sizeof(double).
The order in which you write the parameters associated with a node to the output file is pre-order.
Format of third output file
The third output file stores in the binary format the total capacitance of the subtree rooted at each node.
For node v in the given example,
For each non-leaf node, you write an int of value −1, followed by a double for the total capacitnace
of the subtree rooted at that node. For a leaf node, you write the label (int), followed by a double for the
capacitance associated with the node. The file size of the third output file should be the number of nodes
multiplied by the sum of sizeof(int) and sizeof(double).
The order in which you write the parameters associated with a node to the output file is pre-order.
Format of fourth output file
The fourth output file stores in the binary format the delays of the leaf nodes of the given RC tree in
in-order fashion. For each leaf node, you write the label (int) and the delay (double). The file size of
the second output file should be the number of leaf nodes multiplied by the sum of sizeof(int) and
sizeof(double).
Electronic Submission
The project requires the submission (electronically) of the C-code (source and include files) through
Brightspace. You should create and submit a zip file called pa3.zip, which contains the .h and .c files.
Your zip file should not contain a folder.
zip pa3.zip *.c *.h
You should submit pa3.zip to Brightspace.
If you want to use a makefile for your assignment, please include the makefile in the zip file. If the zip
file that you submit contains a makefile, we use that file to make your executable (by typing “make pa3” at
the command line to create the executable called pa3).
Grading
The assignment will be graded based on the four output files produced by your program, evaluated using
sample files that are randomly generated. The first output accounts for 20%, the second output accounts for
20%, the third output accounts for 30%, and the fourth output accounts for 30%. It is important that your
program can accept any legitimate filenames as input or output files.
Even if you cannot produce the second, third, or fourth output file correctly, you should still write the
main function such that it produces as many valid output files as possible and leave any remaining output
files as empty so that you can earn partial credit.
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. Memory errors or any errors reported by valgrind will result in a
50-point penalty.
Be aware that we set a time-limit for each test case based on the size of the test case. If your program
does not complete its execution before the time limit for a test case, it is deemed to have failed the test case.
What you are given
ECE36800 Purdue University 5
c Cheng-Kok Koh
You are given 5 sample input files (3.txt, 5.txt, 10.txt 100.txt, 1000.txt) and two sets of sample output
files (3.pre, 3.rc, 3.tcap, 3.delay, 5.pre, 5.rc, 5.tcap, and 5.delay). The file 3.txt corresponds to the 3-sink
example used in this document, with leaf nodes x, y, and z being labeled as 1, 2, and 3, respectively. The
file 3.pre corresponds to the pre-order printing of this example; the file 3.rc stores in pre-order fashion,
the resistance and capacitance parameters of each node in the tree; the file 3.tcap stores for each node, in
pre-order fashion, the total capacitance of the subtree for which the node is the root; the file 3.delay stores
the delays of sink nodes in pre-order fashion. Similarly, 5.pre, 5.rc, 5.tcap, and 5.delay are the pre-order
printings of all nodes, resistance and capacitance parameters, total capacitances, and sink delays of the
example in 5.txt, respectively.
To help you get started, we also provide you 3.rc.txt, 3.tcap.txt, 3.delay.txt and 5.rc.txt, 5.tcap.txt, and
5.delay.txt, which are the labels and delays of sink nodes (in pre-order) in text format.
In 3.rc.txt and 5.rc.txt, each line corresponds to a node. If it is not a leaf node (sink node), it is printed
with the format "(%le %le)\n", where the first double is the resistance of the edge connecting the node
and its parent and the second double is the capacitance at that node. If the node is the root node, the
resistance is simply Rd as we can view the driver as the “parent” node of the root node. If it is a leaf
node (sink node), it is printed with the format "%d(%le %le)\n", where the int is the node label, and the
first double is the reistance of the edge connecting the node and its parent and the second double is the
capacitance at that node.
In 3.tcap.txt and 5.tcap.txt, each line corresponds to a node. If it is not a leaf node (sink node), it is
printed with the format "(%le)\n", where the double is the total capacitance of subtree rooted at the node.
If it is a leaf node (sink node), it is printed with the format "%d(%le)\n", where the int is the node label,
and the double is the (total) capacitance at that node.
In 3.delay.txt and 5.delay.txt, each line corresponds to a sink and its delay. Each line is printed with the
format "%d(%le)\n", where the int is the node label, and the double is the node delay.
While developing your program, you probably want to first print to output files as text file using
fprintf. When you are confident of the correctness of your program, you would then write to the output
files as binary files using fwrite.
10.txt, 100.txt, and 1000.txt contain examples of 10 sinks, 100 sinks, and 1000 sinks, respectively. Note
that you should not assume that you can deduce the size of the RC tree based on the filename.
Additional information
As this assignment involves floating point computation, it is unlikely that your results will match my
results exactly. We will allow for some minor discrepancies between your results and my results.
Other important deadlines:
Project plan: Due Wednesday, October 7, 2020, 11:59pm
Project post-mortem: Due Tuesday, October 20, 2020, 11:59pm
For each of these two deadlines, upload a PDF file following the corresponding template provided in the
“Programming assignments”folder on Brightspace.
ECE36800 Purdue University 6
c Cheng-Kok Koh