Discrete Math

Question 1

Geometric Sequence

Answer 1

• a sequence of numbers where each number (after the first) is found by multiplying the previous number by some fixed value (common ratio)

Question 2

n^th term

Geometric Sequence

Answer 2

• Defines the n^th term in a geometric sequence
• In general, use formala starting at 1

Starting at 0

ar^{<span>n</span>}

Starting at 1

ar^n-1

Question 3

Geometric Series

Answer 3

• Sum of the first n terms
• In general, use formala starting at 1

Starting at 0

a(1 - rⁿ⁺¹)

(1 - r)

Starting at 1

a(1 - rⁿ)

(1 - r)

Question 4

Prime Number

Answer 4

A natural numbers that is:

1. Greater than 1
2. Only divisible by itself and 1

• cannot be negative
• must have exactly two factors

Question 5

Composite Number

Answer 5

• a natural, non-prime number

Question 6

Trial Division

Answer 6

• Used to find factors of a number N

Steps

1. Create an output list
2. Loop from 1 - √N (inclusive)
3. Check if N%i == 0
4. If so, add i, and its cofactor to output list

Question 7

cofactor

Answer 7

• factors always exist in pairs
• given factor a, the cofactor is the other factor b s.t. a*b=c
• cofactor may be same as factor (6² == 36)

Question 8

Sieve of Eratosthenes

Answer 8

• Ancient algorithm for finding all prmes less than some number

Steps

• Create a boolean array from 0 to N
• Set all entries to True (mark every number as prime)
• Set 0, 1 to false (they aren’t prime)
• Start looping from 2 to root N
• Find all multiples of i (starting at i^2), mark as false (they are composite)
• Use indices to get primality of a number

Complexity

Time

O( n log log n)

Space

O(n)

*Time complexity is based on fancy math

Question 9

Prime Factorization

Answer 9

• Writing the factors of a number with only primes
• Only one possible prime factorization of a number
• Often written with exponents

Steps

1. Start looping from 2 to √N
2. At each i, while n%i ==0
3. Divide n by i
4. Increase count (number of i’s in n)
5. Return to outer loop
6. If N != 1 after loop, N must be a prime number
7. Add N (frequency 1) to the output

Question 10

GCD

Euclidean Algorithm

Answer 10

• gcd is the largest number that evenly divides two numbers
• euclidean algorithm fast technique for finding gcd of a numbers a and b
• usually implemented recursively
• generally assume (or position) a > b
• note: if two numbers (a, b) share a factor, then their difference (a-b) also shares a factor
• ergo, if two numbers (a, b) share a factor, then their remainder (a%b) also shares a factor

Steps

1. Assuming a > b
2. If b == 0, return a
3. Otherwise, return gcd(b, a%b)

Question 11

cardinality

[set theory]

Answer 11

• The cardinality of a set is the number of elements in a set
• Syntax is the same as for absolute value

Syntax:

If set A has 5 elements, then:

|A| = cardinality of A = 5

Question 12

intersection

(set theory)

Answer 12

• A ∩ B are the elements in both A and B

Question 13

union

[set theory]

Answer 13

• A ∪ B is the elements in X or Y
• Combination of the two sets

Question 14

symmetric difference

[set theory]

Answer 14

• A ∆ B are the elements that A and B don’t share
• Everything other than the overlap in a venn diagram

Question 15

complement

[set theory]

Answer 15

• all the things that are not in A

2 definitions

1. relative complement (difference)
2. absolute complement

Question 16

relative complement

[set theory]

Answer 16

• A\B is the relative complement of B in A
• everything in A with B taken out
• also written as A - B, the difference of sets A and B

Question 17

absolute complement

[set theory]

Answer 17

• A’ is everything in the universe that isn’t in A

Question 18

induction

Answer 18

• mathentical proof technique used to show that something is true for all positive integer numbers greater than or equal to some integer N

3 steps

1. Base Case
   
   • Prove the statement for the first term
2. Construct Inductive Hypothesis
   
   • Assume something is true for every case n <= k
3. Prove k+1 holds
   
   • If the first step is true, and an arbtrary step is true, then the entire statement must be true

Question 19

irrational number

Answer 19

• a number that cannot be expressed by a ratio of two integers
• decimal never repeats
• ex: pi

Question 20

Subtraction/Division

Answer 20

Given (x-a)

• how many a’s are in x
• x/a is the number of times you can subtract a from x and keep x positive (while x >= 0)