Programming Assignment #3: Binary Decision Diagram (BDD)
Programming Assignment #3 Binary Decision Diagram (BDD)
Lab 3 Introduction
- To exercise the concept of binary decision diagram.
- To understand the ordering effects of BDD.
- Problem Description Please construct BDDs with given variable orderings, and find the minimum number of nodes required from the given variable orderings.
Input
Boolean equation.
Variable ordering 1.
Variable ordering 2.
…
Variable ordering n.The first line specifies the Boolean equation, while the following lines give the various variable orderings. Each equation ends up with a period and every variable is represented by exactly one character (i.e., 26 variables at most). The Boolean equation is given i n sum -of-product (SOP) form: lowercase character represents a plain variable, whereas its uppercase counterpart is for its complement (~e represents as E) .
Input example
ab+cd.
acbd. // First is variable ‘a’, then ‘c’ …
abcd. // First is variable ‘a’, then ‘b’ …Output Output the minimum number of nodes required to represent the given BDD from the given variable orderings.
6 // Minimum number of nodes required is 6, as the following figureCompile & Execute Compile command : $ make Execute command : $ ./Lab3 [input file] [output file] e.g. $ ./Lab3 case2.txt out2.txt
Note that input and output file should be the arguments of program. Your executable binary file after “make” should be named as “ Lab3 ” (Hint: add “ -o Lab3” in your compilation command). Please make sure your code can be compiled and executed. If it cannot be executed, you will get zero point!
Program Submission
- Please use the C/C++ langage, and write your own code.
- The materials of CUDD package is provided, which is optionally used in your program.
- Please upload the following materials in a “zip” file to New E3 by the deadline. Name the zip file as: Student_ID.zip. (e.g. 0610128.zip)
- Source code • (.c, .cpp, .h).
- Makefile.
- A readme file • (Describe your compile and execution information).
- cudd -3.0.0/ • (If you use it, please upload . • Make sure your cudd path is working by " make ")
- Don’t print any words on the terminal. Grading
◼ Case1 20% ◼ Case2 20% ◼ Case3 20% ◼ Case4 (hidden) 20% ◼ Case5 (hidden) 10% ◼ Case6 (hidden) 10%
- Time limit is 300s. Otherwise, the case is regarded as failed. Notices ⚫ Please make sure your code is available on our Linux server . If it cannot be executed, you will get zero point. ⚫ Accept four days late submission, 10% deduction per day. ⚫ Plagiarism is strictly forbidden. 0 grade guarantee
