This is an open-book, open-notes, open-computer, open-brain (your own only, please), and open-Internet exam. It is an exam, however, so limit your discussion of the exam to conversations with Jeff Ondich.

Explain your answers clearly.

This exam has been formatted in HTML, which is not especially good at displaying mathematical notation. Where appropriate, I have used C++ style notation (e.g. <= for less than or equal to, and &&, ||, and ! for logical And, Or, and Not, respectively). If you have questions about any of the notaion on this exam, please let me know.

1. A Little Logic (10 points)
   • Determine whether (P || !P) && !(P && !P) is a tautology. Prove your claim.

   • Translate the following sentence into as compact mathematical notation as possible: "There exists an x such that x is in the set A and the set B, but is not in the set C."

   • Negate the expression you wrote down for the previous question.

   • How do you go about disproving a conjecture of the form (P ==> Q)? That is, what do you need to do to show that (P ==> Q) is not true?

   • Elmo says to Zoe, "Elmo does not think that afternoon naps cause happiness. Elmo does not take afternoon naps, but Elmo is very happy!" Zoe rolls her eyes in disgust and walks away, leaving it to you to explain carefully the error in Elmo's use of propositional logic. Do so. (You may write your explanation on your exam paper, trusting me to convey your message to Elmo in due course.)

2. Inversions (12 points) Consider the sample space S4 consisting of all the permutations of the integers 1, 2, 3, and 4 (that is, you're going to imagine an experiment where you randomly pick a permutation, where all permutations are equally likely).

   An inversion in a permutation is a pair of integers where the left integer is larger than the right integer. For example, (1,3,4,2) has two inversions, because 3 is left of 2, and 4 is left of 2.

   Let A = {p in S4 | p has exactly 3 inversions}, let B = {p in S4 | the rightmost integer in p is 1}, and let X be the random variable on S4 defined by X(p) = the number of inversions in p.

   • Pr( A ) = ?
   • Pr( B ) = ?
   • Pr( A | B ) = ?
   • Pr( B | A ) = ?
   • E( X ) = ?
   • Answer the previous five questions for Sn (that is, where the permutations in question are of the integers 1 through n).

3. Height-balanced binary trees (12 points)

   A height-balanced binary tree (HBBT) is a binary tree, each of whose nodes has the following property: the height of the left subtree and the height of the right subtree differ by at most 1. (You have encountered this idea before if you have studied AVL trees, which are height-balanced binary search trees.)

   In this problem, you are going to work through a proof that the height of a HBBT is O( log N ), where N is the number of nodes in the tree. (We'll stop there, but your proof could be used to show that AVL trees have guaranteed insertion, deletion, and search times that are O( log N ).)

   • To get warmed up, draw examples of the smallest (i.e. fewest nodes) HBBTs of heights 1, 2, 3, and 4. For example, there are two smallest HBBTs of height 2, each of which has two nodes each, and you need only draw one of them.

   • Let N_h represent the smallest number of nodes that a HBBT of height h can have. What are N_1 and N_2?

   • Explain why N_h = N_(h-1) + N_(h-2) + 1 for all h > 2.

   • Let F_n be the nth Fibonacci number (where F_1 = F_2 = 1). Show that N_h = F_(h+2) - 1 for all h >= 1.

   • Give a closed form formula for N_h. (Note: you might find your textbook and the Fibonacci numbers handy for this step.)

   • Use the closed form formula for N_h to show that the height of a HBBT is O( log N ), where N is the number of nodes in the tree. Use the definition of Big Oh carefully here (see page 739 of your textbook).

4. Obligatory Foolishness (3 points) Please tell me a joke.

5. Gray Codes (12 points) Take the set of all 3-bit binary numbers {000, 001, ..., 111} and consider each to be a node of a graph G. Furthermore, suppose any pair of nodes in G will have a connecting edge if and only if the two numbers differ in exactly one bit (so 101 and 100 are connected, but 110 and 101 are not).
   • Draw G.

   • Does G have any Eulerian cycles? If so, show one, and if not, explain why not.

   • Does G have any Hamiltonian cycles? If so, show one, and if not, explain why not.

   • If, by chance, G were to have a Hamiltonian cycle, that cycle would be known as a Gray code, and would be a handy tool for designing stable digital logic circuits. How many different 3-bit Gray codes are there?

   • Answer the previous four questions for 4-bit binary numbers.

   • Are n-bit Gray codes guaranteed to exist? Why or why not?

6. Have a great summer.