Functions, Sequences, Big-O
What is a sequence? Give an example of an explicitly defined sequence.
A sequence is a function from the set of natural numbers (sometimes including 0) to another set.
Example: {an}=n
Suppose we have two known integers, a and b. Explain the following division definition:
a = b*x + y
Specifically, what do the variables x and y represent?
x is the quotient and y is the remainder, such that 0<=y<b.
What are the three necessary components for all types of induction proofs? Describe each component.
Base case: Prove the statement is true for the smallest value of n (usually n=0 or 1, but subject to change).
Inductive assumption: Assume the statement is true for n=k.
Inductive step: Show the statement is true for n=k+1.
How many 6-element DNA sequences… (note: DNA elements can be either A, T, C, or G only)
Do not contain A?
End with CG?
1. 36 = 729
2. 44 = 256
Find the closest big-O bound for f(x) = 2x(3+x2). You do not need to find constants c and k (but you can if you want).
f(x) is O(x3).
What does (761)8 + (1001 0111)2 evaluate to in base 2?
(10 1000 1000)2
Describe the difference between PMI (principle of mathematical induction) and strong induction. Give an example of a scenario in which you would want to use strong induction over PMI.
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.
How many passwords of only made up of 8 lowercase english alphabet letters either start with "a" OR end with "xy" if letters can be repeated.
Just set the problem up!
267 + 266 – 265
Find the inverse function of f(x) = x3+1. Prove your solution is correct.
f-1(x) = (x – 1)1/3
f(f-1(x)) = x and f-1(f(x)) = x.
Evaluate the following:
(-136 mod 21 + 163 mod 21) mod 5
(11 + 16) mod 5 = 27 mod 5 = 2
Suppose we want to prove by PMI that 6 divides n3−n whenever n is a nonnegative integer.
Complete the base case and inductive assumption.
Base case: n=1; 13–1 = 0, 6*0 = 0. Thus by definition, 0 is divisible by 6.
Inductive assumption: Assume for n=k there exists an integer a such that k3–k=6a.
One hundred tickets, numbered 1, 2, 3, ... , 100, are sold to 100 different people for a drawing. Four different prizes are awarded, including a grand prize. How many ways are there to award the prizes if…
the person holding ticket 42 wins the grand prize?
the person holding ticket 42 wins one of the prizes?
1. the person holding ticket 42 wins the grand prize? C(1, 1) * P(99, 3) = 941,094
2. the person holding ticket 42 wins one of the prizes? C(4, 1) * P(99, 3) = 3,764,376
Determine if the following function is a bijection. You do not have to prove it, but this is good practice.
Let f be defined on the set of all real numbers such that f(x) = 2x+5.
The function is bijective.
Use the Euclidean algorithm to determine gcd(8924, 272).
gcd(8924, 272) = 4.
Suppose we want to prove by PMI that the following is true for all integers n>0. Complete the inductive assumption and inductive step (skip base case).
31+32+...+3n = (3n+1–3)/2.
Inductive assumption: Assume for n=k that 3+32+...+3k=(3k+1–3)/2 is true.
Inductive step: Show for n=k+1 that 3+32+...+3k+3k+1=(3k+2–3)/2 is true.
3+32+...+3k+3k+1 = (3k+1–3)/2 + 3k+1 = (3k+1–3)/2 + (2 *3k+1)/2 = (3*3k+1–3)/2 = (3k+2–3)/2. Proved by PMI.
I have 5 history books, 4 math books, and 8 novels. I want to put exactly 3 history books, 4 math books, and 5 novels on a shelf. I also want to keep the genres together on the shelf. How many ways can the shelf be arranged?
You do not need to evaluate, just set the problem up!
C(5, 3) * 3! * C(4, 4) * 4! * C(8, 5) * 5! * 3!
Find a solution (explicit formula) to the recurrence relation an=2n*an-1 with a0 = 1
an = 2n * n!
Multiply the following integers in base 8. Then, convert your solution to base 10.
(271)8 * (13)8
(271)8 * (13)8 = (3763)8 = (2035)10
Prove by strong induction that for all integers n>5, n can be expressed as a sum of 2s and 3s.
Base case: n=6 and n=7
Inductive assumption: Assume for n<=k that k can be represented by a sum of 2s and 3s s.t. k=2a+3b where a and b are integers.
Inductive step: show the statement is true for n=k+1.
n = k+1 = k–1+1+1 = (k–1) + 2 = 2a+3b+2 = 2(a+1)+3b. a and b are integers, so a+1 is also an integer.
There are 52 cards in a deck. How many ways can I get a six-card hand so that I have exactly two aces and exactly 3 spades?
You do not need to evaluate, just set the problem up!
C(3, 2) * C(12, 3) * C(36, 1) + C(1, 1) * C(3, 1) * C(12, 2) * C(36, 2).