ECE36800语言代做、代写Programming留学生编程、Java，c++程序调试

日期：2020-11-13 11:38

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