Review Questions for the Final Exam
CS 280  Spring 2002
The Final Exam takes place at noon on Tuesday, May 14, in our regular classroom
(Olin 155). I will try to arrive early
so that we can start right at noon. Although the final exam will
be somewhat longer than the two prelims, I do not expect that you will need the entire 2.5 hours allotted
by the registrar for the final exam. The final exam is worth 30% of
your final grade; the homework is worth 30%; and the two prelims are each worth
20%.
The use of extra material is not permitted during the exam (i.e., no
textbook, no notes, no calculator, etc.).
The exam includes material from readings and lecture throughout the semester,
although the material covered since Prelim II will be stressed more heavily. See the Schedule for a list of topics
covered in lecture and for the corresponding readings. The exam will attempt to gauge your knowledge
and understanding of course concepts. You shouldn't need to memorize specific
code given in the text or in lecture.
The review questions given here are not meant to exhaust the possible topics
for exam questions. Consider reviewing the previous Review Questions,
Prelims I and II, the homework assignments, and
the appropriate sections of the text.
Most of these questions are from exams given in previous incarnations of
cs280.

 Determine which of the following propositions are tautologies.
Show why.
(p > (not p)) > (p > q)
[(p or q) > r] <> [(p > r) or (q > r)]
 Write down a proposition P over the variable p, q, r
such that P is false only when p, q, r have truth
values false, true, false or true, false,
false, respectively.
 Can such a proposition P be constructed using connectives and and
or only? If yes, do. Otherwise, show why not.

 Let L(x, y) be x loves y, b be Bob,
m be Mary. Give English language translations of the
following symbolic sentences (do not use variables in the answer).
(for all x) (there exists y) L(x,y)
(there exists x) L(x, b) > L(m, b)
(for all x) (L(x,m) > ¬L(b, x))
L(b,b) > ¬L(b, m)
 Which of the following sentences are logically equivalent? In
principle, you have to determine equivalence for all 6 pairs of
sentences.
(there exists x)(A(x) > B(x))
(there exists x)(A(x) > (for all y)A(y))
(for all x)A(x) > (there exists x)B(x)
(there exists x)B(x) or (for all y)¬B(y)
 Which of the following are true (A and B are arbitrary sets)? Yes/No
answers. The symbols for set operations are difficult in html, so the
notation here is odd.
 if A subset B and B={Ø} then A=B.
 if A subset B and B={Ø} then A=Ø.
 Ø elementOf A
 Ø subset A
 (A union B^{c})^{c} = B intersect A^{c}
 A intersect B = (A^{c} union B^{c})^{c}
 (A  B) intersect (B  A) = Ø
 if A x B = Ø then A=Ø and B=Ø
 A subset A x A
 A x A = A for some A

 How many onetoone functions from {a, b, c, d} onto {1, 2, 3, 4, 5}
are there?
 How many onetoone functions f from {1, 2, 3, 4, 5} onto
itself are there such that f = f ^{1}?
 Let f be function. Which of the following are true?
f(A intersect B) = f(A) intersect f(B)
f(A union B) = f(A) union f(B)
f ^{1}(C intersect D) = f ^{1}(C) intersect
f ^{1}(D)
f ^{1}(C union D) = f ^{1}(C) union
f ^{1}(D)
f(A) = f(A)
f ^{1}(C)
= f ^{1}(C)
 Yes/No answers. Is it true that n^{2} is O(g(n)) if g(n) is
 100n^{2} + 101n
 n^{3}
 n log n
 n^{2}log n
 n^{2} + log n

 Use the Euclidean Algorithm to find gcd(111, 2222).
 Find the inverse of 6 modulo 11.
 Find a positive integer x such that x = 3(mod 9) and x = 5(mod 10).

 Perform the following operations on binary numbers.
11011 + 10110 =
11011 * 10110 =
11011 / 10110 = (find a quotient and a remainder)
 Transform (11011)_{2} into decimal.
 How many bits can the binary expansion of a six decimal digit number
have?

 Determine which of the following propositions are tautologies. Show why.
(p → ¬q) → ( ¬q → p)
[(p or q) → r] ↔ [(p → r) and (q → r)]
 Write down a proposition P over the variables p, q, and r such that P is true only when p, q, r
have truth values FFT or TFT.
 Can such a P be constructed using the connectives and and → only (no truth constants for
T and F are allowed)? If yes, do so. Otherwise show why not.

 Let L(x, y) be x loves y. Write the following as formal sentences with quantifiers.
Everybody loves somebody.
Everybody loves everybody.
Somebody loves everyone.
Somebody loves someone.
 Which of the following sentences are logically equivalent (answer only)? In principle you
have to determine the equivalence of all 6 pairs of sentences. Assume B does not contain
x.
(for all x)(A(x) →B),
(for all x)A(x) →B,
(there exists x)(A(x) →B),
(there exists x)A(x) →B.
 Which of the following are always true (A, B, C are arbitrary sets)?
Yes/No answers.
if A subset B and B subset A then A = B
Ø elementOf {Ø}
Ø elementOf A
Ø subset A
if A != B and B != C then A != C
AB = (A^{c}  B^{c})^{c}
(A  B) intersect (B  A) = Ø
Ø x A = Ø
A x B = B x A
A union B = A
union B
 How many onetoone functions f from {1, 2, 3, 4, 5 }onto itself are there such that
f ◦f ◦f
is the identity function?
 YesNo answers. Is it true that n^{2} is O(g(n)), if g(n) is
n
n^{3}
n log n
2^{n}
n!
n^{2}log n
n^{2} + log n
n^{2} / log n
(n^{4} +1)/(n^{2} +1)
(n^{4} +1)/(n +1)
 Find 5^{20001} (mod 143). The answer should be a standard integer between 0 and 143.

 Perform the following operations on binary numbers:
1101 + 1011 =
1101 ·1011 =
1101/1011 = (find a quotient and a remainder)
 Transform (1101)_{2} into decimal.
 Transform (1101)_{10} into binary.

 Suppose that S(n) is a proposition involving a nonnegative integer n, and suppose that
if S(k) is true then so is S(k + 2). Which of the following are possible (answer only)?
S(n) holds for all n ≥0,
S(n) holds for all n ≥1, but S(0) is false,
S(n) is false for all n ≥0,
S(n) is true for all n ≤100 and false for all n >100,
S(n) is false for all n ≤100 and true for all n >100.
 A collection S of strings of characters is defined recursively by (1) the empty string is in
S and (2) if X belongs to S then so does aXb.
Which of the following belong to S (YesNo answers):
a
b
c
ab
abb
aabb

 A questionnaire is sent to 13 freshmen, 5 sophomores, 15 juniors, and 20 seniors. A
student won’t necessarily return his/her questionnaire. How many questionnaires must be
received to ensure getting 9 from the same class?
 How many bit strings are there of length 10 with two or more 1’s in the string?

 Find the number of positive integer solutions of x + y + z ≤100.
 A hostess wishes to invite 6 dinner guests. In how many ways can she place them on 6
distinguished seats?
 The same question for a round table with indistinguishable seats.
 Two fair dice are rolled. What is the probability that
 the number on the first die is strictly less than the number on the second die?
 one of those numbers is strictly less than the other one?
 the product of those numbers is even given that their sum equals 6 ?
 A couple agrees to keep having children until they have at least one boy and one girl, but
not more than 5 children. Assume that boys and girls are equiprobable and that the births
are mutually independent. What is the expected value and variance of the number of
 children ?
 girls ?
 An integer is randomly selected from 1 to 1000. What is the probability that it is divisible
by 2 or by 3 or by 5?
 Give an example of a relation R that is
 symmetric, not reflexive
 reflexive, symmetric, not transitive.

 How many vertices and edges does the graph Q_{5} have?
 A graph has 7 vertices, 3 of them of degree two and 4 of degree one. Is this graph connected?
Why?
 Which of the following graphs are planar? (Answer only)
K_{5}
Q_{3}
K_{2,5}
K_{3,5}
K_{4,5}

 Suppose that S(n) is a proposition involving a nonnegative integer
n, and that if S(k) is false for all k<n then so is S(n).
Which of the following are possible (answers only).
S(n) is false for all n.
There is an integer M > 0 such that S(n) is true for all n <
M and false for all n > M.
S(n) is true for all n.
There is an integer M > 0 such that S(n) is false for all n <
M and true for all n > M.
 A collection S of strings of characters is defined recursively by
(1) a belongs to S and (2) if Xa belongs to S then so do Xaa and Xb.
Which of the following belong to S?
b
aa
ab
abb
aab

 How many students must be in a class to guarantee at least k
students with the same birthday in the year 2000? Answer for
k=1, k=2, and k=3.
 A multiple choice exam has 20 questions, each with 5 possible
answers, and 7 additional questions, each with 3 possible
answers. How many different answer sheets are possible?

 In how many ways can a committee of 3 mathematicians and 5 computer
scientists be selected from a panel of 20 having 10 mathematicians and
12 computer scientists?
 Find the number of positive integer solutions of x + y <
100.

 Find the probability that a family with six children has a boy and a
girl (sexes of children are assumed equiprobable and independent).
 What is the most likely number of boys?
 Find the probability of having at least one girl given the first
three children are boys.
 A fair die is rolled until the sum of the spots exceeds 2. What
is the expected number of rolls?
 An integer is randomly selected from 1 to 100. What is the
probability that it is divisible by 2 or by 3, but not by 5?
 Give an example of a relation on {a, b, c} wich is
 reflexive, not symmetric
 irreflexive, symmetric
 reflexive, symmetric, not transitive

 Reorder the words in this phrase lexicographically.
 Find the smallest possible poset having exactly two minimal elements
and exactly three maximal elements. Does it have a greatest
element and a least element (answers only)?

 Indicate all possible vertex degrees occurring in the following
graphs: K_{3}, C_{17}, K_{3,5}, Q_{4}.
 Is there a simple graph with exactly 3 vertices of degree 3?
 Is there a simple graph with 10 vertices and 46 edges?
 Is there a connected graph with 100 vertices, 96 of them of degree
two and 4 of degree one?
 Which of the graphs in 32a are planar (answers only)?

 Represent
(p → ¬p) → ( p → q) using an ordered rooted tree.
 What is the prefix form of the expression (x  y)^{2}  (x +
y)^{2}?
 What is the value of the prefix expression  * 1 / 6 2 3?