


ece473 fn sp2013.pdf
ece473_fn_sp2013.pdf
Showing 17 out of 35
ece473 fn sp2013.pdfEE473 Final Exam Purdue Unive...
ece473_fn_sp2013.pdfEE473 Final Exam Purdue University Spring
ece473 fn sp2013.pdfEE473 Final Ex...
ece473_fn_sp2013.pdfEE473 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
allsubsets
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
allpermutations
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
data structure mutation. Write your answers in a combination of
English
and mathematical notation. Do
not write your answers in
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 twoinput
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
mathematical notation. Do not write your answer in
Scheme
. Note that we do not restrict the circuit to be
in sumofproducts or productofsums 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 Booleanvalued 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
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Purdue UniversityMain Ca...
Purdue_UniversityMain_Campus
School:
INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE
Course:
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
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106