Math for CS Review

Note - Khan Academy Math is a good resource to look up and refresh general math knowledge. Khan Academy AP CS Principles and Khan Academy Computing also have some content related to math embedded within them.

Memorize

These are things you need to memorize.

• Order of operations: 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
  • 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
• Formulae
  • Arithmetic Sum: (1 + 2 + ... + n) = n * (n+1) / 2
  • Geometric Sum: 1 + r + r² + r³ + ... + rⁿ = (rⁿ⁺¹-1) / (r-1)
• 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).
  • Also, 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

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.
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.

1. 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.
2. 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.
3. 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).