CS 223
Final Exam
Ondich
Due on paper 5:00 PM Monday, June 4, 2001
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.
- 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.)
- 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).
- 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).
- Obligatory Foolishness (3 points)
Please tell me a joke.
- 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?
- Have a great summer.