EEL4837 Spring 2024 - Excursion 2 Due Date: April 29, 2024
1
EEL4837 Programming for Electrical Engineering II – Spring 2024
Excursion 2: Technology Mapping
Due Date: April 29, 2024
Submission Instructions
Submit your code to Gradescope. You need to submit the following files separately (not as an
archive):
1. One or several source code files.
● Your program should read an input file named input.txt located in the same
directory as your source code.
● Your output should be a single integer, which should be written to a file named
output.txt and located in the same directory.
2. A documentation named readme.txt.
● Explicitly indicate if you are claiming bonus points.
● (Optional) Any other descriptions of your program if you wish to provide.
Description
The goal is to implement an elementary tool for technology mapping, which will:
1. Transform the original logical expressions into a NAND-NOT tree;
2. Calculate the minimum cost of the transformed structure.
Input: a Boolean model specified in the format as shown in the Excursion 2 slides.
Output: a single integer, which is the calculated minimum cost of the transformed structure.
You may assume:
1. Each node of the input netlist is a single AND, OR, and NOT function.
2. In each test case, there will be one output node only. That is, your circuit will be a tree.
3. A Technology Library is available, which consists of the components listed in Table 1.
EEL4837 Spring 2024 - Excursion 2 Due Date: April 29, 2024
2
Table 1. Technology Library
Name Cost
NOT 2
NAND2 3
AND2 4
NOR2 6
OR2 4
AOI21 7
AOI22 7
Guidelines
1. Read a netlist as input. You can assume that all inputs are legal.
2. Parse the netlist to construct a tree based on the provided expressions.
3. Convert the tree into a NAND-NOT tree.
4. Refer to the Technology Library (Table 1) and recursively compute the minimum cost at
each node.
5. Write the final minimum cost to the output file.
Grading
Total points: 100
1. Automated grading (75 pts)
a. Correctness (60 pts): correct results for normal inputs.
b. Robustness (15 pts): correct results for edge cases, such as very simple and very
complex inputs.
2. Manual grading (25 pts)
a. Efficiency: The time and space complexities are decent. No brute force is
allowed.
EEL4837 Spring 2024 - Excursion 2 Due Date: April 29, 2024
3
b. Elegance: tidy code style, understandable comments for key steps as needed,
meaningful functions, etc.
3. Bonus points (20 pts): implement dynamic programming traversing the tree bottom-up
and saving the intermediate costs for subtrees.
Late Policies
● Late due date: May 3, 2024
● 5% off per late day. No further extension will be permitted due to the UF grading policy
regarding grade report at the end of each semester.
Notes
1. Your code should be in C++ only. We encourage splitting up your code into multiple
files/functions/classes.
2. Your program should compile and run successfully on both the ECE Linux server and
Gradescope.
3. You can only use C++ standard libraries (including STL). Do not use libraries that
implement circuits, trees, or graphs for you. If you are not sure whether a library is
allowed, please reach out to TA.
请加QQ:99515681 邮箱:99515681@qq.com WX:codinghelp
- 网易硬刚腾讯 两大游戏玩家之间的口水仗不断
- 全球“最独特”的一台华为 nova 6 5G 版手机是什么样子的?
- 拼多多抖音淘宝京东,谁是真低价?
- 老杨第一次再度抓握住一瓶水,他由此产生了新的憧憬
- 丰田章男称未来依然需要内燃机 已经启动电动机新项目
- B站更新决策机构名单:共有 29 名掌权管理者,包括陈睿、徐逸、李旎、樊欣等人
- 苹果罕见大降价,华为的压力给到了?
- 三明列东又有房子要拆迁!住这里的人要发了!
- 放大招后,广州又忍不住了…
- 私募积极加仓,百亿股票私募仓位指数创出近八周新高
- 他,传闻中马云最想见的人
- 升级的脉脉,正在以招聘业务铺开商业化版图
- 如何经营一家好企业,需要具备什么要素特点
- 智慧驱动 共创未来| 东芝硬盘创新数据存储技术
- 创意驱动增长,Adobe护城河够深吗?