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?
(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 A ≤ i ≤ k (where A is determined by base case).
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.
How many socks do I have to take out to ensure I get at least 2 white socks?
18 socks
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 = 3n–4 is a solution to the recurrence relation:
an = 2an−1 − an−2 + 3n − 7.
an = 3n–4 is NOT a solution.
400
Find the coefficient of x18y2 in the expansion of:
(2x3 – 4y2)7
C(7, 1) * 26 * (-4)1
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.
Let f be defined on the set of all real numbers. Then, f(x) = 2x + 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
Find a solution to the following linear recurrence relation with the given initial conditions.
an = −4an-1 + 5an-2 for n≥2, a0=2, a1=8
an = 3 – (-5)n
600
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
600
Find an Euler path and/or an Euler circuit if they exist in the following graph:
V={A, B, C, D, E, F, G}
E={AB, AC, AD, BE, CE, DF, EF, FG, EG}
Euler path: A, C, E, G, F, E, B, A, D, F
*Notice this solution is not unique!
Euler circuit: DNE
800
Let our domain be the set of integers. Define the predicate P(x,y) by P(x,y): x > y. Identify the truth value of the following statement. Then, negate the statement and determine its truth value.
∃y∀x P(x,y)
∃y∀x P(x,y) is False
Negated: ∀y∃x ¬P(x,y) is True
800
Convert (5176)8 to binary and decimal.
(5176)8 = (1010 0111 1110)2 = (2 686)10
800
Prove an = 3 – (-5)n that is a solution to the linear recurrence relation an = −4an-1 + 5an-2 when a0=2 and a1=8 using induction.
BC: a0 = 3 – (-5)0 = 2 and a1 = 3 - (-5)1 = 8
IA: Assume for 2≤i≤k that ak = −4ak-1 + 5ak-2 = 3 – (-5)k
IS: Prove for n = k+1 that ak+1 = 3 – (-5)k+1
800
How many passwords only made up of 6 lowercase english alphabet letters start with "z" and contain "a"? Note: letters can be repeated.
Just set the problem up!
265 – 255
800
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.
1000
Prove or disprove the following statement:
If x+y is irrational, then x is irrational or y is irrational.
Proof by contrapositive or contradiction.
1000
Multiply the following integers in base 16.
(A75)16 * (13)16
(A75)16 * (13)16 = (C6AF)16
1000
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. That is, 52k – 1=8x for some integer x.
Inductive step: Prove for n=k+1.
1000
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(13,2)*C(39,4) – C(12,2)*C(36,4)] / C(52,6)
1000
Let A = {1, 2, 3, 4, 5}. Let R be a relation on A such that...
R = {(1,2), (2,4), (2,5), (3,2), (4,3)}
Determine the transitive closure of R.
RT = R ∪ {(1,3), (1,4), (1,5), (2,2), (2,3), (3,3), (3,4), (3,5), (4,2), (4,4), (4,5)}