Math
211
Final
Exam
Name
__________________________
Wednesday, Dec.
17,
200 pts.
I. Logic and proof
1. (10
pts.) Let p stand for the statement “we
go for a walk” and let q stand for the statement “it is sunny outside”. Translate the following into logical form
(using p, q, and logical connectives):
if
it is sunny we go for a walk
we
go for a walk only if it is sunny
it
is sunny, but we do not go for a walk
2. (10
pts.) In the statement
Which
condition is
necessary
sufficient
3. (10
pts.) Using
S(x)
– x is a supplier
P(x)
– x is a part
R(x)
– x is red
SP(x,
y) x supplies y
Translate
into ordinary English (i.e., not simply a transliteration)
4. (5
pts.) Simplify
not
((x>y) and (a >= b))
so
that not does not appear
II. Algorithms,
functions, and asymptotic behavior
1. (5
pts.) Give a brief definition of an algorithm
2. (10
pts.) Suppose that f is a function
from set A to set B (f:A->B). What
does it mean to say that
f
is 1-1 (one-to-one)?
f
is onto?
3. (10
pts.) Give a formal definition of what
it means to say that f is O(g)
4. (5
pts.) You are asked to choose between
two sorting algorithms. One is O(n2), and the other is O(n*log(n)) (both on
average). Which one do you pick, and
why? What if n is small?
5. (10
pts.) Find witnesses to demonstrate
that x4+2x3+1 is O(x4).
III. Number
theory (with some incorporated material on relations)
1. (10
pts.) Consider the integers mod 3. We define
[k]
= {n in Z (the integers) | n ≡ k mod 3}
a. Why are there only three distinct such sets
([0], [1], [2])
b. We can define addition and multiplication on
these three sets as follows:
[j]
+ [k] = [j+k]
[j]
* [k] = [j*k] (as in a lecture past)
complete
the following addition and multiplication tables using only [0], [1], and [2]:
|
+ |
[0] |
[1] |
[2] |
|
[0] |
|
|
|
|
[1] |
|
[2] |
|
|
[2] |
|
[0] (since
1+2≡0 mod 3) |
|
|
* |
[0] |
[1] |
[2] |
|
[0] |
|
|
|
|
[1] |
[0] |
|
|
|
[2] |
|
|
|
2. (10
pts.)
a. Define a|b (evenly divides)
b. Show that the integers are partially ordered
by ‘|’ (i.e., show that the relation a|b satisfies the three requirements of a
partial order where a and b are integers.
IV. Proofs
1. (10 pts.) Prove that 
using mathematical
induction. Describe each step.
2. (10 pts.) Prove
that 
where fk is the kth Fibonacci number (f0=0, f1=1, f2=1,
f3=2, f4=3, ...). Describe
each step.
V. Counting
and probability
1. (5
pts.) Evaluate C(5, 2) to a number. Show work (some calculators have this as a
function, so just a number is not enough).
2. (10
pts.)
In
how many ways can you throw a 6 using a pair of fair dice?
What
is the probability of doing so?
3. (10
pts.)
How
many ways can you draw a five-card hand from a deck of 52 cards so that the
hand contains at least one ace?
What
is the probability of doing so?
4. (10
pts.) In how many ways can you place 10
indistinguishable marbles into four boxes?
VI Relations
(10 pts.)
a. Define mathematically what a relation is
between sets A and B
b. A table SP
in a relational database contains rows with a supplier number and a part
number. That is, each row contains
something from S#_DOM followed by something from P#_DOM. An entry (S3, P7) in the table indicates that
supplier S3 supplies part P7. How can we
consider this a relation?
VII. Graphs
1. (10
pts.) Sketch the graph resulting from
the following incidence matrix:
2. (10
pts.) Consider the following binary
tree:
a. Identify
(write below) the root (letter)
b. Identify
a leaf
c. Identify
a sibling of node B
d. Write
the nodes as they would appear in an inorder traversal of the tree.
3. (10
pts.) Use Dijkstra’s algorithm to find
a shortest path between A and Z. Label
each node with the final L value of that node.
VIII.
History and famous problems (10 pts.)
Pick four of the following names of people and mathematical problems,
and say something about them. Clearly
indicate which person/problem you are describing.
a) René Descartes
b) Georg Cantor
c) The 3x+1 conjecture
d) Charles Dodgson
e)
f) The halting problem
g) Abu Ja’far Mohammed Ibn Musa Al-Khowarizmi
h) Donald Knuth
i)
Goldbach’s conjecture
j)
G.
Lejeune Dirichlet
k)
The
twin primes conjecture
l)
Pierre-Simon
Laplace
m)
Paul
Erdös