CS211 Spring 2021
Data structure代做 | 作业Algorithm | project | assignment | c代写 – 这是一个关于Data structure的题目, 主要考察了关于Data structure的内容,是一个比较经典的题目, 是有一定代表意义的Data structure/Algorithm等代写方向, 这是值得参考的assignment代写的题目
Programming assignment IV
David Menendez
This assignment will provide more practice programming in C and working with circuits and
digital logic. It has two parts. In the first part, you will design several circuits using a simple
specification language. In the second part, you will write a program that generates a truth table
given such a circuit specification.
Advice Start working early. Before you do any coding, make sure you can run the auto-grader, create a Tar archive, and submit that archive to Sakai. You dont want to discover on the last day thatscpdoesnt work on your personal machine. Decide your data structures and algorithms first. Section 4 describes one method for implementing the program that performs well, but you are free to design your own. Writing out pseudocode is not required, but it may be a good idea. When writing your program, use the auto-grader to create thebuilddirectory, and usemakein that directory to compile your code. This will save you time, keep your source code separated from your compiled files, and ensure that you are compiling your program consistently. Start working early. You will almost certainly encounter problems you did not anticipate while writing this project. Its much better if you find them in the first week.
1 Overview
You will write a programtruthtablethat reads a file containing a description of a circuit, and prints that circuits truth table. The files specify (1) the number and names of eachinputto the circuit, (2) the number and names of eachoutputfrom the circuit, and (3) the logic gates and components that make up the circuit. In order to indicate the connections between gates, each connection is also given a name. For example, this is a description for a circuit that implements a 3-argument AND gate: INPUT 3 a b c OUTPUT 1 d AND a b x AND c x d Note that it contains three inputs (a,b, andc), a single output (d), and two AND gates, each of which has two inputs and one output. The variablexindicates an internal connection between the first AND gate and the second. See section 3 for details on the specification language.
When given this file,truthtableshould print:
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 0
1 0 0 | 0
1 0 1 | 0
1 1 0 | 0
1 1 1 | 1
The three columns on the left correspond to the three inputs, and the column to the right corresponds to the output. This assignment has two parts:
Part 1 (100 points) For this part, the circuit descriptions will be sorted so that each temporary
variable appears as an output parameter before any appearances as an input variable.
Part 2 (Extra Credit) For this part, the circuit descriptions willnotbe sorted, meaning that a
temporary variable may be used as an input parameter before its use as an output parameter.
2 Program
truthtabletakes a single argument, which is the name of a file containing a circuit description. The behavior oftruthtableis unspecified if it receives no arguments or more than one argument, but you should still check that the number of arguments is correct. (One possibility is to have truthtableread from standard input if no file argument is given.)
Usage
$ ./truthtable my-cool-circuit.txt
0 0 | 0 0
0 1 | 0 1
1 0 | 0 1
1 1 | 1 0
Input The input to your program will be a single circuit description using the language described
in section 3. The first argument totruthtablewill identify a file containing this circuit description.
You MAY assume that the input is correctly formatted and that no variable depends on its own
output.
Output The output oftruthtableis a truth table showing each combination of inputs and the
corresponding output for the specified circuit. Each column in the table corresponds to a specific
input or output variable, which are given in the same order as their declaration in theINPUTand
OUTPUTdirectives. Columns are separated by a single space, and a vertical bar (|) occurs between
the input and output variables.
Note that no white space follows the final column.
3 Specification Language
In this language, circuits are specified with a series ofdirectives. These directives refer to various namedvariables, which correspond to wires in a circuit diagram. Many of the directives describe a logic gate or similar building block, indicating which varibles correspond to its input and output. Each directive has the form of anamefollowed by one or moreparameters, separated by whitespace. The name indicates which directive and determines the number of parameters. Some directives take a variable number of parameters; their first parameter will always be an integer which is used to determine the number of parameters. Depending on the directive, some parameters will be inputs and some will be outputs. Variables in a circuit can be classified into three non-overlapping sets.Input variablesmust be declared by theINPUTdirective, and may only occur as input parameters.Output variablesmust be declared by theOUTPUTdirective and may occur exactly once in an output parameter. All other variables aretemporary variablesand must occur exactly once as an output parameter and zero or more times as an input parameter. A variable name consists of a letter followed by zero or more letters or digits. You may assume that variable names are no longer than 16 characters. In addition to variables, the constant inputs 0 and 1 may be used as input parameters. These are always false and always true, respectively. Finally,_may be used as the output of a gate, indicating that the output of a gate is discarded. Note that whitespace may include one or more spaces, tabs, or newline characters. It is recommended to usefscanf()to read the files, and to use a format code such as" %16s"to skip whitespace before reading the next variable or directive name. By convention, we will use multiple spaces to separate the inputs and outputs of a gate, but this is not required and has no special meaning. It is purely for readability. Similarly, we will often put a blank line betweenOUTPUTand the first gate, but this is also done purely for readability. Your program should treat repeated newlines the same as single newlines (or, ideally, the same as any whitespace). Use offgets()is not recommended and will only make your life harder. Remember that fscanf()is not limited to reading an entire line at once.
3.1 Directives
This section describes each of the directives used to describe a circuit. Each directive is followed by several parameters. A parameternis always an integer and has a special meaning. Input parameters are indicated asiand output parameters are indicated aso. Ellipses () are used to indicate a variable number of parameters.
- INPUTn i 1 in Declaresninput variables. This directive must always occur first in a circuit description.
- OUTPUTn o 1 on Declaresnoutput variables. This directive must always occur second in a circuit description.
- NOTi o Represents anotgate in logic design. Computeso=i.
- ANDi 1 i 2 o Represents anandgate in logic design. Computeso=i 1 i 2.
- ORi 1 i 2 o Represents anorgate in logic design. Computeso=i 1 +i 2.
- NANDi 1 i 2 o Represents anandgate in logic design. Computeso=i 1 i 2
- NORi 1 i 2 o Represents anorgate in logic design. Computeso=i 1 +i 2
- XORi 1 i 2 o Represents anxorgate in logic design. Computeso=i 1 i 2 , whereindicatesexclusive or.
- DECODERn i 1 ino 0 o 2 n 1 Represents ann: 2ndecodergate in logic design. The first argument gives the number of inputs,n. The nextnparameters are the inputs, followed by 2 nparameters indicating the outputs. The inputs are interpreted as ann-bit binary numbersin the range 0 ,, 2 n 1 , wherei 1 is the most significant bit andinis the least significant bit. The outputoswill be 1 and all others will be 0.
- MULTIPLEXERn i 0 i 2 n 1 i 1 ino Represents a 2 n: 1multiplexergate in logic design. The inputs to a multiplexer are either regular inputs or selectors, indicated byiandi, respectively. The first parameter,n, gives the number of selectors. The next 2 nparameters give the regular inputs, followed bynselector inputs, and finally the output. The selector inputs are interpreted as ann-bit binary numbersin the range 0 ,, 2 n 1. The output iso=is.
- PASSi o Represents the absence of a gate. Computeso=i. This may be used to convert a temporary variable into an output variable.
3.2 Parsing
The specification language can be thought of as a sequence of tokens separated by whitespace. No keyword or variable name in the language exceeds 16 characters, so it is safe to usefscanf()with the format code%16s, which will read a token of up to 16 non-whitespace characters. Each directive will be either be followed by a fixed number of parameters or by a number that will determine the number of parameters. Thus, your parsing code will always be able to tell whether it expects a directive name, integer, input parameter, or output parameter next. For safety, your program should always check thatfscanf()succeeded and that it received the expected token type. If something has gone wrong, either because of bad input or a program error, you want to know about it!
3.3 Examples
This circuit describes a half-adder, wheresis the sum andcis the carry.
INPUT 2 A B
OUTPUT 2 C S
AND A B C
XOR A B S
This circuit computesz=ab+ac:
INPUT 3 a b c
OUTPUT 1 z
AND a b x
AND a c y
OR x y z
Note thatxandyare temporary variables, since they were not declared inINPUTorOUTPUT.
This circuit description is invalid, becuase it uses an output variable as an input parameter:
INPUT 3 IN1 IN2 IN
OUTPUT 2 OUT1 OUT
AND IN1 IN2 OUT
OR IN3 OUT1 OUT
This can be rewritten usingPASS:
INPUT 3 IN1 IN2 IN
OUTPUT 2 OUT1 OUT
AND IN1 IN2 temp
PASS temp1 OUT
OR IN3 temp1 OUT
This circuit demonstrates the user ofMULTIPLEXER:
INPUT 3 A B C
OUTPUT 1 Z
MULTIPLEXER 3 0 0 0 1 1 0 1 1 A B C Z
As shown in class, this can be re-written to use a 4:1 multiplexer:
INPUT 3 A B C
OUTPUT 1 Z
NOT C NC
MULTIPLEXER 2 0 C NC 1 A B Z
An equivalent circuit can be made using a 3:8 decoder:
INPUT 3 A B C
OUTPUT 1 Z
DECODER 3 A B C _ _ _ p q _ r s
OR p q t
OR r s u
OR t u Z
Note the use of_for discarded outputs from the decoder.
4 Implementation suggestions
There are many ways to designtruthtable, but the most efficient way is to create a Data structure that represents a circuit. Your program will read the circuit description file, create the corresponding data structure, and then use that structure to determine the output values for each combination of inputs. Students commonly try to build the entire truth table before printing it. This is not the best strategy, because the truth tables grow exponentially with the number of inputs. (For example, test 1.10 will produce a truth table with 220 = 1 048 576rows.) A better design is to generate and print the table one row at a time. A few tips for creating fast implementations oftruthtable.
- When reading the circuit description file, assign a number to each new variable name and use a linked list or other structure to maintain a table that you can use to look up the number assigned to previously seen variables. Internally, refer to variables by number rather than name: integer comparisons are faster than string comparisons, and you can use variable numbers as array indices.
- Carefully consider what information you need to represent a circuit. This will likely include the circuits input and outputs and the gates making up the circuit.
- Carefully consider what data is needed to represent a gate. Design a structure that is general enough to represent any gate, and then write code that can handle any of the gates. This will likely include a code that indicates the type of gate and the input and output variables. See fig. 1 for one possibility.
- In order to handle DECODER and MULTIPLEXER, your gates will need to work with a variable number of inputs and outputs. One possibility is to use an array of variable numbers representing the inputs and outputs along with a field indicating the size of the gate. For fixed-sized gates, such as AND, this number can simply be ignored and the array can be assumed to contain the correct number of inputs and outputs. For MULTIPLEXER and DECODER, one number is sufficient to determine how many inputs and outputs there are.
- To generate a single row of the truth table, first assign values to the circuit inputs. Then, for each gate, determine the values for its outputs based on the values of its inputs. Once every gate has been handled, you will know the values for the outputs and can print the table row. If you have assigned a unique number to each variable, then you can use an array to hold the values of all the variables.
typedef enum { AND, OR, NAND, NOR, XOR, NOT, PASS, DECODER, MULTIPLEXER } kind_t;
struct gate { kind_t kind; int size; // indicates size of DECODER and MULTIPLEXER int *params; // length determined by kind and size; // includes inputs and outputs, indicated by variable numbers };
Figure 1: One possible data structure representing a logic gate
- For each row of the truth table, note that every input value will be followed by a space, and every output value will be preceded by a space.
- When reading the circuit description, you may assume that the file is correctly formatted. Thus, after reading a directive name, you may assume that it will be followed by the correct number of parameters. Thus, it is acceptable to use the whitespace-skipping tokenizer and ignore line breaks.
- When using a format string such as" %16s"withfscanf(), the corresponding variable must be the address of an array containing a sufficient number of characters (17, in this case). While it is fine to use local variable to hold the result fromfscanf(), be sure to make a copy of the string if you intend to hold onto it.
- There are several methods for dealing with circuit descriptions where the gates are not given in order. One way is easy to write, but slow. Another is more complicated, but fast. (Hint: the circuit can be thought of as a directed, acyclic graph, and you have learned an Algorithm for ordering the nodes in a DAG.)
5 Submission
Your solution to the assignment will be submitted through Sakai. You will submit a Tar archive file containing the source code and makefiles for your project. Your archive should not include any compiled code or object files. The remainder of this section describes the directory structure, the requirements for your makefiles, how to create the archive, how to use the provided auto-grader, and how to create your own test files to supplement the auto-grader.
5.1 Quick start
These steps will unpack the auto-grader archive, set up yoursrcdirectory and make file, and use the auto-grader to create thebuilddirectory. The auto-grader is flexible and many of these steps can be customized. See the remainder of this section for more in-depth explanations. Unpacking the auto-grader archive will create a directorypa4containing the auto-grader and associated test data. First, move to the directory you want to contain thepa4directory and unpack
the archive. You can move the archive to this directory first, or simply give a path to its location.
E.g.,
$ tar -xf ~/Downloads/pa4-grader.tar
Next, move into thepa4directory and set up yoursrcandbuilddirectories.
$ cd pa
pa4$ mkdir src
pa4$ cp template.mk src/Makefile
pa4$ ./grader.py --init
Write your code in a filesrc/truthtable.cusing your editor of choice.
pa4$ vim src/truthtable.c
Compile in thebuilddirectory usingmake.
pa4$ cd build
pa4/build$ make
gcc -g -std=c99 -Wall -Wvla -Werror -fsanitize=address,undefined
../src/truthtable.c -o truthtable
pa4/build$ ./truthtable my_circuit.txt
If you are repeatedly compiling and testing with a specific test file, you can combine both steps
into a single command using&&.
pa4/build$ make && ./truthtable test_circuit
This works well in combination with the up-arrow key (used to repeat earlier commands).
5.2 Directory structure
Your project should be stored in a directory namedsrc, which will contain (1) a makefile, and (2)
any source files needed to compile your program. Typically, you will provide a single C file named
for the program (truthtable.c).
This diagram shows the layout of a typical project:
src +- Makefile +- truthtable.c
Note that your code and makefile go directly insrc, without any subdirectories.
5.3 Makefiles
We will usemaketo manage compilation. Yoursrcdirectory will contain a file namedMakefile
that describes at least two targets. The first target must compile the program. An additional
target,clean, must delete any files created when compiling the program (typically just the compiled
program).
For reference, this makefile is provided with the auto-grader in the filetemplate.mk:
TARGET = truthtable
CC = gcc
CFLAGS = -g -std=c99 -Wall -Wvla -Werror -fsanitize=address,undefined
$(TARGET): $(TARGET).c
$(CC) $(CFLAGS) $^ -o $@
clean:
rm -f $(TARGET) *.o *.a *.dylib *.dSYM
You may move this file to your source directory and rename itMakefile. Note that the command for compilingtruthtableuses warnings and includes AddressSanitizer and UBSan. Your score may be reduced if your makefile does not include these options. Use of-gis recommended, but not required. If you prefer to name your source code file something other thantruthtable.c, simply replace $(TARGET).cwith your preferred name. Use of multiple source files is permitted, but contact me for tips first. You are free to design your own makefile, but be sure to use the variables$^or$<to refer to your source files so that make can find your source files. Contact me if you have trouble getting your makefile to work. Note that the makefile format requires that lines be indented using a single tab, not spaces.Be aware that copying and pasting text from this document will helpfully convert the indentation to spaces. You will need to replace them with tabs (literal tab characters), or simply type the makefile yourself. You are advised to use make when compiling your program, as this will ensure (1) that your makefile works, and (2) that you are testing your program with the same compiler options that the auto-grader will use.
5.4 Creating the archive
We will usetarto create the archive file. While in the directory containingsrc, execute this command:
pa4$ tar -czvf pa4.tar src/Makefile src/truthtable.c
tarwill create a filepa4.tarthat contains your makefile and source code. (If you are using multiple source files, or have re-named your source code, you will need to adjust this command accordingly.) This file can now be submitted through Sakai. To verify that the archive contains the necessary files, you can print a list of the files contained in the archive with this command:
pa4$ tar -tf pa4.tar
You should also use the auto-grader to confirm that your archive is correctly structured.
pa4$ ./grader.py -a pa4.tar
5.5 Using the auto-grader
We have provided a tool for checking the correctness of your project. The auto-grader will compile
your programs and execute them several times with different arguments, comparing the results
against the expected results.
Setup The auto-grader is distributed as an archive filepa4_grader.tar. To unpack the archive,
move the archive to a directory and use this command:
$ tar -xf pa4_grader.tar
This will create a directorypa4containing the auto-grader itself,grader.py, a libraryautograde.py,
abd a directory of test casesdata.
Do not modify any of the files provided by the auto-grader. Doing so may prevent the auto-grader
from correctly assessing your program.
Usage While in the same directory asgrader.pyandsrc, use this command:
pa4$ ./grader.py
The auto-grader will create a directorybuild, and compile your program using the make file and
source code insrc, placing compiler outputs inbuild.
During development, you may prefer to use the--stopor-1option, which produces more
program output but stops after the first failed test case.
pa4$ ./grader.py -
The tests for this assignment come in two groups, for normal and extra credit. To test only a
single part, include an argumenttruthtable:1ortruthtable:2.
To obtain usage information, use the-hoption.
Program output By default, the auto-grader will not print the output from your programs, except for lines that are incorrect. To see all program output for all unsuccessful tests, use the –verboseor-voption:
pa4$ ./grader.py -v
To see program output for all tests, use-vv. To see no program output, use-q.
Checking your archive We recommend that you use the auto-grader to check an archive
before submitting. To do this, use the--archiveor-aoption with the archive file name. For
example,
pa4$ ./grader.py -a pa4.tar
This will unpack the archive into a temporary directory, grade the programs, and then delete the
temporary directory.
Specifying source directory If yoursrcdirectory is not located in the same directory as
grader.py, you may specify it using the--srcor-soption. For example,
pa4$ ./grader.py -s ../path/to/src