CMSC250 Final Exam Study Guide
December 11, 2021
Contents
1 Intro 1
2 Topics 1
2.1 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.2 Number Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Predicates & Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.4 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.5 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.6 Sequences, Series, Summations, Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.7 Countability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.8 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.9 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.10 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.11 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.12 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Tips 13
4 Answers to Sample Problems 14
5 Outro 20
1 Intro
Hello everyone! This document is a study guide, as the name suggests. The document contains a summary
of everything you have learned in this class. It’s crazy that one document can contain all of the information
you have spent 4 months studying, but here we are. This document should be one of your tools (but not the
only tool) to aid in your studying. Additionally, due to fluctuations over topics covered over the
last few semesters, this study guide may not include every little thing covered in the class,
but it definitely covers all the important parts. Read this document, read your notes, re-take your
old exams, find practice problems, do anything and everything (within reason) to set yourself up for success.
The final exam will be 100 points. You will have 120 minutes. The exam is in the AFTERNOON/EVENING
at 4:00pm. Since we want to give you the full 120 minutes, we would prefer if you arrive early so we can
pass out exams, make sure everything is good, etc. You WILL be given a table of logical equivalencies with
the names/associated equivalency. You WILL be given a list of assumptions you may make in your proofs.
Please, please, please do not make any big assumptions that we may have proved in class. If you are ever
confused if you can use something in your proof, step 1 is to check the provided assumed facts, and step 2
is to raise your hand and ask a TA during the exam.
The TAs use gradescope to grade your exam. We do this as a convenience for both us and you. We can
grade your exams significantly faster using gradescope, so you get your exam scores back faster, AND it’s
easier for you to submit re-grade requests. It’s a win-win, but it comes with some necessary evils. You must
write your name NEATLY. Write your first and last name, in that order, directly as it appears on elms.
Write your UID neatly. I can’t iterate enough how important it is to write your information as neatly as
possible. You can use your normal handwriting for the rest of the exam, but please please please just take
your time, slow down, and write your name, printed, as neatly as possible. Cool? Cool. For everything else,
just follow the exam question directions as closely as possible and you’ll be good to go. Thank you.
Okay, now for the fun part!
2 Topics
Everything you have learned in this class is spelled out in this section. These sub-sections should be in
roughly the same order that you learned each item. There were a lot of topics covered in this course. Each
subsection has a small intro, a list of terms, and a sample problem or two with solutions. Enjoy!
2.1 Logic
Logic, the American rapper, has some incredible songs. Logic was raised in Gaithersburg, Maryland, which
is like half an hour away from here. Logic has released three studio alb- oh, oh wait. Oh this isn’t. This is
the 250 study guide. Oh. Logic was the very first topic you learned in this class. Logic is innate to humans.
Everything in this topic should sort-of ‘make sense’ in your mind. All we do is take your intuition and write
out explicit rules. Here’s what you should know:
• Proposition – any statement that is exclusively either True or False.
• Logical Operators – (sometimes called ‘binary operators’) ∼,∧,∨,⇒,⇔. What are the truth
table values for p□q where □ can be any logical operator (i.e.: p ∧ q, p ⇒ q, …)? Don’t forget
the prescedence order for these operators (or just USE PARENTHESIS) – ∼ takes prescedence
over ∧ which takes prescedence over ∨ which takes prescedence over ⇒ which takes prescedence
over ⇔.
• Converse, Inverse, Contrapositive – Manipulations of the p ⇒ q statement
Converse of p ⇒ q is q ⇒ p. These are NOT equivalent.
Inverse of p ⇒ q is ∼p ⇒ ∼q. These are NOT equivalent.
Contrapositive of p → q is ∼q ⇒ ∼. These are equivalent. Additionally the inverse and
converse are contrapositivies of each other.
1
• Boolean Expressions – when we put propositions together using our logical operators. p ∧ q ∨ r
is a boolean expression.
• Truth Table – a table showing all possible inputs/outputs of a propositional statement. How
many rows are in a 1-variable table? 2-variable table? 3-variable table? n-variable table? How
do we quickly write all the input values?
• Tautology – a logical Truthhood. A boolean expression has a Tautology iff every input leads to
a True output.
• Contradiction – a logical Falsehood. A boolean expression has a Contradiction iff every input
leads to a False output.
• Logical Equivalencies/Axioms – the things we use to simplify boolean expressions (propositional
statements, whatever..). Commutativity, Associativity, Distributivity, Identity, Negation, Dou-
ble Negation, Idempotence, De Morgan’s, Universal Bound, Absorption. Those things. Also,
Equivalency between Implication and Disjunction, and Equivalency between bi-conditional and
Implication.
• Satisfiability – a boolean expression is satisfiable iff there exists at least one set of inputs that
make the boolean expression evaluate to True. p∧ q is satisfiable because the set of inputs p =
True and q = True make the expression output True (True ∧ True ≡ True).
• Circuits – AND ∧, OR ∨, NOT ∼ gates. Know the gates’ circuit symbols, and know their
corresponding logical operators.
Check out this page for the circuit symbols.
Sample Problem(s):
Q: Write out a truth table for [(p ∨ q) ∧ ((p ∧ r) ∨ (p ∧ ∼r))] ∨ (p ∧ q) ∨ q.
Q: Simplify the above expression (minimize the number of operators).
2.2 Number Bases
Numbers are abstract ideas used to represent quantities and relations. They are abstract in the idea that you
can’t really tell me where ‘3’ is. This abstract concept of numbers (or even just ‘3’) is what some philosophers
(and some PL people) call ‘types.’ We usually see numbers represented with what philosophers (and some
PL people) call ‘tokens’. Ultimately you don’t need to know this, I just find it interesting. Anyway, this
section is about how we can represent these quantities with different ‘tokens’ based on our understandings
of grouping. Here’s what you should know:
• Number base – the symbols used in a system of counting which represent quantities. We usually
say ‘Base n’ where n is the number of digits used in the counting system. Additionally n is the
way which we group quantities. Typically these digits start at 0 and will continue through 9,
and if more are needed, we then start to use letters starting at A. We rarely go past Z, and
you won’t need to do so in this class.
• Number Base Convention – We use the subscript notation to express the base system used. If
no subscript is given, it typically means base 10.
Ex. 2314 means we are using the base 4 number system.
• Number Base Conversion – When we convert numbers from base a to base b, we typically break
convert the base a number to base 10 then convert the resulting base 10 number to base b.
Converting from base a to base 10 – if na is represented as a series of digits dm . . . d2d1d0, we
can convert to base 10 using the following method: n10 = dm(am)+ . . . d2(a2)+d1(a1)+d0(a0).
This is because our number representation system is based on grouping.
2
http://www.ee.surrey.ac.uk/Projects/CAL/digital-logic/gatesfunc/
Converting from base 10 to base b (the fast way) – When we talk about base b, we are saying
that each digit is a grouping of bp where p ∈ Z≥0 in some manner. We can take advantage of
this by repeatedly dividing n10 by b, then taking the remainders in reverse order.
Ex. 3410 to base 4 is 34÷ 4 = 8R4, 8÷ 4 = 2R0, 2÷ 4 = 0R2 so 3410 = 2084
• Binary or Base 2 – this should be a familiar. The binary or base 2 numbering system uses only
2 symbols: 0, 1.
• Octal or Base 8 – this is another common number base for use in CS. This system uses digits
01, 2, 3, 4, 5, 6, 7.
• Hexadecimal or Base 16 – yet another common number base for use in CS. This system uses
digits 01, 2, 3, 4, 5, 6, 7, 8, 9, A,B,C,D,E, F .
Sample Problem(s):
Q: Convert 379843 to base 8
Q: Convert 2BAD4DAD16 to base 10
2.3 Predicates & Quantifiers
Ah, the second section. The bridge between english phrases and ‘mathy’ stuff. Why, oh why, did we have to
introduce more letters to math? Math should have 4 letters and only 4 letters: ‘m’, ‘a’, ‘t’, and ‘h’. Here’s
what you should know:
• Predicate – a property that the subject of a statement can have. Break a sentence into the two
parts – subject and predicate (your English teacher would be so proud). Your subject becomes
the input to the predicate, which outputs a truth value for the input. Ex: “some integer is
greater than 5”, subject = “some integer”, predicate = “is greater than 5”.
• Quantifier – a way to describe when a predicate is True over a range of elements. This requires
three parts – a variable, an amount, and a set/domain. Build as follows: (‘amount’ of ‘variable’
in ‘set/domain’). Our two ‘amounts’ are the ∀ (every single value), and ∃ (at least one value).
From the previous example, we would ‘quantify’ our subject as ∃x ∈ Z.
• Existential Statement – a statement that uses the ∃ symbol; says that there is at least one
element that satisfies the statement.
• Universal Statement – a statement that uses the ∀ symbol; says that every element satisfies the
statement.
• Syntax of Quantified Statements – here’s the syntax I use:
(‘amount’ [of] ‘variable’ [in] ‘set/domain’)[‘predicate’].
Ex: (∃x ∈ Q)[x < 1/3], read as “there exists an x in the Rationals such that x is less than 1/3”. In the course we also used: ‘amount [of] ‘variable’ [in] ‘set/domain’,‘predicate’ Ex: ∃x ∈ Q, x < 1/3 You can have multiple quantifiers at the beginning, i.e.: (∀x ∈ Z)(∃y ∈ Z)[y > x] or
∀x ∈ Z,∃y ∈ Z, y > x.
You’ll always want to quantify your variables, and you’ll want to put that at the beginning
of the statement. If your predicate uses a quantified statement, then keep it’s own quantified
variables with that statement.
Ex: (∀x ∈ D)(∀y ∈ D)[(x < y) ⇒ (∃z ∈ D)[x < z < y]].
3
• Negating Quantified Statements - ∼(∃x ∈ Q)[x < 1/3] becomes (∀x ∈ Q)[x ≥ 1/3].
If it’s confusing why the quantified variable [in] part doesn’t change, then consider the
following:
“Every student has taken calculus”, the opposite of this would be, “NOT Every student
has taken calculus”, which pretty much means that, “There IS a student who has NOT taken
calculus”. ∼(∀s ∈ S)[C(s)] ≡ (∃s ∈ S)[∼C(s)].
Similarly, “There is a student who has taken calculus”, the opposite of this would be, “There
is NOT a student who has taken calculus”, which pretty much means that, “All students have
NOT taken calculus”. ∼(∃s ∈ S)[C(s)] ≡ (∀s ∈ S)[∼C(s)].
If I give you ∼(∀p, q ∈ D)[p ⇒ q], remember to translate the p ⇒ q into ∼p ∨ q, THEN
push the negation in.
Similarly, for ∼(∀p, q ∈ D)[p ⇔ q], remember to translate the p ⇔ q into (p ⇒ q)∧ (q ⇒ p)
OR into p⊗ q ≡ ∼(p⊕ q).
• ‘but’ in English is usually translated to ∧.
Sample Problem(s):
Q: Translate the following english phrase, “For all people, if a given person is Big Shaq, then that person is
not hot,” into predicate logic (note, there are multiple correct answers).
Q: Push the negation in as far as possible for the following quantified statement (ignore the truth value of
the statement): ∼(∃n ∈ Z≥2)[(∀a, b ∈ Z)[n ̸= a · b]].
2.4 Proofs
Proofs are at the core of this class. Everything theoretical in Computer Science involves proofs. Even on
the programming side, you’ll have to prove the correctness of your program. Number Theory proofs are a
good place to start though, since everything builds off it’s core concepts. Here’s what you should know:
• Domains - we learned some general domains that are useful for proofs. You should know these
by heart by now:
Integers - Z, the set of all signed counting numbers: {...,−5,−4,−3,−2,−1, 0, 1, 2, 3, 4, 5, ...}.
Rationals - Q, the set of all numbers that can be written as an Integer divided by an Integer
not equal to zero. q ∈ Q ⇔ (∃a ∈ Z)(∃b ∈ Z̸=0)[q = a
b
].
Irrationals - R−Q, the set of Reals MINUS the set of Rationals. π is not Rational, but it
IS a Real number.
√
2 is not Rational, but it IS a Real number.
Reals - R, the set of Real numbers. Basically any number that is not Imaginary.
• Closure - a set is closed under an operator iff applying said operator to any two members of
the set always yields a member in the set.
Integers are closed under Addition, Subtraction, and Multiplication.
Rationals are closed under Addition, Subtraction, and Multiplication (this may not be
given to you, so you should know how to prove these).
Reals are closed under Addition, Subtraction, and Multiplication.
• Evens & Odds -
definition of Evens: (∀x ∈ Z)[x ∈ ZEven ⇔ (∃k ∈ Z)[x = 2 · k]].
definition of Odds: (∀x ∈ Z)[x ∈ ZOdd ⇔ (∃k ∈ Z)[x = 2 · k + 1]].
• Parity - a property of the Integers; simply means that an Integer can be exclusively either even
or odd. If you have an Integer, and you know it is not odd, then you know for a fact that it is
even. If you have an Integer, and you know it is not even, then you know for a fact that it is
odd.
4
• Primes & Composites -
Prime - a number p is prime iff p’s only factors are 1 and p. The set of primes begins at 2,
increasing in magnitude. Any number below, and including, 1 is not prime. 2 is the only even
prime (I believe you may assume this without proof, but double check during the exam if you
think you need to use it). The primes are infinite - you proved this in class, but be sure you
know how to prove this fact.
Composite - a number that is not prime.
• Proving the Affirmative -
of Existential statements - find an example that makes the statement True.
of Universal statements - show the statement is True for every element (use a formal proof
method).
• Proving the Oppositionary -
of Existential statements - show the statement is False for every element (use a formal
proof method).
of Universal statements - find an example that makes the statement False.
• Direct Proof - using well-known facts/axioms/lemmas/theorems to straightforwardly show a
statement is True or False.
• Indirect Proof - showing a statement is True or False in a non-straightforward way. We use the
following two techniques for this class:
Contrapositive - the contrapositive of a statement is: p ⇒ q ≡ ∼q ⇒ ∼p. If you can prove
∼q ⇒ ∼p True/False, then you’ve proved p ⇒ q True/False. Sometimes the contrapositive is
easier to prove than the original statement.
Contradiction - if you make an assumption about a statement, and show that that assump-
tion leads to a contradiction (logical Falsehood), then you’ve proven the original statement True.
∼p ⇒ c ∴ p.
• Quick Tips:
Always quantify your variables.
Don’t use the same variable twice unless you’re referring to the same element. (i.e. if we
create an even number and an odd number, these numbers are not necessarily the same, hence
our even number should = 2 · k, k ∈ Z, and our odd number should = 2 · r + 1, r ∈ Z.
Each step in a proof should logically and directly follow the statement(s) before it. If you
are unsure if you are making too large of a jump, make sure you are not assuming anything you
cannot or making an assumption about what you can assume. As a last resort, you can justify
each step.
Sample Problem(s):
Q: Prove the Rationals are closed under Subtraction.
Q: Prove (∀n ∈ Z)[4 ∤ n2 − 2].
2.5 Sets
“Sets are wild, fam” - Justin Goodman. We use sets to define all of mathematics. Crazy, right? Luckily for
you, you just need to know the basic concepts of set theory. Here’s what you should know:
• Set - an unordered collection of unique objects. Notation: Set S = {e1, e2, e3, ...}.
NOTE: your textbook for this class claims, on page 117 near the bottom, that the set
{1, 3, 3, 3, 5, 5} “is the same set as the set” {1, 3, 5} “because they have the same elements”. I
would argue that the first set is NOT actually a set, and hence can’t have set operators, BUT
5
that would disagree with your textbook. So who should you believe? Well, Cliff and Justin say
that all elements in a set must be unique, so the first is NOT a set. Now, the textbook also
says that {1, 3, 5} is the same as {3, 5, 1}, which makes sense since the order of a set does not
matter.
• Member/Element - an object that is part of a set. Notation: 5 ∈ {1, 2, 3, 4, 5}.
• Subset - a set of elements that are all members of another set. A subset CAN be equal to it’s
parent set. Notation: for sets S and T , S ⊆ T ⇔ (∀s ∈ S)[s ∈ T ].
• Proper Subset - a set of elements that are all members of another set, but the subset is NOT
equal to the parent set. Notation: for sets S and T , S ⊂ T ⇔ (∀s ∈ S)[(s ∈ T ) ∧ (S ̸= T )].
• Cardinality - the number of elements in a set. The Cardinality of any finite set will always be
a non-negative integer. Notation: for set S, |S| = num elements in S. If S = {2, 3, 4, 5, 6}, then
|S| = 5.
• Empty/Null Set - the set containing zero elements. Notation: ∅ or {} – these symbols are
INTERCHANGABLE. The cardinality of the empty set is zero.
• Universal Set - the set of all possible sets. Notation: U is the Universal Set.
• Power Set - the set of all possible subsets of a set. Notation: if set S = {1, 2, 3}, the power set
of S is P(S) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. The cardinality of the power set
of any set S is |P(S)| = 2|S|.
• Cartesian Products - The Cartesian product of two sets A,B,written as A × B, is a set of
ordered pairs between the items in A and B. The exact definition is:
A×B = {(a, b)|a ∈ A ∧ b ∈ B}
• Set-Builder Notation - a way of defining sets. Syntax: { element | conditions }, read as, “element
such that conditions.” For example, the set of even Integers is: {e | (∃k ∈ Z)[e = 2 · k]}.
• Union - the union of two sets is a set that includes all elements from both sets (discounting
duplicates, since a set must contain unique elements). Notation: for sets S and T , S ∪T = { e |
(e ∈ S) ∨ (e ∈ T ) }. For example, {1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}.
• Intersection - the intersection of two sets is a set that includes only elements from both sets.
Notation: for sets S and T , S ∩T = { e | (e ∈ S)∧ (e ∈ T ) }. For example, {1, 2, 3}∪{3, 4, 5} =
{1, 2, 3, 4, 5}.
• Subtraction - a set minus another set is just a set representing the elements of the second set
taken out of the first set. Notation: for sets S and T , S − T = { e | (e ∈ S) ∧ (e ̸∈ T ) }.
• Compliment - the compliment of a set S is every element from the Universal set that is NOT
contained in set S. Notation: for sets S and T , the compliment is noted as Sc, or S
′
, or S;
(S ∪ T )c, or (S ∪ T )
′
, or S ∪ T ; S
′
= { e | e ∈ (U − S) }.
• Equality - two sets are equal iff both sets are subsets of each other. Notation: for sets S and T ,
S = T ⇔ (S ⊆ T ) ∧ (T ⊆ S). To show this, you can use set-builder notation & logical axioms
to prove an equivalence, or you can prove (e ∈ S ⇒ e ∈ T ) ∧ (e ∈ T ⇒ e ∈ S).
• Disjoint - two sets are disjoint iff both sets have no members in common. This is the same as
saying, for two sets S and T , S ∩ T = ∅.
• Partition of a Set S - a set of sets, I’ll call it T , where the union of every element in T equals the
original set S, and all elements in T are disjoint and non empty. For example, {Z−, {0},Z+} is
a partition of Z.
6
• Venn Diagrams - useful for visualizing sets and set operations. They can be used to get an
understanding of a question, but are not sufficient for proofs.
• Set Proofs - These are proofs where you usually need to show that when any given item in some
set A, that item is either also in some other set B or not in B. Ex. Showing that A ⊂ B means
showing that given any item, x in A, that item x is also in B, but when given some item y in
B, that item y is not in A.
It is important to note that when proving that A = B, you must show that A ⊆ B∧B ⊆ A.
Sample Problem(s):
Q: True or False, (A ∪ (A ∩ (B ∪ (B ∩A)))) ⊆ ((A ∪B) ∩A) ? Justify.
Q: Show that (A ∩B) ∩ (A ∪B) = (A ∩B).
2.6 Sequences, Series, Summations, Products
Sequences and Series are the most hated parts of Calculus II. Luckily for you, they’re in this course too!
You don’t need to do any of the difficult things associated with Sequences and Series though (rejoice!). In
this course, you need to know how to construct them and how to use them. Otherwise, who cares about
convergence and divergence? The most useful series to memorize, from my limited experience in the world,
for me has been the Geometric Series. Don’t spend your time memorizing the Geometric Series for this class
though since we don’t use it often. Here’s what you should know:
• Sequence - any function defined on the non-negative integers to the Reals. Here’s an example:
sn =
2, n = 0, 1
6, n = 2
3sn−3, n ≥ 3
• Series - the sum of all terms in an infinite sequence. Here’s an example:
1
1× 2
+
1
2× 3
+
1
3× 4
+ · · ·+
1
n(n+ 1)
• Summation - represents the sum over a sequence of numbers. Here’s an example:
3∑
i=0
i+ 2
i+ 1
=
0 + 2
0 + 1
+
1 + 2
1 + 1
+
2 + 2
2 + 1
+
3 + 2
3 + 1
0∑
i=1
ai = 0
• Product - represents the product over a sequence of numbers.
4∏
i=1
i2 = 12 + 22 + 32 + 42
0∏
i=1
ai = 1
Sample Problem(s):
Q: Calculate
5∏
i=0
i∑
j=0
j
i+ 1
7
2.7 Countability
Hey, VSauce, Michael here. What is, countability? My original plan was to leave this section blank and
just put a link to the famous VSauce video on countability. I won’t do that, but definitely check out the
meme-master himself’s video, it’s pretty rad. Here’s what you should know:
• Countable - a set S is countable if S is finite.
• Countably Infinite - (countable) a set S is considered countably infinite if you can find a 1 to
1 mapping from Z to S.
Something interesting to note is that if A ⊆ B and B is countably infinite or countable,
then A is countably infinite or countable. You can’t use this fact on exams in this class though
because we never proved it in class.
• Uncountable - a set S which you cannot find a bijection from Z≥0 to S.
Something interesting to note is that if A ⊆ B and A is Uncountable, then B is also
Uncountable. You can’t use this fact on exams in this class though because we never proved it
in class.
• Enumeration - a specific ordering of a set.
• Cantor’s Diagonal Argument - a proof by contradiction that shows a set S is Uncountable. A
diogonalization proof has three steps:
assume S is countable and provide an enumeration of S
create a diagonalizer function that constructs numbers that are in S
use your diagonalizer with your enumeration as input and show that the generated number
is not in your enumeration (hence contradiction)
Sample Problem(s):
Q: Prove whether the set of cubed Reals is countable or uncountable.
2.8 Modular Arithmetic
Arithmetic? We already know Arithmetic; we’ve spent the past 8+ years studying math in grade school!
Well, young ones, this kind of Arithmetic is different, oooooooo. Modular Arithmetic is fun because it
lets you do proofs much easier. Knowing these terms and rules can up your number theory proof game by
5%! Modular Arithmetic is useful for proving statements involving even and odds. Divisibility proofs are
notorious for tripping up students, so make sure you know these rules. Here’s what you should know:
• Divisibility - a number is divisible by another number if there is no remainder/the division of
the numbers results in an integer. Here’s how we represent, “x is divisible by y,” i.e., “y divides
x”:
y | x
and the general rule:
d | n ⇔ (∃k ∈ Z)[n = d · k]
• Modulus - the modulus of a number represents the remainder after dividing. Here’s how we
write it:
4 ≡ 10 (mod 6)
10 % 6 = 4 % 6 = 4
You should write it the first way, because that’s how we write it in this class, but the above
two statements are entirely equivalent in meaning. Also take note that modulus is circular,
much like a clock.
X ≡ −1 (mod 7) ⇔ X ≡ 6 (mod 7)
8
https://youtu.be/s86-Z-CbaHA
Note that, in terms of logic, A ≡ B means statements A and B have the same truth tables,
but in terms of number theory, a ≡ b means the value of a is congruent to the value of b.
• Modulus equivalencies - the following statements are all equivalent:
a ≡ b (mod m)
a (mod m) = b (mod m)
m | (a− b)
a− b
m
∈ Z
a = b+ k ·m, k ∈ Z
• Arithmetic - here are some fancy-dancy modular arithmetic rules:
(a ≡ b (mod m)) ∧ (c ≡ d (mod m)) ⇒ (a+ c) ≡ (b+ d) (mod m)
(a ≡ b (mod m)) ∧ (c ≡ d (mod m)) ⇒ (a · c) ≡ (b · d) (mod m)
Sample Problem(s):
Q: Prove (∀x ∈ Z)[(x ≡ 0 (mod 6)) ⇒ ((x ≡ 0 (mod 2)) ∧ (x ≡ 0 (mod 3)))] . Can you prove the reverse?
Q: For x, y ∈ Z, if the parity of x + y is the same as x · y, prove that you can or cannot determine the
parities of x and y .
Q: For x, y ∈ Z, if x+ y has a different parity as x · y, prove that you can or cannot determine the parity
of x, given
a) y ≡ 4 (mod 12)
b) y ≡ 7 (mod 12)
2.9 Induction
Induction as a whole is a proof technique where what you need to compute/want to prove is built on what you
have already build/already proven. This applies to all forms of induction. There are four forms of Induction
we teach in this class: Weak, Strong, Structural, and Constructive. We usually teach weak induction first so
you understand the fundamental process, then we move on to strong and structural and constructive after
you’ve had some practice. With all induction, if you use the inductive hypothesis in the inductive step,
you MUST say something like, “by the inductive hypothesis”. You will be marked off points if you do not
say this. Also, you MUST NOT assume your hypothesis statement to be true for ALL values (k, n, etc...),
because then you have a logical fallacy (circular reasoning). You will be marked off points if you do this.
Here’s what you should know:
• Properties of Weak Induction:
One base case.
Want to prove that P (k) ⇒ P (k + 1).
• Properties of Strong Induction:
Multiple base cases.
Want to prove P (k + 1).
Assume a range of values to be true
• Properties of Structural Induction:
Can have one or multiple base cases (remember, you’re doing induction on a structure, not
a function).
Want to prove statements about structures (Sets, Trees, Strings, etc...).
Is usually more abstract.
The Hypothesis is funky.
9
The following items are skeletons of how I do MY inductive proofs. Certainly there are different ways to do
it, but this is how I do it.
• Weak Induction
Inductive Base: Prove P (the lowest and only base case) is true.
Inductive Hypothesis: Assume for some arbitrary k ∈ N≥lowest and only base case that
P (k) holds,
i.e.:
Inductive Step: Prove P (k) ⇒ P (k + 1),
i.e.:
• Strong Induction
Inductive Base: Prove P (all base cases) is true.
Inductive Hypothesis: Assume ∀i ∈ {lowest base case, lowest base case+1, lowest base case+
2, …, k}, k ∈ Z≥greatest base case that P (i) holds,
i.e.:
Inductive Step: Prove P (k + 1),
i.e.:
• Structural Induction (varies a lot, take this skeleton with a grain of salt)
Inductive Base: Prove the smallest possibe structure is true.
Inductive Hypothesis: Assume for some arbitrary non-empty / k ∈ Z≥depends structure
holds,
i.e.:
Inductive Step: Prove the property of the structure holds after taking a hypothesis
structure and applying whatever recursive definition,
i.e.:
Sample Problem(s):
Q: Prove (∀n ∈ Z≥4)[n! > 2n] .
Q: Prove (∀n ∈ Z)[sn ≡ 0 (mod 2)], where
sn =
2, n = 0
4, n = 1
3sn−1 + sn−2, n ≥ 2
Q: Prove that the number of vertices in a non-empty binary tree equals the number of edges in that tree plus 1.
2.10 Combinatorics
Justin has 5 dank memes, and Aaron is a meme-critic. Justin wants to know which dank meme he should
post on the UMD meme page, so Justin goes to Aaron to rate his memes. Aaron tells Justin that, although
his memes are trash, he will choose 2 of Justin’s memes to rate. How many combinations of memes could
Aaron choose? Most of these terms’ definitions are taken from your textbook. Here’s what you should know:
• Multiplication Rule – given some procedure E that can be broken down into a sequence of two
tasks, if there are n1 ways to do the first task and for each of those ways there are n2 ways to
do the second task, then the total number of ways to do procedure E is n1 × n2.
10
• Addition Rule – if a task can be done in either one of n1 ways or in one of n2 ways (n1ways ̸=
n2ways) then you can do the task in n1 + n2 ways.
• Permutations – the permutation of a set is the ordered arrangement of the elements in the set.
• r-permutations – the r-permutation of a set is the ordered arrangement of r elements from the
set. The number of r-permutations of a set of size n is denoted:
P (n, r) =
n!
(n− r)!
where n, r ∈ Z≥0, and r ≤ n
• r-combinations – the r-combination of a set is the unordered selection of r elements from the
set (i.e. a subset, of size r, of the original set). The number of r-combinations of a set of size n
is denoted:
C(n, r) =
(
n
r
)
=
n!
r!(n− r)!
where n, r ∈ Z≥0, and r ≤ n
• Combinatorial Argument – (Combinatorial Proof) a proof technique to show a combinatorial
identity is true. You’ll be given some sort-of statement and you’ll want to prove it. Sometimes
doing algebra or induction may be difficult, whereas showing the statement is true combinato-
rially may be easier. In a Combinatorial Argument, you’ll want to generate some combinatorics
question and show you can answer that question two ways.
For more information, see here.
Sample Problem(s):
Q: Prove P (n, n) = P (n, n− 1) through algebra and combinatorial argument.
Q: Prove in any way you see fit,
n∑
i=0
(
m+ i− 1
i
)
=
(
m+ n
n
)
2.11 Probability
This could be considered an extension of combinatorics, as probability is just a ratio of integers based on
counting events. That being said, its probably good to know this stuff. Here’s what you should know:
• The sample space is a set of all outcomes or results of an experiment.
• An event is a subset of the sample space. We usually are going to take the probability of certain
events happening.
• Probability (informal) – The definition that we used in this course is the ratio between the
number of ways an event can happen to the number of all possible events.
Ex. If I roll a 6-sided dice, and want to know the probability of rolling an even number,
then I count the number of ways an even number can occur (3), and the total number of possible
outcomes (6) and then take the ratio: 3
6
.
• Probability (formal) – A function which maps the set of all events in the sample space S to
R1≥x≥0. It’s important to point out that if A and B are disjoint events, then P (A ∪ B) =
P (A) + P (B).
From this definition we can also derive that P (Ac) = 1− P (A)
It is also important to note that for non-disjoint events, P (A∪B) = P (A)+P (B)−P (A∩B).
• Expected value – The expected value is the average outcome supposing that we repeat the
experiment infinitely many times. This value can be calculated using =
n∑
i=1
pia where pi being
the probability of outcome ai happening.
11
http://discretetext.oscarlevin.com/dmoi/sec_comb-proofs.html
• Conditional Probability – The probability of event A occurring given that event B has already
occurred is written as P (A|B). This can be calculated as P (A|B) = P (A∩B)
P (B)
Because A∩B and A∩Bc are disjoint, we can write P (A) = P (A|B)P (B)+P (A|Bc)P (bc).
• Bayes Theorem – We can relate P (A|B) and P (B|A) with Bayes’ Theorem: P (B|A) = P (A|B)P (B)
P (A)
.
This helps us either make inferences about what previously happened given what we observed,
or helps up strengthen our beliefs about something based on our observations.
We can rewrite this as P (B|A) = P (A|B)P (B)
P (A|B)P (B)+P (A|Bc)P (Bc) .
Sample Problem(s):
Q: If I am roll 3 distinct 6-sided dice, what is the probability that the sum of all 3 is prime?
Q: Suppose that a friend flipped a coin 3 times. They said that the first flip was heads. What is the
probability that all three coin flips are heads?
Q: If I were to roll a 4-sided dice and a 3-sided dice, and add up the values, what is the expected value?
2.12 Algorithms
As scientists, we care a lot about how well an algorithm works, and how well it performs. This pretty much
uses a wide variety of things we already learned and will be the bases for CMSC351. Here’s what you should
know:
• Algorithm – A series of steps with reasoning that should be used to obtain a goal. Algorithms
have properties like runtime, space complexity, feasibility, Independence, etc. We mostly care
about runtime and space, but we will focus on runtime.
• Runtime – A property an algorithm can have. There are two main ways to calculate runtime:
by counting how long an algorithm takes to run, or by counting the number of operations which
occur in an algorithm. In Software, the actual time is difficult because this is highly dependent
on hardware and what other processes are running on the system. Thus, we focus on counting
the number of operations which occur.
• Runtime Notations – We usually focus on 3 types of runtime: best case, worst case, and average
case.
Best case is asking the fastest time that could ever be achieved, or what is the least amount
of operations.
Worst case is asking the longest time that could ever be achieved, or what is the most
amount of operations.
Average case is asking what is the average time or number of operations over a range of
input. This is vague as most algorithms have an infinite number of possible inputs.
Sample Problem(s):
i n t mystery ( i n t n){
i n t c = 0 ;
f o r ( i n t i = 0 ; i < n ; i++)
f o r ( i n t j = 0 ; j < i ; i++)
c = c ∗ i ∗ j ;
r e turn c ; }}
Q: How many multiplications occur?
12
3 Tips
My strategies for exam success:
• Get plenty of sleep the night before the night before the exam. My high school track coach
always told us the night before the night before is more important than the night before. I
don’t know if it actually works. Maybe it’s a placebo. Who knows.
• Get plenty of sleep the night before the exam. I know this is important to success. Your brain
needs rest. 8 hours of sleep with 2 hours of studying is significantly better than 2 hours of sleep
with 8 hours of studying.
• Eat food before the exam. This is a long exam; feeling hungry mid-exam will certainly distract
you.
• Drink water before and during the exam. I don’t have any rationale other than your body is
nearly 70% water.
• Use the restroom before the exam. If you really really really need to pee during the exam, then
you have just wasted precious exam time.
• Be aware of each concept, even if you didn’t get to study it. If you come across something
you’re rusty with, then write down as much as you know about the problem.
• Go for a run, or do something active the day before the exam. Get the blood flowing. You’ll
feel the effects of exercise for 24 hours. It will also tire you out so you’ll sleep better.
• Avoid drugs and alcohol before the exam (unless a medical professional says it’s fine).
• The internet suggests eating healthy snacks, like fruit, during an exam. My go-to is sugar
(specifically Pixy Stixtm). Find what works for you and stick with it, even if it’s a placebo. If
it works, it works.
• Please write neatly. Us graders much prefer reading a paragraph proof with handwriting we
can actually read.
• Be confident, but not cocky.
• Often, your first instinct answer is the correct answer. Stay away from over-analyzing a question.
• During the exam when you have time, re-read each question and make sure you’re actually
answering the question. I can’t even begin to count how many times this tip has saved my ass
during math exams.
• If you read a problem and the answer doesn’t immediately jump out at you, or you get stuck
on a problem, mark it and move on. Sometimes other exam questions will give you the insight
you need to go back and answer the marked problem.
• A few hours before the exam, just relax. You have been studying all semester for this exam
and you know the content. You got this.
• Look at pictures of cute baby animals before the exam. It will help you relax.
• Plan in your mind how you want to attack this exam. 2 hours for 6 questions means 20 minutes
per question. Maybe your plan is to spend 2 minutes reading a question, then 10 minutes
answering a question, then 8 minutes checking your work (repeat 6 times). Maybe you are
more comfortable on topic A than topic B, so you want to allot more time to topic B but save
it for last. You have to find a system that works for you, but come to the exam knowing your
system.
• Don’t forget the big picture of life.
13
4 Answers to Sample Problems
These are the answers to the sample problems presented in each section.
1. Logic
(a) (0 = False, 1 = True)
p q r p ∨ q p ∧ r p ∧ ∼r p ∧ q [(p ∨ q) ∧ ((p ∧ r) ∨ (p ∧ ∼r))] ∨ (p ∧ q) ∨ q
0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 1 0 1 0 0 0 1
0 1 1 1 0 0 0 1
1 0 0 1 0 1 0 1
1 0 1 1 1 0 0 1
1 1 0 1 0 1 1 1
1 1 1 1 1 0 1 1
(b) Statement: [(p ∨ q) ∧ ((p ∧ r) ∨ (p ∧ ∼r))] ∨ (p ∧ q) ∨ q
≡ [(p ∨ q) ∧ (p ∧ (r ∨ ∼r))] ∨ (p ∧ q) ∨ q Distributivity Law
≡ [(p ∨ q) ∧ (p ∧ T )] ∨ (p ∧ q) ∨ q Negation Law
≡ [(p ∨ q) ∧ p] ∨ (p ∧ q) ∨ q Identity Law
≡ [p ∧ (p ∨ q)] ∨ (p ∧ q) ∨ q Commutativity Law
≡ p ∨ (p ∧ q) ∨ q Absorption Law
≡ p ∨ q Absorption Law
Q: Convert 2BAD4DAD16 to base 10
2. Number Bases
(a)
379843÷ 8 =47480 R 3
47480÷ 8 = 5935 R 0
5935÷ 8 = 781 R 7
781÷ 8 = 92 R 5
92÷ 8 = 11 R 4
11÷ 8 = 1 R 3
1÷ 8 = 0 R 1
37984310 = 13457038
(b) 2BAD4DAD16 = 2(167)+11(166)+10(165)+14(164)+4(163)+14(162)+10(161)+14(160) =
73277790110
3. Pred. & Quant.
(a) (∀p ∈ P )[BIG(p) ⇒ (p ̸∈ H)], where,
• P is the set of all people.
• BIG(p) is a predicate that returns true iff the person p is the one and only Big Shaq.
• H is the set of all people who are hot, and H ⊂ PP .
(b) Statement: ∼(∃n ∈ N≥2)[(∀a, b ∈ Z≥0)[n ̸= a · b]]
≡ (∀n ∈ Z≥2)∼[(∀a, b ∈ Z≥0)[n ̸= a · b]]
≡ (∀n ∈ Z≥2)[(∃a, b ∈ Z≥0)∼[n ̸= a · b]]
≡ (∀n ∈ Z≥2)[(∃a, b ∈ Z≥0)[n = a · b]]
4. Proofs
(a) We can directly prove the Rationals are closed under Subtraction by taking two Rational num-
bers, subtracting them, and showing that the resulting number is a Rational number.
Let’s first sample 2 Rational numbers: x, y ∈ Q.
14
By definition of Rational, (∃a ∈ Z)(∃b ∈ Z̸=0)[x = a
b
] and (∃c ∈ Z)(∃d ∈ Z̸=0)[y = c
d
].
x− y = a
b
− c
d
= a·d
b·d −
c·b
d·b =
a·d−c·b
b·d ...
a · d− c · b ∈ Z because the Integers are closed under multiplication and subtraction, and
a, b, c, d are all Integers.
Let e ∈ Z and set e = a · d− c · b.
b · d ∈ Z because the Integers are closed under multiplication, and we also know b · d ̸= 0
since neither b nor d equal 0.
Let f ∈ Z̸=0 and set f = b · d.
...a·d−c·b
b·d =
e
f
, which is a Rational number by definition
(b) We can prove 4 ∤ n2 − 2 by contradiction.
Assume 4 | n2 − 2. By definition, 4 | n2 − 2 ⇔ n2 − 2 = 4 · k, k ∈ Z.
Case 1:
n is even, i.e. n = 2 · p, p ∈ Z
n2 − 2 = 4k ⇒ (2p)2 − 2 = 4k ⇒ 4p2 − 2 = 4k ⇒ 2p2 − 1 = 2k ⇒ 2p2 = 2k + 1
The left side must be an even number (we have 2 times an integer (an integer squared is
an integer by closure)), and the right side must be an odd number (definition of odd). An even
can never equal an odd number, so we have a contradiction in this case.
Case 2:
n is odd, i.e. n = 2 · q + 1, q ∈ Z
n2 − 2 = 4k ⇒ (2q + 1)2 − 2 = 4k ⇒ 4q2 + 4q + 1− 2 = 4k ⇒ 2(2q2 + 2q) = 2(2k) + 1
The left side must be an even number (we have 2 times an integer (integers are closed
under multiplication and addition)), and the right side must be an odd number (definition of
odd (integers are closed under multiplication)). An even can never equal an odd number, so we
have a contradiction in this case.
Since an Integer, by parity, can be exclusively even or odd, and since we arrived at a contra-
diction in both cases of even and odd, we have arrived at a contradiction, which means our
original statement 4 ∤ n2 − 2 is true
5. Sets Q: True or False, (A ∪ (A ∩ (B ∪ (B ∩A)))) ⊆ ((A ∪B) ∩A) ? Justify.
Q: Show that (A ∩B) ∩ (A ∪B) = (A ∩B).
(a) This one looks gross at first, but then you realize it’s trivial. Suppose that x ∈ (A ∪ (A ∩ (B ∪
(B ∩A)))). This means
x ∈ A ∨ x ∈ (A ∩ (B ∪ (B ∩A))).
x ∈ A ⇒ x ∈ A ∨ x ∈ B
x ∈ A ∧ (x ∈ A ∨ x ∈ B) is the same as saying x ∈ (A ∪B) ∩A
x ∈ (A ∩ (B ∪ (B ∩A))) means that x ∈ A ∧ x ∈ (B ∪ (B ∩A))
(x ∈ A ∧ x ∈ (B ∪ (B ∩A))) ⇒ x ∈ A.
We saw before that x ∈ A ⇒ x ∈ (A∪B)∩A so we can say that (x ∈ A∧x ∈ (A∩(B∪(B∩A)))) ⇒
x ∈ (A ∪B) ∩A
Since x ∈ A ⇒ x ∈ (A ∪ B) ∩ A and (x ∈ A ∧ x ∈ (B ∪ (B ∩ A))) ⇒ x ∈ (A ∪ B) ∩ A, then
we can say that x ∈ A ∨ x ∈ (A ∩ (B ∪ (B ∩ A))) ⇒ x ∈ (A ∪B) ∩ A. This is the definition of
subset so we can conclude that (A ∪ (A ∩ (B ∪ (B ∩A)))) ⊆ ((A ∪B) ∩A)
(b) To show set equality, we need to show that (A ∩ B) ∩ (A ∪ B) ⊆ (A ∩ B) and that A ∩ B ⊆
(A ∩B) ∩ (A ∪B) = (A ∩B).
Let us begin with showing that (A∩B)∩(A∪B) ⊆ (A∩B). Suppose that x ∈ (A∩B)∩(A∪B).
This means that x ∈ (A ∩B) ∧ x ∈ (A ∪B).
This means that x ∈ (A ∩ B) so x ∈ (A ∩ B) ∩ (A ∪ B) ⇒ x ∈ (A ∩ B). This is the definition
of subset, so we showed that (A ∩B) ∩ (A ∪B) ⊆ (A ∩B).
Now we need to show that A ∩B ⊆ (A ∩B) ∩ (A ∪B) = (A ∩B).
Suppose that x ∈ A ∩B. This means that x ∈ A ∧ x ∈ B.
x ∈ A ⇒ x ∈ A ∨ x ∈ B
x ∈ B ⇒ x ∈ A ∨ x ∈ B
This means that x ∈ A ∩B ⇒ x ∈ A ∪B.
15
Since x ∈ A ∩ B ⇒ x ∈ A ∪ B then this means that we can conclude that x ∈ A ∩ B ⇒ (x ∈
A ∪ B ∧ x ∈ A ∩ B which is the same as x ∈ A ∩ B ⇒ x ∈ (A ∩ B) ∩ (A ∪ B). This is the
definition of subset so we can conclude A ∩B ⊆ (A ∩B) ∩ (A ∪B) = (A ∩B).
Since (A∩B)∩ (A∪B) ⊆ (A∩B) and A∩B ⊆ (A∩B)∩ (A∪B) = (A∩B), we can say that
(A ∩B) ∩ (A ∪B) = A ∩B
6. Seq., Ser., Sum., Prod.
(a)
5∏
i=0
i∑
j=0
j
i+1
= (
∑0
j=0
j
0+1
) × (
∑1
j=0
j
1+1
) × (
∑2
j=0
j
2+1
) × (
∑3
j=0
j
3+1
) × (
∑4
j=0
j
4+1
) ×
(
∑5
j=0
j
5+1
) = ( 0
1
)× ( 0
2
+ 1
2
)× ( 0
3
+ 1
3
+ 2
3
)× ( 0
4
+ 1
4
+ 2
4
+ 3
4
)× ( 0
5
+ 1
5
+ 2
5
+ 3
5
+ 4
5
)× ( 0
6
+ 1
6
+
2
6
+ 3
6
+ 4
6
+ 5
6
) = 0
7. Countability
(a) The set of cubed Reals is uncountable. We will prove this by contradiction. Before I go into the
proof, note that every Real number has a cube root (see here). This means I can write out any
Real number and know for certain that there exists a cube root of it, which means any Real
number I write is the cube of another Real number. Hence, this proof is identical to Cantor’s
Diagonal Argument for the Reals being uncountable.
Assume the set of cubed Reals (I’ll note as ‘CR’) is countable. Then, there exists some 1 to 1
mapping of f(x) such that f : Z≥0 7→ CR. Let’s enumerate this as such:
N CR
0 10 . 9 2 3 4 1 5 6 2 4 ...
1 2 . 7 1 4 1 5 9 3 6 6 ...
2 67 . 1 2 3 4 5 2 1 2 3 ...
3 104 . 6 4 2 0 9 5 7 5 9 ...
4 9 . 0 0 0 0 0 8 1 2 2 ...
5 2 . 9 8 7 6 5 0 0 1 0 ...
6 81 . 3 3 3 4 4 4 4 7 8 ...
7 0 . 0 2 4 1 1 1 5 8 9 ...
... ...
Now, let us define a function g(x) such that g : Z≥0 7→ Z≥0. g(x) is defined as follows:
g(x) = (fx(x) + 1)%10, where fx(x) is the xth decimal digit in our bijection f(x).
In our example enumeration, f0(0) = 9, f1(1) = 1, f2(2) = 3, ....
Let us define a sequence of digits that generates a number as such: 0.g(0)g(1)g(2)g(3)g(4)...
In our example enumeration, this sequence would generate the number 0.02411159... I
argue that this number generator will create a number that is in CR but NOT given in any
enumeration from Z≥0 7→ CR.
Note that the number created by our generator is a Real number, and we know that all Real
numbers have a cube root, so the outputted number must be a cube of another Real number.
Hence, all numbers created by our generator are elements of CR.
Note that the number created by our generator is necessarily different than any number given
in any enumeration from Z≥0 7→ CR. We change each digit on the diagonal, which makes the
new number different from ANY number in the enumeration by at least 1.
In our example, the generated number is 0.02411159..., which you know is different than
all of the numbers already written in the enumeration. Even the last number, 0.024111589, our
generated number differs from it by the (indexed) 7th decimal digit.
Hence, our generator will create, given any finite enumeration, a new number in CR that is
NOT in the enumeration. This is a contradiction, because we assumed [the enumeration of]
CR was finite. Since we have a contradiction, our original statement is true.
The set of cubed Reals is uncountable
8. Mod. Arith.
16
https://en.wikipedia.org/wiki/Cube_root#Real_numbers
(a) x ≡ 0 (mod 6) ⇔ x = 6 · k, k ∈ Z
x = 6k ⇔ x = 2(3k), now set 3k = p, p ∈ Z by closure.
x = 2p ⇔ x ≡ 0 (mod 2)
x = 6k ⇔ x = 3(2k), now set 2k = q, q ∈ Z by closure.
x = 3q ⇔ x ≡ 0 (mod 3)
We have now shown both x ≡ 0 (mod 2) and x ≡ 0 (mod 3)
It turns out we CAN go the other way, ((x ≡ 0 (mod 2))∧ (x ≡ 0 (mod 3))) ⇒ (x ≡ 0 (mod 6)).
This requires a theorem from Euclid’s Lemma, which says, “If n | ab, and n is coprime to a,
then n | b”. We know 3 | x, so set x = 2b, b ∈ Z. We now have 3 | 2b. Well, the only positive
integer that divides both 2 and 3 is 1, so 2 and 3 are coprime. Hence, from the theorem, we
have that 3 | 2b ⇒ 3 | b ⇔ b = 3k, k ∈ Z ⇔ 2b = 6k ⇔ 6 | 2b ⇔ 6 | x
(b) x+ y and x · y must both be the same parity.
We have 4 sub-cases to show now.
If x ≡ 0 (mod 2) and y ≡ 0 (mod 2), then x+ y ≡ 0 + 0 ≡ 0 (mod 2) and x · y ≡ 0 · 0 ≡
0 (mod 2).
If x ≡ 0 (mod 2) and y ≡ 1 (mod 2), then x+ y ≡ 0 + 1 ≡ 1 (mod 2) and x · y ≡ 0 · 1 ≡
0 (mod 2).
If x ≡ 1 (mod 2) and y ≡ 0 (mod 2), then x+ y ≡ 1 + 0 ≡ 1 (mod 2) and x · y ≡ 1 · 0 ≡
0 (mod 2).
If x ≡ 1 (mod 2) and y ≡ 1 (mod 2), then x + y ≡ 1 + 1 ≡ 2 ≡ 0 (mod 2) and
x · y ≡ 1 · 1 ≡ 1 (mod 2).
The only sub-case where we output x + y and x · y having the same parity is the first, where
both x and y are even, and x+ y and x · y are also both even. Since this is the only case that
works, the answer is YES we can determine the parities of x and y and they turn out to be
both even
(c) (a) Given y ≡ 4 (mod 12)
If x+ y ≡ 0 (mod 2) then x · y ≡ 1 (mod 2), or, if x+ y ≡ 1 (mod 2) then x · y ≡ 0 (mod 2)
Well, y ≡ 4 (mod 12) ⇔ y = 4 + 12 · k, k ∈ Z ⇒ y = 2(2 + 6k) ⇔ y ≡ 0 (mod 2)
Now we just need parities of x that satisfy our case, if any.
x ≡ 0 (mod 2) or x ≡ 1 (mod 2).
For x ≡ 0 (mod 2), x+ y ≡ 0+0 ≡ 0 (mod 2) and x · y ≡ 0 · 0 ≡ 0 (mod 2). This doesn’t
work.
For x ≡ 1 (mod 2), x+ y ≡ 1+ 0 ≡ 1 (mod 2) and x · y ≡ 1 · 0 ≡ 0 (mod 2). This DOES
work.
The only case that works is when x is odd, and, since x being even doesn’t work, we can safely
deduce that the parity of x is odd
(b) Given y ≡ 7 (mod 12)
If x+ y ≡ 0 (mod 2) then x · y ≡ 1 (mod 2), or, if x+ y ≡ 1 (mod 2) then x · y ≡ 0 (mod 2)
Well, y ≡ 7 (mod 12) ⇔ y = 7 + 12 · k, k ∈ Z ⇔ y = 1 + 6 + 12k ⇒ y = 1 + 2(3 + 6k) ⇔
y ≡ 1 (mod 2)
Now we just need parities of x that satisfy our case, if any.
x ≡ 0 (mod 2) or x ≡ 1 (mod 2).
For x ≡ 0 (mod 2), x+ y ≡ 0+ 1 ≡ 1 (mod 2) and x · y ≡ 0 · 1 ≡ 0 (mod 2). This DOES
work.
For x ≡ 1 (mod 2), x + y ≡ 1 + 1 ≡ 2 ≡ 0 (mod 2) and x · y ≡ 1 · 1 ≡ 1 (mod 2). This
DOES work.
Since both parities of x satisfy the requirement, we cannot determine the parity of x (we just
showed x can be even OR odd)
9. Induction
(a) Let P (n) be the proposition we are attempting to prove true. We proceed via mathematical
induction on n.
Inductive Base: Prove P (4).
17
https://en.wikipedia.org/wiki/Euclid%27s_lemma
https://en.wikipedia.org/wiki/Coprime_integers
4! = 4× 3× 2× 1 = 24
24 = 16
24 > 16, done
Inductive Hypothesis: Assume for some arbitrary k ∈ Z≥4, P (k) holds, i.e.: k! > 2k
Inductive Step: Prove P (k) ⇒ P (k + 1), i.e. show (k + 1)!
?
> 2k+1
(k + 1)! = k!× (k + 1), by definition of factorial.
k! > 2k, by our inductive hypothesis
∴ k!× (k + 1) > 2k × (k + 1)
So, if we can show 2k × (k + 1) > 2k+1, then by transitivity we can conclude
(k!× (k + 1) > 2k × (k + 1)) ∧ (2k × (k + 1) > 2k+1) ⇒ (k + 1)! > 2k+1
So now we want to prove, 2k × (k + 1)
?
> 2k+1
2k × (k + 1)
?
> 2k+1 ⇒ 1× (k + 1)
?
> 21, by algebra (dividing the 2k)
k + 1
?
> 2 ⇒ k > 1, which is a true statement since by definition k ∈ Z≥4
By transitivity, our inductive step holds, and hence our inductive proof holds ∀n ∈ Z≥4
(b) Note that this question is asking you to prove that each number in the sequence is even.
Let P (n) be the proposition we are attempting to prove true. We proceed via mathematical
induction on n.
Inductive Base: Prove P (0) ∧ P (1).
P (0): s0 = 2 by definition, s0 ≡ 2 ≡ 0 (mod 2), done
P (1): s1 = 4 by definition. s1 ≡ 4 ≡ 2 ≡ 0 (mod 2), done
Inductive Hypothesis: Assume for some arbitrary i ∈ {0, 1, 2, …, k}, and k ∈ Z≥1, P (i)
holds, i.e.: si ≡ 0 (mod 2)
Inductive Step: Prove P (k + 1), i.e. show sk+1 ≡ 0 (mod 2)
k ∈ Z≥1 ⇒ k ≥ 1 ⇒ k + 1 ≥ 2, so we can apply the recursive definition to sk+1
sk+1 = 3sk + sk−1
k ∈ Z≥1 ⇒ k ≥ 1, and k ≤ k, so k falls in the inductive hypothesis
k ∈ Z≥1 ⇒ k ≥ 1 ⇒ k − 1 ≥ 0, and k − 1 ≤ k, so k − 1 falls in the inductive hypothesis
By the inductive hypothesis, sk ≡ 0 (mod 2) and sk−1 ≡ 0 (mod 2)
sk ≡ 0 (mod 2) ⇔ sk = 2m, m ∈ Z
sk−1 ≡ 0 (mod 2) ⇔ sk−1 = 2t, t ∈ Z
sk+1 = 3sk + sk−1 = 3(2m) + 2t = 6m+ 2t = 2(3m+ t) …
m and t are both integers, and integers are closed upon multiplication and addition,
let r = 3m+ t,r ∈ Z
… sk+1 = 2r ⇔ sk+1 ≡ 0 (mod 2)
(c) Let P (T ) be the property V (T ) = E(T ) + 1 where V (T ) = number of vertices in binary tree T
and E(T ) = number of edges in binary tree T . We proceed via Structural Induction on binary
trees T .
Inductive Base: Prove P (T ) holds when T is a single root vertex.
Well, when T is a single vertex, V (T ) = 1 and E(T ) = 0. V (T ) = 1 = 0 + 1 = E(T ) + 1, done
Inductive Hypothesis: Assume P (T ) holds for some arbitrary non-empty binary tree T , i.e.:
V (T ) = E(T ) + 1
Inductive Step: Construct a new binary tree Tnew that consists of a root node with child
trees Tl and Tr. By definition, Tnew could have one child or both children. Let Tl and Tr be
inductive hypothesis trees and show P (Tnew) holds.
Case 1: Without loss of generality, let Tnew have one child, either Tl or Tr. Both cases of one
child are exactly the same, so I’ll show it for Tl but you can repeat this exactly for Tr.
By the hypothesis, Tl has the property V (Tl) = E(Tl) + 1.
By definition of binary trees, V (Tnew) = V (Tl) + 1 and E(Tnew) = E(Tl) + 1. So,
V (Tnew) = V (Tl) + 1
IH
= E(Tl) + 1 + 1 = E(Tnew) + 1 .
Case 2: Let Tnew have two children, Tl and Tr.
By the hypothesis, Tl and Tr have the property V (Tl) = E(Tl)+1 and V (Tr) = E(Tr)+1.
By definition of binary trees, V (Tnew) = V (Tl)+V (Tr)+1 and E(Tnew) = E(Tl)+E(Tr)+
18
2. So, V (Tnew) = V (Tl) + V (Tr) + 1
IH
= E(Tl) + 1 + E(Tr) + 1 + 1 = E(Tl) + E(Tr) + 2 + 1 =
E(Tnew) + 1.
Since P (Tnew) holds in both cases, by induction P (T ) holds for all non-empty binary trees
10. Combinatorics
(a) Algebra: P (n, n) = n!
(n−n)! =
n!
0!
= n!
1
= n!
(1)!
= n!
(n−n+1)! =
n!
(n−(n−1))! = P (n, n− 1)
Combinatorical Argument: Consider a list with n unique elements. The number of n-tuples
(ordered) you can make from this list is n!, equal to the number of n-permutations which is
P (n, n). Now consider the same list but creating n − 1-tuples (ordered). Note that when you
get all of your n− 1-tuples, there is just 1 element left in the original list, so tacking that one
element onto your n − 1-tuple doesn’t change anything. Hence, the two ways of ordering are
equal
(b) I’ll prove this inductively.
Let P (n) be the proposition we are attempting to prove true. We proceed via mathematical
induction on n.
Inductive Base: Prove P (0).∑0
i=0
(
m+i−1
i
)
=
(
m+0−1
0
)
= 1(
m+0
0
)
= 1
1 = 1, done
Inductive Hypothesis: Assume P (k) holds for some arbitrary k ∈ Z≥0, i.e.:
∑k
i=0
(
m+i−1
i
)
=(
m+k
k
)
Inductive Step: Prove P (k) ⇒ P (k + 1), i.e.:
∑k+1
i=0
(
m+i−1
i
)
=
(
m+k+1
k+1
)∑k+1
i=0
(
m+i−1
i
)
=
∑k
i=0
(
m+i−1
i
)
+
(
m+(k+1)−1
k+1
)
By the Inductive Hypothesis, =
(
m+k
k
)
+
(
m+k
k+1
)
By Pascal’s Identity, =
(
m+k+1
k+1
)
11. Probability
(a) The total number of rolls possible is 63 = 216. The largest value I could obtain is 18, and the
smallest value is 3. The prime numbers in this range are: {3, 5, 7, 11, 13, 17}.
To obtain a 3, I could only roll {(1, 1, 1)}.
To obtain a 5, I could roll a (1, 1, 3) or any variant of this (ie. (1, 3, 1)or(3, 1, 1)) or a (1, 2, 2)
or any of it’s variants. Each of these can be represented as 3!
2!
.
To obtain a 7, I could roll a (1, 1, 5), (1, 2, 4), (1, 3, 3), (2, 2, 3). These have 3!
2!
, 3!, 3!
2!
, 3!
2!
ways of
occurring respectively.
To obtain an 11, I could roll a (1, 4, 6), (1, 5, 5), (2, 3, 6), (2, 4, 5), (3, 3, 5), (3, 4, 4). These have
3!, 3!
2!
, 3!, 3!, 3!
2!
, 3!
2!
ways of occuring respectively.
To obtain a 13, I could roll a (1, 6, 6), (2, 5, 6), (3, 4, 6), (3, 5, 5), (4, 4, 5). These have a 3!
2!
, 3!, 3!, 3!
2!
, 3!
2!
ways of occurring respectively.
To obtain a 17, I could roll a (6, 6, 5). This can occur 3!
2!
ways.
So the total number of ways I can roll a prime number is (1) + ( 3!
2!
+ 3!
2!
) + ( 3!
2!
+ 3! + 3!
2!
+ 3!
2!
) +
(3! + 3!
2!
+ 3! + 3! + 3!
2!
+ 3!
2!
) + ( 3!
2!
+ 3! + 3! + 3!
2!
+ 3!
2!
) + ( 3!
2!
) = 73. So the probability is 73
216
(b) Let A = flipping 3 heads in a row and B = First coin flip Heads. To calculate P (A|B) we need
P (A ∩ B) and P (B) to use the formula P (A|B) = P (A∩B)
P (B)
. P (B) should be 0.5. P (A ∩ B) is
the probability of flipping 3 heads in a row and the first one is heads. Because in order to flip
all 3 heads the first one must be heads as well, this is the same as P (A). This is .125. Then
P (A|B) = .125
.5
= .25
(c) If I roll a 4 sided dice, and a 3 sided dice, then add the values up, I could obtain a sum of
{2, 3, 4, 5, 6, 7}. I can get a 2 one way: (1, 1). I can get a 3 in 2 ways: (1, 2), (2, 1). I can get
a 4 in 3 ways (1, 3), (2, 2), (3, 1). I can get a 5 in 3 ways: (2, 3), (3, 2), (4, 1). I can get a 6 is 2
ways: (3, 3), (4, 2). I can get a 7 in 1 way: (4, 3). We then need the probability of each of these
19
outcomes.
The probability I got a 2 is 1
4
· 1
3
= 1
12
The probability I got a 3 is 1
4
· 13 + 1
4
· 13 = 2
12
The probability I got a 4 is 1
4
· 1
3
+ 1
4
· 1
3
+ 1
4
· 1
3
= 3
12
The probability I got a 5 is 1
4
· 1
3
+ 1
4
· 1
3
+ 1
4
· 1
3
= 3
12
The probability I got a 6 is 1
4
· 1
3
+ 1
4
· 1
3
= 2
12
The probability I got a 7 is 1
4
· 1
3
= 1
12
Thus the expected value is 1
12
(2) + 2
12
(3) + 3
12
(4) + 3
12
(5) + 2
12
(6) + 1
12
(7) = 54
12
= 9
2
12. Algorithms
(a) The multiplications only occur in the body of the inner for loop, and there are 2 of them. We
can simplify this as just counting the number of times the body of the for loop executes and
then multiplying that by 2.
Since we are counting (and hence adding) the number of times this occurs, we can break this
into summations. The outer loop runs
n∑
i=0
times. The inner loop would then consequently run
outer loop index∑
j=0
times. We can then say the total number of times the body of the inner loop will
run
n∑
i=0
i∑
j=0
times. Finally if there are two multiplications per body of innerloop, then we can
say the total number of multiplications is
n∑
i=0
i∑
j=0
2
5 Outro
First, congrats for making it to the end of the course! This course is difficult. This course is much different
than the Computer Science courses you’re acclimated to, and it only gets weirder from here. You all put a
lot of work into the course (tons of homework and quizzes), but you made it to the end and you should feel
proud of yourself for coming this far. The course is not over because there is a final exam, but after that
you’re done! Then comes CMSC351…..
Second, I cannot stress enough how important it is to practice, and (more importantly) fully understand,
the material. Although this class is in the computer science department, this class is absolutely a math class.
How do you study for a Calculus I or II or III final? I do all of the provided practice exams and textbook
practice problems until I am comfortable with the methods, and I make sure I understand whatever it is I’m
doing. The same deal applies to this course. It’s a math course and you should treat it as such. The harder
you study and the more you practice, the better you will do on this exam. If you haven’t started studying
and practicing, now is the time to start. Some of the first topics you learned may be rusty. Study those first.
Look through all of the topics in this guide, mark the ones you understand, then look back in your notes
and study all of the unmarked topics. Then do practice problems. Retake your old exams. Find induction
problems online. Work hard. You got this. Good luck!
– –
20
Intro
Topics
Logic
Number Bases
Predicates & Quantifiers
Proofs
Sets
Sequences, Series, Summations, Products
Countability
Modular Arithmetic
Induction
Combinatorics
Probability
Algorithms
Tips
Answers to Sample Problems
Outro