Math for CS Review

This page is meant to be a a review sheet for math that is needed in computer science. Some of this is review from high school math, while some is covered in CS 303. For content you have seen before, this review sheet is probably enough to jog your memory and help you study. For content you have not seen before, see the texts used in CS 303, Khan Academy (Math, AP CS Principles, and Computing), or ask the internet and pick a resource that works for you (then check back here to make sure what you are seeing agrees with the review information here).

Notation

Not all of the following will be meaningful to you if you have not seen the context where these symbols are used, so check this list periodically.

• ℝ: the set of real numbers
• ℚ: the set of rational numbers
• ℤ: the set of integers
• ℂ: the set of complex numbers
• ℝ²: a pair of real numbers
• ⅈ: the imaginary unit
• ⌊   ⌋: floor of a number (round down)
• ⌈   ⌉: ceiling of a number (round up)
• |   |: cardinality of a set (size)
• ▪ or □: end-of-proof symbol
• ∃: there exists
• ∄: there does not exist
• ∈: is an element of
• ∉: is not an element of
• ∀: for every
• ¬: not
• ∅: empty set
• ∏: product
• ∑: summation
• ∞: infinity
• ∣: such that, or 'divides'
• ∤: does not divide
• ∧: and
• ∨: or
• ∩: intersection
• ∪: union
• ∴: therefore
• ≅: is congruent to
• ⊂: is a proper subset of
• ⊄: is not a proper subset of
• ⊆: is a subset of or is equal to
• ⊈: is not a subset of and not equal to
• ⊕: exclusive or
• ∩: intersection
• ∪: union
• ∼: is approximately, also used for relations
• ℤ_n: the integers mod n
• e: base of the natural logarithm
• ln: natural logarithm
•  !: factorial
• →: implies
• ⇔ or ↔: if and only if
• √: square root
• { }: used to denote a set
• -: set difference
• line over the set: complement of a set
• ×: Cartesian product
• 2 raised to the set: powerset of a set
• G or G=(V,E): a graph
• E: edges of a graph
• V: vertices of a graph
• m: number of edges of a graph
• n: number of vertices of a graph
• d or deg: degree of a vertex
• s.t.: such that

From Algebra

• Order of operations: PEMDAS - first parenthesis, then exponents, then multiplication/division/modulus, then addition and subtraction. And left to right.
• Powers/exponents
  • 2¹⁰ = 1024, roughly 1 thousand
  • 2^a+b = 2^a * 2^b
  • y^a+b = y^a * y^b
  • (y^a)^b = y^{a * b}
  • 2^-a = 1 / (2^a)
  • 2²⁰ = 1024 × 1024, roughly 1 million
  • 2³⁰ = 1024 × 1024 × 1024, roughly 1 billion
• Logarithms
  • log_bx = y, means b^y = x, for any b > 1
  • log₁₀1000 = 3
  • log₂1024 = 10
  • log_bx = log_cx / log_cb, for any b > 1, c > 1
  • log₂10 is about 3.32
  • log_b(x^y) = y log_b x, for any b > 1
  • log_b(x y) = log_b x + log_b y, for any b > 1
  • log_b(x / y) = log_b x - log_b y, for any b > 1
• Formulae
  • Arithmetic Sum: (1 + 2 + ... + n) = n * (n+1) / 2
  • Geometric Sum: 1 + r + r² + r³ + ... + rⁿ = (rⁿ⁺¹-1) / (r-1)

Other Basics

• Boolean logic
  • Possible values - true, false - can mean on, off - often represented by 1, 0
  • and, or, not - read about in Khan academy
  • De Morgan's laws: not (A and B) is equivalent to (not A) or (not B). not (A or B) is equivalent to (not A) and (not B).
  • Distributing and over or (and vice versa): A and (B or C) is equivalent to (A and B) or (A and C). And, A or (B and C) is equivalent to (A or B) and (A or C).
  • Should be able to answer questions about truth tables for and / or / not, and evaluate expressions of and's / or's / not's
• Sets
  • De Morgan's laws: complement of (A ∪ B) = (complement of A) ∩ (complement of B). And, complement of (A ∩ B) = (complement of A) ∪ (complement of B).
  • Distributing ∩ over ∪ (and vice versa): A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). Also, A ∪ (B ∩ C) = (A ∩ B) ∪ (A ∩ C).
• Matrices
  • Indexing: For matrix A, A_{r, c} is the element in row r and column c
  • Matrix addition or subtraction: term-wise. Given matrices A, B, C with A + B = C, then C_{r, c} = A_{r, c} + B_{r, c}.
  • Matrix multiplication: Given matrices A, B, C with A * B = C, then C_{r, c} = r^th row of A times c^th column of B = A_{r, 1} * B_{1, c} + A_{r, 2} * B_{2, c} + ... A_{r, k} * B_{k, c}. Note that A*B is only defined if the number of columns of A is equal to the number of rows of B (e.g., A is an n by k matrix, and B is a k by m matrix).
  • Note that matrix multiplication is not commutative (it is not in general the case that A * B = B * A for matrices A and B).

Sizes of Sets

• Definitions for infinitely sized sets, uncountability of the reals

Assignment

You can practice these skills and knowledge with some of the quizzes at CS Learn and Assess. You may take similar quizzes for your course that will count for a grade.

Pass rating check You should earn at least 90% on each quiz for a pass rating, and should earn 100% for a pass+ rating. A score of 80% is a pass- rating. Note that these scores are based on (a) this information being relatively "easy" once you are comfortable with it, and (b) the information being very important to know well.

Other Assignments

Mathematics for Computer Science (MCS) contains many problems that are good practice. We have included some here, and some additional problems, which are good practice of different parts of math. Note that some of this material is taught in CS 303 and/or CS 600.

1. MCS Problem 3.38. This has you practice translating math statements in English into logical/math notation.
2. MCS Problem 4.1. This has you practice with power sets.
3. MCS Problem 4.16. This has you practice reasoning about relations, in particular the inverses of relations. Notes: a function is total if it is defined or all possible values of the right type (f(x) = sqrt(x) is not total over the real numbers). surjection is another name for onto, injection is another name for one to one, and bijection means both a surjection and injection.
4. Prove the following, which is claim 25 in the chapter on number theory in Building Blocks for Theoretical Computer Science (MCS): For any integers a, b, c, d, and k, k positive, if a ≡ b (mod k) and c ≡ d (mod k), then ac ≡ bd (mod k). The proof is similar to the proof of claim 24 just above claim 25 in MCS. This has you practicing using the definition of congruence modulo k and using the properties of the integers.
5. Use the inclusion-exclusion principle to determine how many numbers from 0 up to (and including) 899 are divisible by 2, or 3, or 5. You need to justify the steps of your argument. Properties you can use include: inclusion-exclusion principle on 2 or 3 sets, De Morgan's laws, distributing union over intersection, distributing intersection over union.
6. Write a python or C program to compute the value above (how many numbers 0 to 899 are divisible by at least one of - 2, 3, 5), and verify that you have the correct answer.
7. Consider 4 different sets W, X, Y, Z. Give the main argument for a proof of the inclusion-exclusion principle for these 4 sets. You only need to simplify the expression of |W union X union Y union Z| until you have it in terms of the sizes of each of the sets, pairwise intersections, intersections of three of the sets, intersection of all four. For each step, you need to indicate the reason for that step (De Morgan's laws, inclusion-exclusion (IE) for 2 or 3 sets, or some other reason).

Grading Notes

• Overall grading note - Remember to use good writing techniques and style. You need to explain clearly and in a logical way. You should not "just" show your work, you need to give a complete explanation of your solution that is enough for someone reading to check your work even if they had not solved the problem themself. For proofs, you need to justify each step in your proof, and "just" intuition is not enough.
• MCS 3.38
  • You need to follow the example given in the problem. You are only allowed to use: exists, forall, not, or, and, multiplication / addition, implication, equality tests
  • Any variables you use should be introduced with a quantifier (either exists or forall). But you should /not/ introduce n with a quantifier.
  • Whatever you come up with needs to work precisely for the right set of numbers (for part b it should work for any prime and not work for any composite).
• MCS 4.1
  • Part b - there are two items in the set here, so the powerset will have 4 items. They seem a bit odd, but things like {emptyset}, { {emptyset} }, {emptyset, {emptyset} } - these are perfectly fine sets.
• MCS 4.16
  • Hint - draw a graph that has the property on the left (but just that property, not the others), then rotate the graph by 90 degrees and what property does that one have?
  • Note - all of the answers on the right are different, so all of the options do get used: injection, surjection, function, total, bijection.
  • I did not ask for an explanation, but you should have one that convinces you that you have the right answers.
• BB Claim 25
  • First step is to write down what a = b mod k means, and the same for c = d mod k.
  • The goal is to show ac = bd mod k, so you should write down what that means as well.
• Inclusion-Exclusion for numbers up to 900.
  • How to set up this problem - what are the 3 sets?
  • I wanted you to indicate which rules you are using for each step in your argument, but I am giving credit even if you didn't.
  • Many people have their numbers off by 1. Note that 0 is a multiple of 2, 3, 5, and in general anything.
  • Check the formula for inclusion-exclusion for 3 sets, make sure you have it right.
• Program for inclusion-exclusion of numbers up to 900.
  • Many people had programs that computed the final count correctly, but also incorrectly reported the # of multiples of 2, 3, and 5. Check your logic to make sure...
• Inclusion-Exclusion of 4 sets
  • You are supposed to show how we derive the formula for 4 sets using things we already know: De Morgan's laws, distributing intersection over union (and union over intersection), and inclusion/exclusion for 3 and 2 sets.
  • Note that the assignment is not "just" to explain why the formula makes sense based on what it is for 2 and 3 sets. The assignment is to "prove" it.
  • You can check Building Blocks section 5.7 for how this is done for 3 sets. You will do something similar, but you also need to indicate for each step what rule you are using.