Brown Cs022 Final

Front 1

Other forms of a ≡ b (mod m)

Back 1

a = b + mk

m | (a - b)

Front 2

Properties of a ≡ b (mod m) which arise from congruence relation.

Properties when we consider c ≡ d (mod m) as well.

Back 2

aⁿ ≡ bⁿ (mod m) for any positive integer n

a + n ≡ b + n (mod m) for any integer n

an ≡ bn (mod m) for any integer n

a + c ≡ b + d (mod m)

ac ≡ bd (mod m)

Front 3

The congruence ax ≡ c (mod m) has a solution if and only if...

Back 3

gcd(a,m) | c

Front 4

Fermat's Little Theorem

Back 4

If p is prime and gcd(a,p) = 1, then

a^(p-1) ≡ 1 (mod p)

Multiply by a: a^p ≡ a (mod p)

Front 5

Modular Inverse

Back 5

The solution to the congruence ax ≡ 1 (mod m).

Always (but not only) exists if gcd(a, m) = 1.

Front 6

Euler's Phi (Totient) Function

Back 6

Counts the number of integers from 1 to n (inclusive) that are relatively prime to n.

If gcd(a,m) = 1, then a^phi(m) ≡ 1 (mod m).

If p and q are distinct primes, then

phi(pq) = (p - 1)(q - 1)

Front 7

Relatively Prime

Back 7

gcd(a,b) = 1

Front 8

How to set up a private and public RSA key

Back 8

1) Choose 2 distinct large primes p and q

2) Find k s.t. k < phi(pq) and gcd(k, phi(pq)) = 1

3) Find d s.t. kd ≡ 1 (mod phi(pq))

4) Keep d private, make k and n = pq public.

Front 9

How to send an RSA-encrypted message

Back 9

1) Map the message to numbers (less than n)

2) For each number m, compute m^k ≡ r (mod n) where r < n

3) Send r

Front 10

How to decrypt an RSA-encrypted message

Back 10

Given encoded message r and private key d:

r^d ≡ x (mod n) where x < n

Front 11

Given a proposition p implies q, we can derive what three named expressions?

Back 11

The converse: q implies p. {T,T,F,T}

The inverse: NOT p implies NOT q. {T,T,F,T}

The contrapositive: NOT q implies NOT p. {T,F,T,T}

Front 12

Tautology

Back 12

A proposition that is always true (e.g. x OR NOT x)

Front 13

Contradiction

Back 13

A proposition that is always false (e.g. x AND NOT x)

Front 14

Binomial Theorem

Back 14

(a + b)^n = ∑ from k = 0 to n of (n choose k) a^k * b^(n - k)

Front 15

The number of functions from domain X to codomain Y

Back 15

|Y|^(|X|)

Front 16

The number of injective functions from domain X to codomain Y

Back 16

|Y|! / (|Y| - |X|)!

Only if |Y| ≥ |X|

Front 17

The number of bijections from domain X to codomain Y

Back 17

|Y|!

...but |X| must be equal to |Y|

Front 18

Formula for (n choose k)

Back 18

n!/(k! (n - k)!)

Front 19

3 properties of the binomial coefficient (n choose k)

Back 19

1) (n choose k) = (n choose n - k)

2) ∑ from k = 0 to n of (n choose k) = 2ⁿ

3) (n choose k) = (n - 1 choose k) + (n - 1 choose k - 1)

Front 20

Meanings of (n choose k)

Back 20

The number of subsets of size k of a set n, with no ordering.

The number of ways to pick k objects from n objects.

Front 21

Steps of the Euclidean Algorithm to compute gcd(a,b)

Back 21

Let a be the greater number and b be the lesser

1) a = __*b + r

2) Solve for b and r, shift left

3) Repeat until r = 0, then the previous r = GCD

Front 22

Steps of the Extended Euclidean Algorithm

Back 22

1) Complete the Euclidean Algorithm

2) Rearrange the last equation s.t. you have 1 = __*n + r₁

3) Rearrange the next equation s.t. you get n = __*__ + r₂ and then substitute back in

4) Continue until you have 1 in terms of a and b

Front 23

Defintion of a Derangement

Back 23

A derangement is a permutation with no fixed points

Front 24

Set Operations

Back 24

A ∪ B => Union => all items in A and B (all 1s)

A ∩ B => Intersection => Items in both A and B

A \ B => Set Minus => Items in A and not in B

Front 25

Power Set [P(A)]

Back 25

The set of all subsets of A. Size is 2^|A|. Includes {} and A.

Front 26

Cartesian Product [A x B]

Back 26

Set containing ordered pairs of every combination of elements from the two sets.

e.g. {(a₁, b₁), (a₁, b₂), (a₂, b₁), ... }

Front 27

Properties of an equivalence relation

Back 27

Reflexive: aRa for all a (every element must be related to itself)

Symmetric: aRb => bRa

Transitive: aRb and bRc => aRc (e.g. a < b and b < c then a < c)

Front 28

Equivalence classes

Back 28

Equivalence classes partition a set into distinct classes of related items.

The equivalence class containing a in the relation R is written as [a]_R

An example: 8 mod 3 is in the equivalence class of 2

Front 29

Injective function

Back 29

If a ≠ b, then f(a) ≠ f(b)

In other words, only one input → one output

Front 30

Surjective Function

Back 30

∀x ∈ X ∃ a ∈ A s.t. f(a) = x

where X is the codomain and A is the domain

In other words, every output → some input

Front 31

Bijective Function

Back 31

A function that is both injective and surjective.

If a function is bijective, then the domain and the codomain have the same size.

Front 32

Permutation

Back 32

The number of ways to order unique elements of a set

n!

Front 33

Combination

Back 33

The number of ways to pick some number of unique elements from a set, where order does not matter

n! / (k! (n-k)!)

Front 34

Pigeonhole Principle

Back 34

Weak: Given n buckets and n + 1 things, there must exist a bucket with at least 2 things in it

Strong: Given Kn + 1 items and n buckets, there must exist a bucket with at least K + 1 things in it

Front 35

Stars and Bars

Back 35

Ways to partition n indistinguishable objects into k categories

If every category must have at least one member: (n - 1) Choose (k - 1)

If empty categories are allowed: (n + (k - 1)) Choose (k - 1)

Front 36

Big O

Back 36

Upper bound on a function's growth

Front 37

Big θ

Back 37

Tight bound on a function's growth (f(x) * C₁ is greater than the function, f(x) * C₂ is less than the function)

Front 38

Big Omega:

Back 38

Lower bound on a function's growth

Front 39

Probability of an event

Back 39

|E| / |S| (where E is the number of event(s) we want to occur and S is the total of possible events)

Front 40

Bayes' Law

Back 40

Standard: P(A|B) = (P(A) * P(B|A))/P(B)

Extended: P(A|B) = P(A) * P(B|A)

P(A) * P(B|A) + P(NOT(A)) * P(B|NOT(A))

...but ONLY if A and B are independent!!

Front 41

P(A and B)

Back 41

P(A) * P(B) if A and B are independent

P(A) * P(B|A) otherwise

Front 42

Expectation of a random variable

Back 42

The expectation of a random variable X is the value X will take on average

E[X] = ∑X * P(X = x) for all x in A

Front 43

Variance of a random variable

Back 43

The variance of a random variable X tells on average how far away the actual value of X will be from the expected value of X, E[X]

V(X) = E[X²] - E[X]²

Front 44

Linearity of Expectation

Back 44

E[A + B] = E[A] + E[B]

**This works even when A and B are dependent!

Front 45

Linearity of Variance

Back 45

V(A + B) = E[(A + B)²] + E[A + B]² if dependent

V(A + B) = V(A) + V(B) if independent

Front 46

Binomial distribution

Back 46

A probability which can be modeled by a 0/1 string (e.g. a series of coin flips). Each event (coin flip) must be INDEPENDENT from the last.

If P if the probability of a success in a binomial distribution, 1 - P is the probability of a failure

Front 47

Expectation and Variance for Binomial Distributions

Back 47

E[X] = np (where n is the number of trials and p is the probability of success)

V(X) = np(1 - p)

Front 48

Markov's Inequality

Back 48

P(X ≥ a) ≤ E[X] / a

Front 49

Chebyshev's Inequality

Back 49

P(|X - E[X]| ≥ a) ≤ V(X) / a²

Front 50

Total degree of a graph

Back 50

2|E| (2 times the number of edges)

Front 51

Degree of a vertex

Back 51

The number of edges that connect to that vertex

Front 52

Properties of a Tree

Back 52

v - 1 edges, fully connected (no loose nodes or portions of the graph which do not connect to other portions), acyclic

Front 53

Planar Graphs

Back 53

Graphs that can be drawn on a plane without any lines crossing each other.

|E| ≤ 3|V| - 6

Front 54

Eulerian Cycle

Back 54

A path through a graph which visits every edge only once and returns to its starting point

Front 55

Hamiltonian Cycle

Back 55

A path through a graph which visits every vertex only once and returns to its starting point

Front 56

Complete Graph

Back 56

A graph which has an edge between every single point on it