Ch. 1 & 2
Ch. 3 & 4
Ch. 5 & 8
Ch. 6 & 7
Ch. 9 & 10
200
Let A = {a, b, c, d, e}. Determine...
a. |A|
b. how many unique subsets does A have?
a. 5
b. 32
200
What does (761)8 + (1001 0111)2 evaluate to in base 2? Also, convert this to base 16.
(10 1000 1000)2 = (288)16
200
What are the three necessary components for all types of induction proofs? What is the difference between PMI and strong induction?
Components: base case, inductive assumption, inductive step.
For PMI, in our inductive assumption, we assume the statement is true for n=k. For strong induction, in our inductive assumption, we assume the statement is true for n<=k.
200
My sock drawer contains 14 pairs of socks. 6 of these pairs are white, 4 pairs are black, and the remaining pairs are blue. None of my socks are paired in the drawer.
1. How many socks do I have to take out to ensure I get at least two that match?
2. How many socks do I have to take out to ensure I get at least two blue socks?
1. 4
2. 22
200
Let A = {1, 2, 3, 4} and R be a relation on A such that R = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}. Represent R as a graph. Then, determine which properties R satisfies.
R is antisymmetric and transitive.
400
Determine if (¬p → (q → r)) is logically equivalent to ((¬q ∨ r) → p). Must show work to get points!
No, they are not logically equivalent because the bicondition of (¬p → (q → r)) and ((¬q ∨ r) → p) is not a tautology.
400
Evaluate the following:
(-124 mod 17 + 75 mod 17) mod 6
(12 + 7) mod 6 = 19 mod 6 =1
400
Determine if the sequence an = -n + 2 is a solution to the recurrence relation an = an-1 + 2an-2 + 2n – 9.
You must show your work to win points!
an = -n + 2 is a solution.
400
Consider a 7-sided die that is biased so that 4 and 5 are rolled twice as often as each of the other numbers. What is the expected value if we roll this die once?
37/9
400
Determine if the following graph is bipartite. If it is, determine an appropriate partition of the vertices.
Bipartite with partition (V1 , V2) s.t. V1 = {a, b, d, e} and V2 = {c, f}
600
Determine if the following function is a bijection. If your answer is yes, prove it.
Let f be defined on the set of all real numbers. Then, f(x) = 2x3 + 3.
The function is bijective!
600
Find the closest big-O bound for f(x) = 2x(3+x2). Also find constants c and k.
f(x) is O(x3). Notice that c and k are not unique. A solution that works is c=3 and k=3
600
Prove by PMI: 52n – 1 is divisible by 8 for all n>0.
Base case: n=1. 52 – 1 = 24 = 3*8
Inductive assumption: Assume for n=k that 52k – 1 is divisible by 8 (or = 8x for some integer x).
Inductive step: Prove for n=k+1.
600
How many passwords of only made up of 6 lowercase english alphabet letters either start with "z" and contain "a"? Note: letters can be repeated.
Just set the problem up!
265 – 255
600
Determine if the following graphs are isomorphic. If they are, determine an appropriate isomorphism function.
The graphs are isomorphic. One solution is f(u1)=v1, f(u2)=v3, f(u3)=v5, f(u4)=v7, f(u5)=v2, f(u6)=v4, and f(u7)=v6.
800
Prove or disprove the following statement:
If x+y is irrational, then x is irrational or y is irrational.
Proof by contrapositive.
800
Multiply the following integers in base 16. Then, convert your solution to base 10.
(A7F4)16 * (13)16
(A7F4)16 * (13)16 = (C771C)16 = (816 924)10
800
Find a solution to the following linear recurrence relation with the given initial conditions. Then, prove your solution using induction.
an+2 = −4an+1 + 5an for n≥0, a0=2, a1=8
an = 3 – (-5)n
800
There are 52 cards in a deck. What is the probability I get a six-card hand so that I have at least one ace and exactly 2 hearts?
*You do not need to evaluate, just set the problem up!
(C(1, 1)*C(12, 1)*C(39, 4) + C(3, 1)*C(13, 2)*C(38, 3)) / C(52, 6)
800
Let S be the Cartesian coordinate plane ℝ x ℝ and define a relation R on S by R = {((a,b), (c,d) | a+d = b+c}. Determine which property/properties the defined relation satisfies. Justify your claims!
The relation is an equivalence relation (reflexive, symmetric, and transitive).