ECE36800语言写作、辅导Programming留学生编程

” ECE36800语言写作、辅导Programming留学生编程ECE36800 Programming Assignment 3Due Monday, October 19, 2020, 11:59pmThis 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 andalgorithms 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 childnodes.Delay modelEvery tree edge in the binary tree is a wire with some resistance and some capacitance. Consider a treeedge e = (u, v) of length le Connecting a parent node u and to a child node v. The resistance and capacitanceof the wire are given byRe = r le, Ce = cle,where r and c Are per-unit-length resistance and per-unit-length capacitance, respectively. A first-ordermodel 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 correspondingRC-tree of a binary tree is as follows:ECE36800 Purdue University 1c Cheng-Kok Koh(a) A binary tree (b) The corresponding RC treeIn 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 binarytree 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 sourcenode src to node j. Let Path(src, j) denote the path in the tree from node src to node j. Moreover, letRPath(src,i)Path(src, j)denote the total resistance along the path common to Path(src,i) and Path(src, j). Thedelay 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 sinkdo not increase monotonically. For example, it is possible that tv is less than tz even though node z appearsat 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 rdis a strictly positive value.Tree traversalsUsing 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 becomputed in O(n) time-complexity. In order to achieve that, it is important to analyze how ty and tz arerelated 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 therelationship between the delays of different nodes in the tree.Similarly,as the respective sums of all capacitances atall nodes in the subtrees rooted at x, y, z. Again, we have to ask the questions of what information is requiredto compute the sum of capacitances at nodes in a subtree.ECE36800 Purdue University 3c Cheng-Kok KohThis assignment is in fact about applying suitable tree traversal algorithms to pass and compute informationrequired to Compute the delays.DeliverablesIn this assignment, you are required to develop your own include file(s) and source file(s), which can becompiled with the following command:gcc -std=c99 -pedantic -Wvla -Wall -Wshadow -O3 *.c -o pa3It 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 ofdata types and the functions associated with the data types should reside in the include file delay.h orsource 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 filename4The executable loads the RC tree from a file whose filename is given as input filename (note thatthe 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 isgiven as output filename2 (effectively, argv[3]) the delays of all leaf nodes.Format of input fileThe format of the input file specified by the input filename is as follows. The first line of the filecontains three numbers (in the format of %le %le %le\n), where the first double specifies the outputresistance 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 orderin which the nodes are printed is based on a post-order traversal of the binary tree. If it is a leaf node (whichis a sink), it has been printed with the format %d(%le)\n, where the int is the label of the sink, and thedouble 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 lengthto the right child.Format of first output fileThe first output file is a pre-order printing of the given RC tree. Each line corresponds to a node in thebinary tree. If it is a leaf node (which is a sink), you print the node with the format %d(%le)\n, wherethe int is the label of the sink, and the double is the sink node capacitance (F). If it is a non-leaf node, youprint with the format (%le %le)\n, where the first double is the wire length to the left child and thesecond double is the wire length to the right child.Format of second output fileThe second output file stores in the binary format the resistance and capacitance associated with eachnode. 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 viewedas the parent node of the root node. The capacitance associated with a node is the total capacitance of allcapacitors directly connected to that node. For node v in the given example,ECE36800 Purdue University 4c Cheng-Kok KohFor each non-leaf node, you write an int of value 1, followed by a double for the resistance associatedwith the Node and another double for the capacitance associated with the node. For a leaf node, you writethe label (int), followed by a double for the resistance associated with the node and another double forthe capacitance associated with the node. The file size of the second output file should be the number ofnodes multiplied by the sum of sizeof(int) and 2sizeof(double).The order in which you write the parameters associated with a node to the output file is pre-order.Format of third output fileThe 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 capacitnaceof the subtree rooted at that node. For a leaf node, you write the label (int), followed by a double for thecapacitance associated with the node. The file size of the third output file should be the number of nodesmultiplied 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 fileThe fourth output file stores in the binary format the delays of the leaf nodes of the given RC tree inin-order fashion. For each leaf node, you write the label (int) and the delay (double). The file size ofthe second output file should Be the number of leaf nodes multiplied by the sum of sizeof(int) andsizeof(double).Electronic SubmissionThe project requires the submission (electronically) of the C-code (source and include files) throughBrightspace. 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 *.hYou 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 zipfile that you submit contains a makefile, we use that file to make your executable (by typing make pa3 atthe command line to create the executable called pa3).GradingThe assignment will be graded based on the four output files produced by your program, evaluated usingsample files that are randomly generated. The first output accounts for 20%, the second output accounts for20%, the third output accounts for 30%, and the fourth output accounts for 30%. It is important that yourprogram 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 themain function such that it produces as many valid output files as possible and leave any remaining outputfiles 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 allocatedare freed before the program exits. Memory errors or any errors reported by valgrind will result in a50-point penalty.Be aware that we set a time-limit for each test case based on the size of the test case. If your programdoes not complete its execution before the time limit for a test case, it is deemed to have failed the test case.What you are GivenECE36800 Purdue University 5c Cheng-Kok KohYou are given 5 sample input files (3.txt, 5.txt, 10.txt 100.txt, 1000.txt) and two sets of sample outputfiles (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-sinkexample used in this document, with leaf nodes x, y, and z being labeled as 1, 2, and 3, respectively. Thefile 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, inpre-order fashion, the total capacitance of the subtree for which the node is the root; the file 3.delay storesthe delays of sink nodes in pre-order fashion. Similarly, 5.pre, 5.rc, 5.tcap, and 5.delay are the pre-orderprintings of all nodes, resistance and capacitance parameters, total capacitances, and sink delays of theexample 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, and5.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 printedwith the format (%le %le)\n, where the first double is the resistance of the edge connecting the nodeand its parent and the second double is the capacitance at that node. If the node is the root node, theresistance is simply Rd as we can view the driver as the parent node of the root node. If it is a leafnode (sink node), it is printed with the format %d(%le %le)\n, where the int is the node label, and thefirst double is the reistance of the edge connecting the node and its parent and the second double is thecapacitance 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 isprinted 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 theformat %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 usingfprintf. When you are confident of the correctness of your program, you would then write to the outputfiles as binary files using fwrite.10.txt, 100.txt, and 1000.txt contain examples of 10 sinks, 100 sinks, and 1000 sinks, respectively. Notethat you should not assume that you can deduce the size of the RC tree based on the filename.Additional informationAs this Assignment involves floating point computation, it is unlikely that your results will match myresults 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:59pmProject post-mortem: Due Tuesday, October 20, 2020, 11:59pmFor each of these two deadlines, upload a PDF file following the corresponding template provided in theProgramming Assignmentsfolder on Brightspace.ECE36800 Purdue University 6c Cheng-Kok Koh如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“