Midterm Concepts Flashcards by Michael Joshua Slain

What does the symbol ∅ represent?

A set with no elements

How well did you know this?

Not at all

Perfectly

What is the difference ⊆ and ⊂?

A subset ⊆ may equal the original set,
while a proper subset ⊂ must be strictly smaller than the original set

How well did you know this?

Not at all

Perfectly

What is the intersection (∩) of sets?

Elements that belong to both sets

How well did you know this?

Not at all

Perfectly

What is the union (∪) of sets?

Elements that belong to either set or both

How well did you know this?

Not at all

Perfectly

What is the difference (B \ A) of sets?

Elements in B that are not in A

How well did you know this?

Not at all

Perfectly

What is the Cartesian/cross product (A × B)?

The set of all ordered pairs (a,b) where a ∈ A and b ∈ B

How well did you know this?

Not at all

Perfectly

What is the power set P(S)?

The set of all possible subsets of S

How well did you know this?

Not at all

Perfectly

What is the size of power set P(S)?

2^|S|

How well did you know this?

Not at all

Perfectly

What does N represent in set notation?

Natural numbers

How well did you know this?

Not at all

Perfectly

What does Z represent in set notation?

Integers

How well did you know this?

Not at all

Perfectly

What does Q represent?

Rational numbers

How well did you know this?

Not at all

Perfectly

What does R represent in set notation?

Real numbers

How well did you know this?

Not at all

Perfectly

What does C represent in set notation?

Complex numbers

How well did you know this?

Not at all

Perfectly

What does ∑ represent?

The addition of a sequence of numbers

How well did you know this?

Not at all

Perfectly

What does the product ∏ notation represent?

The multiplication of a sequence of numbers

How well did you know this?

Not at all

Perfectly

What does ∀ mean?

For all elements

How well did you know this?

Not at all

Perfectly

What does ∃ mean?

There exists at least one element

How well did you know this?

Not at all

Perfectly

What is a proposition in logic?

A statement that has exactly one truth value (true or false)

How well did you know this?

Not at all

Perfectly

What is a tautology?

A compound proposition that is always true regardless of the truth values of its components

How well did you know this?

Not at all

Perfectly

What is a contradiction?

A compound proposition that is always false regardless of the truth values of its components

How well did you know this?

Not at all

Perfectly

What is conjunction ∧?

Logical AND - true only when both statements are true

How well did you know this?

Not at all

Perfectly

What is ∨?

How well did you know this?

Not at all

Perfectly

What is ¬?

NOT - reverses the truth value of a statement

How well did you know this?

Not at all

Perfectly

What is implication (P ⟹ Q)?

If P then Q - only false when P is true and Q is false

How well did you know this?

Not at all

Perfectly

What is the equivalent form of implication `(P ⟹ Q)`?

`¬P ∨ Q`

What is biconditional (P ⟺ Q)?

P if and only if Q - true when P and Q have the same truth value

What is the contrapositive of `P ⟹ Q`?

`¬Q ⟹ ¬P` - logically equivalent to the original implication

What is the converse of `P ⟹ Q`?

`Q ⟹ P ` - NOT logically equivalent to the original implication

What is vacuous truth?

An implication that is true because its hypothesis (P) is false

What is the negation of `∀x P(x)`?

`∃x ¬P(x)`

What is the negation of `∃x P(x)`?

`∀x ¬P(x)`

What is De Morgan's Law for `¬(P ∧ Q)`?

`¬P ∨ ¬Q`

What is De Morgan's Law for `¬(P ∨ Q)`?

`¬P ∧ ¬Q`

What is a direct proof?

Assume `P`, show series of steps to reach `Q` for statements of form `P → Q`

What is a proof by contraposition?

Prove `¬Q → ¬P` instead of `P → Q`

What is a proof by contradiction?

Assume `¬P`, derive contradiction (`R` and `¬R`)

What is a proof by cases?

Divide into exhaustive cases, prove each separately

How do you prove an 'if and only if' statement?

Prove both `P → Q` and `Q → P` separately

What is a non-constructive proof?

Prove existence without explicit construction

What are the steps in simple/weak induction?

1) Base case: Prove `P(0)` or `P(1)`, 2) Induction hypothesis: Assume `P(k)`, 3) Inductive step: Prove `P(k+1)` from `P(k)`

What is strong induction?

Assume `P(0), P(1),..., P(k)` are all true, then prove `P(k+1)`

What is a stable matching?

A matching with no rogue couple (pair who would both prefer each other over current matches)

What does the Propose-and-Reject Algorithm (Gale-Shapley) produce?

A stable matching that is proposer-optimal

What is an Eulerian tour?

A path that traverses each edge exactly once and returns to the starting vertex

When does a connected graph have an Eulerian tour?

If and only if all vertices have even degree

What is a tree in graph theory?

A connected, acyclic graph

What is Euler's Formula for planar graphs?

`v + f = e + 2`

What is a corollary of Euler's Formula for planar graphs with `v ≥ 3`?

`e ≤ 3v - 6`

What are examples of non-planar graphs?

K₅ (complete graph on 5 vertices) and K₃,₃ (complete bipartite graph with 3 vertices in each part)

What is a bipartite graph?

A graph whose vertices can be divided into two disjoint sets such that no edge connects vertices in the same set

What does `x ≡ y (mod m)` mean?

`m` divides `(x-y)`

When does a number have a multiplicative inverse in modular arithmetic?

If and only if `gcd(x, m) = 1`

How is `gcd(x, y)` computed in Euclid's Algorithm?

`gcd(x, y) = gcd(y, x mod y)`

What does the Extended Euclid's Algorithm find?

Coefficients `a`, `b` where `gcd(x, y) = ax + by`

What does the Chinese Remainder Theorem address?

System `x ≡ aᵢ (mod nᵢ)` has unique solution `mod N = n₁·n₂·...·nₖ` when `nᵢ`'s are coprime

What are the components of the RSA public key?

`(N, e)` - `N = p × q` - `e` is coprime to `(p-1)(q-1)` (`p` and `q` are prime)

What is the RSA private key?

`d` where `d·e ≡ 1 [mod (p-1)(q-1)]`

How is a message encrypted in RSA?

E(x) ≡ x^e (mod N)

How is a message decrypted in RSA?

`D(y) ≡ y^d (mod N)`

What does Fermat's Little Theorem state?

If `p` is prime and `p` doesn't divide `a`, then: `a^(p-1) ≡ 1 (mod p)`

How many roots can a non-zero polynomial of degree d have?

At most d roots

What is the uniqueness property of polynomial interpolation?

Given `d+1` points, there exists a unique polynomial of `degree ≤ d` passing through them

How many possible polynomials of degree ≤ d exist over a field with m elements?

m^(d+1)

How does Shamir's secret sharing scheme work?

Create polynomial P with P(0) = secret; any k participants can reconstruct P(x) using Lagrange interpolation

What's the difference between erasure errors and general errors?

Erasure errors: - known positions - needs `n+k` packets General errors: - unknown positions - needs `n+2k` packets

How many different ways are there to arrange n distinct objects?

`n!`

What is the formula for the binomial coefficient (`n` choose `k`)?

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

What does the Binomial Theorem state?

`(a+b)^n = Σ (n k) * a^k * b^{n-k}`

What is the sum of all binomial coefficients for a given `n`?

`2^n`

What makes a set countable?

It can be put in one-to-one correspondence with the natural numbers or a subset of the natural numbers

What makes a set uncountable?

It cannot be put in one-to-one correspondence with the natural numbers

Which of these sets are countable: `ℕ, ℤ, ℚ`?

All of them

Which of these sets are uncountable: ℝ, P(ℕ)?

Both are uncountable: real numbers (ℝ) and the power set of natural numbers P(ℕ)

What technique is used to prove a set is uncountable?

Cantor's diagonalization

What is the cardinality of the power set `P(S)` in terms of `|S|`?

`|P(S)| = 2^|S|`