MATH 211 Final, Spring 2007
American University of Beirut · Discrete Structures · 8 pages
More MATH 211 files
Show the text of this final exam
AMERICAN UNIVERSITY OF BEIRUT
Faculty of Arts and Sciences
Mathematics Department
MATH 211
FINAL EXAMINATION
SPRING 2007
Closed Book, 2 HOURS
WRITE YOUR ANSWERS ON THE QUESTION SHEET
STUDENT NAME
ID NUMBER
Problem
Out of
Grade
1
5
2
10
3
10
4
10
5
15
6
10
7
10
TOTAL
70
1
1. (5 points) Express this statement using quantifiers on specific universe of discourses :
“There is exactly one student in this class who has taken exactly one mathematics
course at this school”.
2
2. (10 points) Let Xn = {x1, x2, ..., xn} be a set of n objects forming the universe of
discourse for the propositional functions (predicates) P(x) and Q(x). Prove by (soft)
mathematical induction that :
∃x ∈ Xn, (P(x) → Q(x)) and (∀x ∈ Xn, P(x)) → (∃x ∈ Xn, Q(x))
are logically equivalent.
Specify the base and inductive steps. (Hint : Use the equivalence p → q ≡ ¬p ∨ q.)
3
3. (10 points) Prove that for all x ∈ R :
⌊⌊x/2)⌋ /2⌋ = ⌊x/4⌋
Hint : use x/4 = ⌊x/4⌋ + α.
4
4. (10 points) In what follows, a, b, c and m are integers with m > 1.
(a) (5 points) Prove or disprove the following statement : If ac ≡ bc(mod m), then
a ≡ b(mod m).
(b) (5 points) Show that if ac ≡ bc(mod m), then a ≡ b(mod (m/d)), where
d = gcd(m, c).
5
5. (15 points) Consider the recurrence relation :
an = a3
n−1a2
n−2, with a0 = 2 and a1 = 2
(1)
(a) (3 points) Use logarithms to change (1) into a linear recurrence relation for (bn =
log2(an)). Find such recurrence relation for {bn} :
........................................................
(2)
(b) (8 points) Solve (2) and find the expressions of bn and an.
(c) (4 points) Find functions f(n) and g(n) such that bn = Θ(g(n)) and an = Θ(f(n)).
6
6. (10 points)
(a) (5 points) How many strings of length 10 over the alphabet {a, b, c} have exactly
3 a’s or exactly 4 b’s ?
(b) (5 points) There are 12 signs in the zodiac. How many people are needed to
guarantee that at least six of these people have the same sign ?
7
7. (10 points) Given a sequence of n + 1, (n ≥ 1) real numbers {a(0), a(1), ..., a(n)} and
a real number c, consider the following algorithm :
p :=a(0) t :=c
for i from 1 to n {,i.e. i=1,2,...,n-1,n}
p=p+a(i)*t
t=c*t
end
(a) (3 points) Check which function p(c) is computed for n = 3, 2, 1 ?
(b) (5 points) Give f(n) the number of artithmetic operations needed to execute this
algorithm.
(c) (2 points) Give a and α in f(n) = Θ(a × nα).
8