Next: About this document
CSE321 Final Exam December 11, , 1995
Answer any eight of the eleven questions. All questions count
equally. Write each answer in the space provided.
- Let p and q be propositional variables. Given that is false, determine the value of . Briefly explain you answer.
- The Fibonacci numbers are defined by
with the initial conditions . Let . Then . Prove: for all ,
- How many strings can be formed by permuting the letters of the
word AARDVAARK? Clarification: each string must be of length nine
and contain four As, two Rs, one D, one V and one K.
- An urn contains four red balls and two green balls. Consider the
experiment of repeatedly removing a random ball from the urn until a
red ball is removed. Once a ball has been removed it is not put back
in the urn. Let the random variable X denote the number of balls
removed during this experiment. Determine the expected value of X.
- Let A be a array of zeros and ones, such that
each row of A contains at least 6 ones.
- Prove that some column of A contains at least 6
- Prove that there exist two columns in A such that every row
has a one in at least one of the two columns.
- Let E, F and G be events in a probability space.Prove:
- Let be the number of ordered triples of
nonnegative integers such that x + y + z = n.
- Verify that .
- Prove that the generating function of the sequence is
. Hint: .
- Let STUDENTS be the set of students at a university, COURSES, the
set of courses, GPAS, the set of possible grade-point
and YEARS the set of possible years in which a student might have
entered the university. A database has three relations:
, , and . An ordered
pair is in if student s is taking course c; an
ordered pair is in if student s entered in year
y. An ordered pair is in if student s has
grade-point average g. Using the operations on relations that we
have defined, give a sequence of operations that produces a list of
those courses that are being taken by at least one student who
entered in 1992 and
has a grade-point average greater than 3.5.
- Let R be an equivalence relation (reflexive, symmetric and transitive)
and, for any element x, let . Prove that the
following three statements are equivalent:
- x R y;
- is not empty.
- Let G be a connected multigraph with at least one edge. Let
E be the edge set of G. Prove:
G has a circuit that covers each edge in E exactly twice.
- A planar simple graph G has six vertices, each of which is of degree
four. How many regions are there in a planar representation of G?
Next: About this document
Fri Dec 15 17:03:40 PST 1995