ece473 fn sp2013.pdf-EE473 Final Exam Pu...
ece473_fn_sp2013.pdf-EE473 Final Exam Purdue University Spring
Showing 1-7 out of 35
ece473 fn sp2013.pdf-EE473 Final Ex...
ece473_fn_sp2013.pdf-EE473 Final Exam Purdue University Spring
##### Page 1
EE473 Final Exam
Purdue University
Spring 2013
There are 6 questions in this ﬁnal exam. You are to answer 3 out of the 6 questions. Indicate below which 3
questions you wish to have graded. If you do not indicate exactly 3 questions, we will not grade your exam.
The 3 questions that you choose to have graded are equally weighted. All of your solutions must be written
on the exam handout and no other handins will be accepted or graded. We have a supply of extra exams,
thus if you want more space to write your solution, raise your hand and ask for another copy of the exam.
We will only grade one solution per problem per student.
If in the process of writing your solution you
explore alternate approaches, you must clearly cross out the portion of your solution that you do not wish
to be graded. All of the copies of this exam that you received should be returned to the proctor at the end
of this exam. No copies of this exam may be removed from the exam room by students. All exams handed
in must have the student’s name, PUID, and ECN userid indicated below or they will not be graded. Good
luck and have fun!.
Circle the
three
questions you wish to have graded: 1 2 3 4 5 6.
Name:
PUID:
ECN userid:
1

##### Page 2
Problem 1:
Part A:
Write an
inductive
deﬁnition of a function
all-subsets
that takes a set of numbers as input, represented
as a list, and returns the set of all subsets of that list of numbers, as output, represented as a list of lists.
Part B:
Write an
inductive
deﬁnition of a function
all-permutations
that takes a list of numbers as input, and
returns the set of all permutations of that list of numbers, as output, represented as a list of lists.
You are to formulate the deﬁnitions for both parts A and B in the style that we have been using throughout
the semester, that is as a
functional
deﬁnition without assignment statements or any form of variable or
English
and mathematical notation. Do
Scheme
.
2

##### Page 7
Problem 2:
In digital circuit design, we often wish to ﬁnd the smallest circuit that computes a given
Boolean function.
Assume you are given a Boolean function, speciﬁed by a truth table, that computes a
single Boolean output from
n
Boolean inputs. You wish to ﬁnd the circuit, composed solely out of two-input
NAND gates, that is built out of the minimal number of such gates, that implements the speciﬁed Boolean
function. Describe a nondeterministic algorithm that searches that space of circuits to ﬁnd the smallest one
that implements a speciﬁed target Boolean function. Write your answer in a combination of
English
and
Scheme
. Note that we do not restrict the circuit to be
in sum-of-products or product-of-sums form thus the methods that you have learned, like Karnaugh Maps,
are not applicable.
Hint: one way to approach this problem is to consider digital circuits to be represented as expressions in
an extremely small
Scheme
-like language containing only Boolean-valued variables, a procedure
nand
, and
the syntax
let
to handle fanout. For example, the following contains fanout of the output of
(nand a b)
:
(let ((x (nand a b))) (nand x x))
.
7

Browse thousands of Study Materials & Solutions from your Favorite Schools
Purdue University-Main Ca...
Purdue_University-Main_Campus
School:
INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades