CSE321 Final Exam December 11, , 1995

Answer any eight of the eleven questions. All questions count equally. Write each answer in the space provided.

1. Let p and q be propositional variables. Given that is false, determine the value of . Briefly explain you answer.

2. The Fibonacci numbers are defined by with the initial conditions . Let . Then . Prove: for all , .\

3. 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.

4. 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.

5. Let A be a array of zeros and ones, such that each row of A contains at least 6 ones.
   1. Prove that some column of A contains at least 6 ones;
   2. Prove that there exist two columns in A such that every row has a one in at least one of the two columns.

6. Let E, F and G be events in a probability space.Prove:

7. Let be the number of ordered triples of nonnegative integers such that x + y + z = n.
   1. Verify that .
   2. Prove that the generating function of the sequence is . Hint: .

8. Let STUDENTS be the set of students at a university, COURSES, the set of courses, GPAS, the set of possible grade-point averages, 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.

9. Let R be an equivalence relation (reflexive, symmetric and transitive) and, for any element x, let . Prove that the following three statements are equivalent:
   1. x R y;
   2. ;
   3. is not empty.

10. 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.

11. 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?

• About this document ...