# This site is now deprecated Go to [notes.bencuan.me](https://notes.bencuan.me/cs70) for the latest version! # LaTeX Reference A list of frequently used mathematical notation bits. ### Basics | Symbol | Description | LaTeX | | ------------------------ | ------------------------ | --------------------- | | $$\cdot$$ | Multiplication dot | `\cdot` | | $$\cdots$$ | Dots | `\cdots` | | $$\frac{x}{y}$$ | Fraction | `\frac{x}{y}` | | $$\ge$$ | Greater than or equal to | `\ge` | | $$\le$$ | Less than or equal to | `\le` | | $$\ne$$ | Not equal to | `\ne` | | $$\sum\_{i=0}^{n}$$ | Summation | `\sum_{i=0}^{n}` | | $$\infty$$ | Infinity | `\infty` | | $$\lim\_{x \to \infty}$$ | Limit | `\lim_{x \to \infty}` | ### Propositional Logic | Symbol | Description | LaTeX | | ------------ | ------------------- | ---------- | | $$\implies$$ | Implication | `\implies` | | $$\iff$$ | Logical equivalence | `\iff` | | $$\equiv$$ | Congruence | `\equiv` | | $$\exists$$ | Existence | `\exists` | | $$\in$$ | Inclusion | `\in` | | $$\land$$ | Conjunction (and) | `\land` | | $$\lor$$ | Disjunction (or) | `\lor` | | $$\lnot$$ | Negation (not) | `\lnot` | | $$\forall$$ | For all | `\forall` | | $$\oplus$$ | Exclusive or (xor) | `\oplus` | ### Sets | Symbol | Description | LaTeX | | --------------- | ---------------------- | ------------- | | $$\mathbb{C}$$ | Complex numbers | `\mathbb{C}` | | $$\mathbb{R}$$ | Real numbers | `\mathbb{R}` | | $$\mathbb{Q}$$ | Rational numbers | `\mathbb{Q}` | | $$\mathbb{Z}$$ | Integers | `\mathbb{Z}` | | $$\mathbb{N}$$ | Natural numbers | `\mathbb{N}` | | $$\mathscr{P}$$ | Power set | `\mathscr{P}` | | $$\cup$$ | Union (set or) | `\cup` | | $$\cap$$ | Intersection (set and) | `\cap` | | $$\emptyset$$ | Empty Set | `\emptyset` | | $$\setminus$$ | Set Division | `\setminus` | | $$\subseteq$$ | Subset (inclusive) | `\subseteq` | ### Modular Arithmetic | Symbol | Description | LaTeX | | -------------- | --------------------- | ---------- | | $$p \mod q$$ | Modulo | `\mod` | | $$p \pmod{q}$$ | Modulo in parentheses | `\pmod{q}` | # Overview ## What even is discrete math? According to [Wikipedia](https://en.wikipedia.org/wiki/Discrete_mathematics), "*Discrete mathematics* is the study of mathematical structures that are fundamentally discrete rather than continuous." Very helpful, thank you Wikipedia. The floor is indeed made of floor rather than sky. The word **discrete** means "distinct" or "countable". This suggests that discrete math has to do with **countable numbers** like integers, rather than the continuous $$f(x)$$functions we're used to seeing that are defined for any real$$x$$, even ones we don't know the exact value of like $$\pi$$. Dealing with countable integers is nice because **that's how computers work.** Behind the scenes, every floating point number is actually just a whole bunch of bits, which are countable :) I would say that dealing with integers makes things nicer too (since we no longer have to deal with decimals), but you might be inclined to disagree. ## A brief summary of the contents covered Discrete math is an extremely wide field of mathematics. Here, we'll be covering the basics as well as a few important applications: * [**Propositional logic**](/discrete-math/propositional-logic) and sets give us the **language** we need to talk about discrete math. * [**Proofs**](/discrete-math/proofs) allow us to demonstrate **how** and **why** things work the way they do. * [**Stable Matching**](/discrete-math/stable-matching) explores how we can apply sets to create optimal matches between two groups with preferences. * [**Graph theory** ](/discrete-math/graphs)provides a highly visual representation of a wide variety of mathematical relationships using vertices, edges, and faces. One of the most important concepts here is **Euler's Formula** which relates the number of vertices, edges, and faces together. * [**Modular arithmetic** ](/discrete-math/modular-arithmetic)explores what happens when when all numbers are remainders of dividing itself by another number. There are some really important theorems here, like the **Chinese Remainder Theorem, Euclid's Algorithm,** and **Fermat's Little Theorem.** * [**RSA Cryptography**](/discrete-math/rsa-cryptography) is an interesting application of how modular arithmetic is used to encrypt and decrypt messages using a public-private key pair. * [**Polynomials** ](/discrete-math/polynomials)can be used in a discrete sense to create **secret sharing** schemes, and can be recovered from points using **Lagrange Interpolation.** # Propositional Logic ## What are Propositions? Propositions are anything that can be **true** or **false.** This could include: * Statements like "Birds can fly". * Well defined equations with no free variables like $$1 + 1 = 3$$. Propositions are **not:** * Variables like $$x$$ or $$5$$. * Equations with free variables like $$P(x) = y$$. * Statements that aren't clearly true or false, like "I like trains." ### Connectives Simple propositions can be **joined together** to make complex statements. There are three basic ways to connect propositions together: * **Conjunction** is the **and** operation: for $$P \land Q$$to be true, $$P$$and $$Q$$must **both** be true. * **Disjunction** is the **or** operation: for $$P \lor Q$$to be true, **either** $$P$$or $$Q$$must be true. * **Negation** is the **not** operation: if $$P$$is true, then $$\lnot P$$is false. * The **law of the excluded middle** states that $$P$$and $$\lnot P$$ *cannot both be true.* One example where we can see these components in action is in **De Morgan's Laws**, which state how negation can be **distributed** across conjunction or disjunction: $$ \lnot(P \lor Q) \iff (\lnot P \land \lnot Q) $$ "If neither P nor Q are true, then P and Q must both be false." $$ \lnot(\forall x)(P(x)) \iff (\exists x)(\lnot P(x)) $$ "If P(x) isn't true for every x, then there exists an x where P(x) is false." *** Another example of distribution is this congruence, which works for any combination of and's and or's. $$ (P \lor Q) \land R \equiv (P \land R) \lor (Q \land R) $$ *** ### Implication One proposition can **imply** another, which looks like this: $$ P \implies Q $$ Roughly, implication in plain English can be stated in the form **if P, then Q.** However, there are a lot of nuances to what this really means! #### Properties of Implication * **Reversible:** Q is true if P is true. However, be careful- *this doesn't necessary mean that Q implies P!* * **P is sufficient for Q:** Proving P allows us to say that Q is also true. * **Q is necessary for P:** For P to be true, it is necessary that Q is true. (If Q is false, then P is also false.) * **Contrapositive Equivalence:** If P implies Q, then $$\lnot Q \implies \lnot P$$. * Note that this is different from the **converse**, which is $$Q \implies P$$. This statement is **not logically equivalent!** #### Truth Table | P | Q | P $$\implies$$Q | P $$\iff$$Q | | - | - | --------------- | ----------- | | T | T | T | T | | T | F | F | F | | F | T | T | F | | F | F | T | T | **Note that the truth table for** $$P \implies Q$$ **is equivalent to the one for** $$\lnot P \lor Q$$**!** That means this formula is logically the same as $$P \implies Q$$. (If two propositions have the same truth table, then they are logically equivalent. However, it's still possible for a proposition to imply another even if their truth tables are different!) ### Quantifiers Sometimes, we need to define a specific type of variable to work with in a propositional clause. For instance, take the proposition, *"There exists a natural number that is equal to the square of itself."* We could write this as: $$ (\exists x \in \mathbb{N})(x=x^2) $$ You could think about the parentheses almost like defining a **scope** of variables, like what might happen in programming! Here, the first clause is *defining* an arbitrary variable $$x$$to be any natural number. ## Exercises {% tabs %} {% tab title="Q1" %} Is the expression $$\forall x \exists y (Q(x,y) \implies P(x))$$equivalent to the expression $$\forall x ((\exists y \ Q(x,y)) \implies P(x))$$?\ (Source: Discussion 0 2a) {% endtab %} {% tab title="Answer 1" %} **No**, they are not equivalent. We can see this more clearly by converting the implication $$Q \implies P$$ to $$\lnot Q \lor P$$ as was demonstrated in the Truth Table section above.\ \ On the left side, this conversion is straightforward, yielding $$\forall x \exists y (\lnot Q(x,y) \lor P(x))$$. On the right side, we'll need to invoke De Morgan's Laws to convert the 'exists' into a 'for all' since it was negated. This yields $$\forall x (\forall y\lnot(Q(x,y)) \lor P(x))$$which is not the same thing! {% endtab %} {% endtabs %} {% tabs %} {% tab title="Q2" %} An integer $$a$$is said to *divide* another integer $$b$$ if $$a$$is a multiple of $$b$$. Write this idea out using propositional logic (a divides b can be written as $$a \mid b$$). **Note:** This idea is going to be important for a lot of future sections! {% endtab %} {% tab title="Answer 2" %} $$a \mid b \iff (\exists q \in \mathbb{Z})(a = qb)$$ In plain English: "There exists an integer $$q$$such that when we multiply $$q$$with $$b$$, we get $$a$$." {% endtab %} {% endtabs %} ## Resources Note 1: \ Discussion 0: # Proofs ## Introduction A **proof** is a **set of logical deductions** that can be used to show how something is true. This is powerful because proofs can often be very **general,** allowing a truth to be used in a whole bunch of cases that don't individually need to be re-proven. There are a number of common proof techniques (although these certainly aren't exhaustive!) outlined below. ## Direct Proofs In direct proofs, we can use the **definitions** directly to show that something is true. No trickery here, just straightforward navigation from point A to point B. **Direct Proof Form:** * **Goal:** $$P \iff Q$$\*\*\*\* * **Assume P.** * Do a bunch of steps using the definitions and assumptions created by the values and operators used. * **Therefore Q.** **Example:** Let $$D\_3$$be the set of 3 digit natural numbers. Show that for all $$n \in D\_3$$, if the alternating sum of digits of $$n$$is divisible by 11, then $$11 \mid n$$. (Lecture 2) * First, let's make sure this makes sense. Let's try some examples: * if $$n=605$$, then $$n$$is divisible by 11. Its alternate sum is $$6 - 0 + 5 = 11$$. $$11$$is indeed divisible by 11, so this looks like it could be true! * Next, let's write this in propositional logic: * $$\forall n \in D\_3, (11 \mid \mbox{alt sum of digits of n}) \implies 11 \mid n$$ * Now, let's try to prove it starting with assuming that all $$n$$ are 3 digit natural numbers. * Let $$a, b,$$and $$c$$ represent the three digits of $$n$$such that $$n = 100a + 10b + c$$. * If the alternating sum of digits is divisible by 11, then $$11 \mid a - b + c$$. * Using the definition of division, $$a - b + c = 11k$$for some natural number k. We're trying to prove that $$n = 100a + 10b + c = 11m$$for another integer $$m$$as well! * Solve for $$c$$using the alternating sum to get $$c = 11k + b - a$$. Substitute this value into the second equation to get $$100a + 10b + 11k + b - a = 11m$$. Simplifying, this equation is equivalent to $$99a + 11b + 11k = 11m$$. * We know that **this must be true** because each individual term is multiplied by a number divisible by 11. Therefore, the entire number must also be divisible by 11. ## Proof by Contraposition As a reminder, the **contrapositive** of a statement $$P \implies Q$$is $$\lnot Q \implies \lnot P$$. **These two statements are logically equivalent!** Sometimes, it's easier to prove the contrapositive, which would in turn prove the original statement. **Contraposition Form:** * **Goal:** $$P \implies Q$$\*\*\*\* * **Assume** $$\lnot Q$$. * Do a bunch of steps using another type of proof. * **Therefore** $$\lnot P$$. **Example:** For every $$n \in \mathbb{N}, n^2 \mbox{even} \implies n \mbox {even}$$ * If we try proving using a direct proof, we'll have to deal with the squared term (and square roots)! This might get nasty; we'd rather deal with the nicer right side. * First, let's find the **contrapositive of Q.** Q is "n is even", so the contrapositive is "n is odd". * Then, let's find the contrapositive of P. P is "n squared is even", so the contrapositive is "n squared is odd". * Let's use the definition of an odd number ($$n = 2k + 1$$for some natural number k) to work through this. * If $$n = 2k +1$$, then $$n^2 = 4k^2 + 4k + 1$$ = $$2(2k^2 + 2k) + 1$$. * Since this is also the form of an odd number, $$n^2$$must be odd! ## Proof by Contradiction Instead of proving that $$P$$is true, maybe we could show that $$\lnot P$$makes no sense at all! (We know that if $$\lnot P$$is false, then $$P$$must be true.) Contradiction is a great choice for proving things that have **infinitely many cases** (since you can just prove the opposite, which is finite!). **Contradiction Form:** * **Goal:** $$P \implies Q$$\*\*\*\* * **Assume** $$\lnot P$$. * Do some steps here. * **Therefore,** $$\lnot P$$**is a contradiction.** **Example:** Show that there are infinitely many prime numbers. * First, let's assume the opposite - that there are a finite number of prime numbers, which can be represented by the set $${ p\_1, \cdots, p\_k}$$. * Let's define a number $$q = (p\_1 \times p\_2 \cdots \times p\_k) + 1.$$ * Since $$q$$is larger than any prime number in our set, it can't be a prime number by our assumption. Note that we **did not prove that**$$q = (p\_1 \times p\_2 \cdots \times p\_k) + 1$$**is a prime number!** This is because we started with a false statement, so everything in the middle of a contradiction proof cannot be generalized to true statements. ## Proof by Cases Sometimes, we can break a statement down into smaller **cases** and prove each one individually. These cases could be something like "a is odd" and "a is even", where it is impossible for any other case to be true. If all possible cases are proven, then the entire statement is then proven. **Example:** Show that there exists an irrational x and y such that $$x^y$$is rational. * First, let's find some cases. The two cases could be that $$x^y$$is rational or $$x^y$$is irrational. If $$x^y$$is rational (the first case is true), then we're done! But if the second case is true, then we're back to where we started. * Since all we need to do is show existence, we can choose any irrational number for x and y. $$\sqrt{2}$$seems like an easy choice! * $$\sqrt{2}^{\sqrt{2}}$$is irrational, but what about $$(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}}$$? That's just $$2$$! ## Proof by Induction Induction is great for proving that something is true for everything in a set (often the natural numbers). If we prove the first value, then prove that the next value is true, then the value after that is *also* true, and so on. This can be likened to the **domino effect.** If the first one's true, then it knocks down the domino for the next value. If that's true, then it knocks out the next one, and so on until every possible value is covered. **Induction Form** * **Prove P(0).** (Base case) * **Assume P(k).** (Induction Hypothesis) * **Prove P(k+1).** (Induction Step) * When proving the induction step, we can treat the induction hypothesis as a true statement! **Example: The Two Color Theorem** Here's a visually intuitive example of induction in action! The Two Color Theorem states that for any collection of intersecting line segments, the regions that they divide can be assigned one of two colors such that a line never has the same color on both sides. In order to prove this, let's start at the **base case**, where there is only one line: ![](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFka3X4qx2R0yzli0Ke%2F-MGJkQseqD7Oaie5Ka5_%2F-MGJkWpTZ5-8x64ZiZGm%2Fimage.png?alt=media\&token=1fd9396a-edcc-489c-add2-9d15abc42bc5) Here, it's pretty clear that it is indeed possible to put a different color on each side of the line, in this case let's just choose blue and red. Now, let's see what happens when we add a new line: ![](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFka3X4qx2R0yzli0Ke%2F-MGJkQseqD7Oaie5Ka5_%2F-MGJkcmC5xg9KZbkGG96%2Fimage.png?alt=media\&token=9679fbbd-fa4f-450b-a010-612dd4c84654) Looks like we have a conflict now! The blues on the top and reds on the bottom are touching. However, it's not too hard to fix this. Let's just flip the blue and red on one of the sides: ![](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFka3X4qx2R0yzli0Ke%2F-MGJkQseqD7Oaie5Ka5_%2F-MGJksHN6enQDAGN7KNk%2Fimage.png?alt=media\&token=3d723ec5-a27b-469b-9d8a-c4dcfb1269cf) It turns out that this process: drawing a new line and flipping all of the colors on one side, works in any configuration of lines! This is because of the fact that flipping the colors on one side of a line doesn't affect whether or not those colors are alternating. ![](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFka3X4qx2R0yzli0Ke%2F-MGJkQseqD7Oaie5Ka5_%2F-MGJkxEAV8YT_R1Y4YRq%2Fimage.png?alt=media\&token=0ac186c7-d485-4063-aa3f-c712ef2b116a) ### Stronger Induction Sometimes, an inductive proof can be rather elusive. It might be easier to **make the statement stronger** and prove that instead! (It should make sense that a stronger argument means that a weaker argument is also true.) For example, take the statement "The sum of the first *n* odd numbers is the square of a natural number." As we try to figure out a pattern, we might notice something: > For n = 1: $$1 = 1^2 = n^2$$ > > For n = 2: $$1 + 3 = 2^2 = n^2$$ > > For n = 3: $$1 + 3 + 5 = 3^2 = n^2$$ Wow, looks like not only is the sum equal to some arbitrary square number, but it's actually equal to $$n^2$$! It's a lot easier to prove this fact than the original one, and proving this completely includes the original statement. Another (aptly named) principle that might come in handy is the **Strong Induction Principle!** This principle is useful for when you don't want your base case to be $$0$$. The Strong Induction Principle states that if we prove all of the propositions from P(0) up to P(k), then P(k) can be used as a base case: $$(\forall k \in \mathbb{N})((P(0) \land P(1) \land \cdots \land P(k)) \implies P(k+1)) \implies (\forall k \in \mathbb{N})(P(k))$$ ### Proof of the Induction Principle $$(\lnot \forall n)P(n) \implies ((\exists n) \lnot (P(n - 1) \implies P(n))$$ The **Well Ordering Principle** states that for all subsets of natural numbers, there exists a smallest number in that subset. * **This is not trivial!** Think about rational numbers- it's impossible to get the smallest rational number because it extends to $$-\infty$$. * **This principle justifies the use of induction** **for any set of natural numbers.** If the smallest number (base case) always exists, then we can just prove that and move upwards, rather than trying to prove both $$k-1$$and $$k+1$$. ## More Resources Note 2: Note 3: [https://www.eecs70.org/assets/pdf/notes/n3.pdf](https://www.eecs70.org/assets/pdf/notes/n2.pdf) Lecture 2 Slides: # Stable Matching ## Introduction The **stable matching problem** deals with how to match one group to another group while trying to maximize everyone's 'happiness'. It works best when the two groups are **distinct** (nobody can be in both groups at once) and the orderings are **complete** (everyone in the other group has to show up in all orderings). Before we get to examples of when this might apply, I'll throw out a few examples where we **can't** use this algorithm so you don't get any wrong ideas: * We **cannot** use this for creating room groups based on roommate preferences (because everyone is in one big group). * We **cannot** use this for situations where people are limited to their top three choices in jobs. ### Some Definitions In order to more concretely set up the stable matching problem, let's define some terms formally: A **pairing** is a set of job-candidate pairs that uniquely (disjointly) matches each job to each candidate. For example, {(Esports, Joe), (Steakhouse, Donald)} is a valid pairing if we're trying to match Joe and Donald to two possible jobs. Note that 'job' and 'candidate' can be replaced with any two arbitrary groups, as long as one group doesn't contain any items from the other group! A **rogue couple** is a single pair where neither person in the pair wants to be with the other person. If a pairing is **stable**, it cannot contain any rogue couples. **x-optimal matching** is a stable pairing that favors the choices of group x over the other group. This group is **whichever group chooses**- In the example above, the pairing would be **job optimal**, and **candidate pessimal.** (More on why later.) ## The Propose and Reject Algorithm There are a good number of ways we can get stable matchings, but one of the most commonly used methods is the **propose-reject algorithm.** It goes like this: 1. On the first day, each job sends an offer to their favorite candidate. 2. Each candidate has their own set of preferences, though, so if they get multiple job offers they'll reject all but their favorite one. 3. The candidate will then say to their favorite offer, "I like it, but please wait until tomorrow so I can see if I get a better offer." 4. Repeat until each job gets exactly one candidate. #### Important notes about this algorithm: * **It is guaranteed to terminate.** (Check the proofs section to see why) * **Every day, it gets better for candidates.** This is because candidates can choose their best offer, so as more offers keep rolling in they get more (and better) choices. This means that this particular algorithm is **job-optimal** and **candidate-pessimal.** Indeed, regardless of what the groups are, **whichever group proposes will have optimal results.** ### An Example Let's say that three people **Alice (A), Bob (B),** and **Charlie (C)** applied to jobs in **Capitol One (1), Two Sigma (2),** and **3M (3)** . Their preferences are (in order from most to least favored): CANDIDATES JOBS\ A || 1 2 3 1 || C A B\ B || 1 2 3 2 || A B C\ C || 2 1 3 3 || A C B On day 1, Capitol One will send an offer to Charlie. Two Sigma and 3M will send job offers to Alice. Since Alice got multiple offers, they will reject 3M and keep Two Sigma on their list.\ **Day 1: (1,C), (2, A)** On day 2, Capitol One will send an offer to Charlie again, and Two Sigma will send an offer to Alice again. Since 3M was rejected yesterday, they'll move onto the next person on their list, Charlie. However, Charlie still prefers Capitol One over 3M so he will reject 3M.\ **Day 2: (1,C), (2,A)** On day 3, Capitol One will send an offer to Charlie again, and Two Sigma will send an offer to Alice again. Since 3M was rejected yesterday, they'll move onto their final person, Bob. **Since no more candidates or jobs are left unmatched, this algorithm terminates in the stable pairing (1, C), (2, A), (3, B).** ### Proofs of the Propose-Reject Algorithm #### Existence (Termination) **We can prove this by contradiction:** suppose that a job isn't paired yet after the end of the algorithm. This would mean that the job must have made an offer to every single possible candidate and got rejected by all of them. But this is illegal! Those candidates must be matched with other jobs if they rejected this one, meaning there needs to be 1 more job than there actually is. Therefore, all jobs and candidates must be paired at the end of the algorithm. #### Stability Let's say a job J and candidate C are matched after the algorithm terminates. If J preferred another candidate C\*, then that would mean C\* were higher up on its list and must have made an offer to C\* before C. However, the fact that J is matched with C and not C\* means that C\* rejected J, and thus prefers another job over J. This means that the pairing J and C is stable. (You can repeat this argument for any pair J and C.) #### Optimality Theorem: Job Propose, Candidate Reject produces a job-optimal pairing. * Proof by contradiction: assume that there's a job j that doesn't get an optimal candidate c. * Let t be the first day job j gets rejected by its optimal candidate g. * On that day, there was another job offer j\* that c preferred. * Therefore, j\* likes c at least as much as the optimal candidate. **This creates a rogue couple.** * By the Well Ordering Principle, this is the first day that job j was rejected **Pessimality** Theorem: Job Propose, Candidate Reject produces a candidate-pessimal pairing: * Let T be a pairing where (j, c) is a pair. * Let S be a stable pairing that is worse for c than T is. So (j, c\*) is a pair. * Since j prefers c to c\*, (j, c\*) is a rogue couple for S which is a **contradiction.** Therefore, T is the worst possible pairing for c. ### # Graphs {% hint style="info" %} This is a second introduction to graphs that assumes you've at least seen them before. Take a look at the [61B version](https://cs61b.bencuan.me/abstract-data-types/graphs) if you feel lost! {% endhint %} ## What's a graph? Formally, a graph is a **set of vertices with a set of edges connecting them.** A graph can be defined as $$G = (V, E)$$ where $$V = {A, B, \cdots V\_n}$$ and $$E = {{A, B}, {B, C} \cdots }$$ For an **ordered graph** where vertices are numbered, $$E$$could be represented as a set of ordered pairs instead: $$E = {(A, B), (B, C) \cdots }$$ (Insert image of graph) ### Concepts and Definitions A **neighbor** of a vertex is another vertex that is next to the original vertex. Formally u is a neighbor of v if $${u, v} \in E$$. An edge is **incident** to the two vertices that it connects The **degree** of a vertex is the number of other vertices neighboring. If the graph is directed, the degree can be split into the **in-degree** (number of incoming connections) and the **out-degree** (number of outgoing connections). * The sum of vertex degrees is equal to $$2 |E|$$. * Proof: Count the number of incidences. Each edge is incident to exactly two vertices, so the total number of edge-vertex incidences is $$2|E|$$(i.e. two times the number of edges). * The degree can also be defined as the number of incidences corresponding to a particular vertex v. Therefore, the total incidences is the sum of all degrees for all vertices! A **path** is a sequence of edges. These edges must be connected, i.e. a path could be $$(v\_1, v\_2), (v\_2, v\_3), (v\_3, v\_4)$$. * If there are $$k$$vertices, then a path should have $$k-1$$edges! A **cycle** is a special path that begins and ends on the same vertex. * Unlike a noncyclic path, there should be the same number of vertices as edges in a cycle. A **walk** is a sequence of edges that could possibly repeat a vertex or edge. A **tour** is a walk that starts and ends on the same vertex. Additionally, it cannot have any repeated edges. * An **Eulerian walk** is a walk that uses **every edge** exactly once. * Doesn't require all vertices to be connected! There could be an isolated vertex with 0 degree. * An **Eulerian tour** is a tour that visits **every edge** in a graph exactly once\*\*.\*\* * Theorem: any undirected graph has an Eulerian tour if and only if all vertices have **even degree** and is connected. * Proof: You need to use two incident edges every time you visit a node (to enter and leave). So when you enter, you need another edge to be able to leave! If a vertex has an odd number of edges, then you get stuck on that vertex with nowhere to go once you visit it. Here's a handy summary, adapted from an explanation by [Dustin Luong](https://github.com/dstnluong): | | end anywhere | start = end | | ------------------------ | ------------ | ----------- | | repeated vertices ok | walk | tour\* | | repeated vertices not ok | path | cycle\* | \*Eulerian if it uses each edge exactly once. Two vertices $$u$$and $$v$$are **connected** if there exists a **path** between them. * If all vertices are connected, then the graph is considered a **connected graph.** A **complete graph** is a graph where every vertex is connected to every other vertex by exactly one edge. Complete graphs have some nice properties: * Every vertex is incident to $$n-1$$edges (if there are $$n$$total vertices). * The sum of all degrees is $$n(n-1)$$. A **tree** is kind of like the opposite of a complete graph in that it has the **minimum number of edges** in order to ensure all vertices are connected ($$v-1$$ total edges). Here are some properties of trees, from a graph perspective (If you aren't already familiar with the recursive definition of trees, head over to the [61B guide](https://cs61b.bencuan.me/abstract-data-types/binary-trees) first to brush up on it!) * Trees are **acyclic** and **connected.** * **Leaves** are vertices that have degree 1. * In a tree in which each parent node has 2 children, the **root** is a single vertex that has degree 2 and **non-leaf vertices** have degree 3. ## Hypercubes A **hypercube** is a specific class of graphs that have highly connected vertices. In order to understand them better, let's start building some up: Every hypercube has a dimension $$n$$. A 1-dimensional hypercube is simply a line (2 vertices connected by 1 edge). Not too exciting: A 2-dimensional hypercube is a square (4 vertices connected by 4 edges). Still pretty familiar: A 3-dimensional hypercube is a cube (8 vertices, 12 edges): Now, let's get to the interesting stuff. How do we construct a 4-dimensional hypercube?? Well, let's figure out how we went from 2 to 3- we essentially **duplicated** the existing hypercube, then **connected corresponding vertices** (ones that are in the same relative position): If we do this again for the 3-dimensional hypercube, we'll get this 4-dimensional hypercube, which has 16 vertices and 32 edges: You might have noticed a pattern in how many vertices and edges a hypercube has. Here are those properties stated more formally: * A hypercube has $$2^n$$vertices. * A hypercube has $$n2^{n-1}$$edges. Hypercubes are super useful, particularly for representing **bit strings.** If we have an $$n$$-dimensional hypercube, then we have enough vertices to represent all possible permutations of 1's and 0's of length $$n$$. Every edge would then represent the act of flipping exactly one bit. ## Planar Graphs A **planar graph** is a graph that can be drawn without having two edges overlap. **Euler's Formula** states that a connected planar graph has two more vertices and faces than the number of edges: $$ v + f = e + 2 $$ Let's take a look at some examples to convince ourselves of how this works: (A triangle has 3 edges and two faces: the inner face and outer face.) (This shape is connected, but there is no enclosed face so the only face is the outer face.) Another consequence of Euler's Formula is the inequality that holds for connected planar graphs: $$ 3f \le 2e $$ This inequality states that any planar graph with 2 or more vertices must have at most 3 faces for every 2 edges. We know this because the smallest possible face is a triangle. If we plug this into Euler's Formula, we can eliminate one variable to get $$e \le 3v - 6$$. This makes it much easier to figure out if a graph is planar or not, since faces are often difficult to count. ### Proof of Euler's Formula Let's use induction! **Base Case:** Let there be 0 edges and 1 vertex. This means there's only 1 (outer) face as well. In this case, $$v + f = 1 + 1 = 0 + 2$$. This works! **Induction Step:**\ Let's consider the case of a tree. Then, we know that there are always 1 fewer edges than vertices, and only one face:\ $$v + 1 = (v-1) + 2$$ works! What about something that's not a tree? Well, things get a bit tricker here. * Let's consider a graph: * Now, let's start with the tree corresponding to the same number of vertices as the original: * Now, we'll keep adding edges to enclose faces until we reach the number of edges in the original: * We'll notice here that for every edge we add, a new face is created! * Therefore, we can plug this fact into our inductive hypothesis (that Euler's formula works) to get $$v + (f+1) = (e+1) + 2$$. ### Nonplanar Graphs Although nonplanar graphs don't share many of the nice properties planar graphs do, they're often more accurate representations of real life. They can also be used frequently in proofs to prove that a graph must either be planar or non-planar. There are two famous non-planar graphs that are worth taking a look into: #### K3,3 $$K\_{3,3}$$is also known as the "utility graph" because of its connection to a popular puzzle: given 3 houses and 3 utilities (water, gas, electric), how can we draw a line connecting each house to every utility without having any of the lines cross? I'll save you an amount of suffering by spoiling the answer: **this is an impossible task when done on a standard (planar) paper.** (Want topical entertainment? [Watch some youtubers solve this problem on a mug.](https://www.youtube.com/watch?v=VvCytJvd4H0)) This is because $$K\_{3,3}$$is **non-planar**, so by definition at least one of the lines has to cross! $$K\_{3,3}$$is a **bipartite graph** since it has two groups of 3 vertices; and within each group, none of the vertices are directly connected to one another. #### K5 $$K\_5$$is the **complete graph** of 5 vertices. (This means that each vertex is connected to every other vertex.) We can see that $$K\_5$$has 5 vertices and 10 edges. Since we know that all planar graphs have $$E \le 3V - 6$$, we can show that $$K\_5$$certainly isn't planar (since 10 is greater than 3(5)). A striking fact: **ALL non-planar graphs contain either** $$K\_5$$**or** $$K\_{3,3}$$**!** This means that you can prove that a graph is either planar or nonplanar simply by showing that either of these component graphs can or cannot exist in a larger graph. ## Graph Coloring A **graph coloring** assigns a color to each vertex such that **every edge has two different colors** on its two endpoints: Often, we would like to figure out the **minimum number of colors** (categories) \*\*\*\* it takes to properly color a graph. This could have many uses, from [register allocation](https://en.wikipedia.org/wiki/Register_allocation) to [solving sudoku puzzles](https://medium.com/code-science/sudoku-solver-graph-coloring-8f1b4df47072). ### Six Color Theorem Let's propose that every **planar** graph can be colored with 6 colors or less. From Euler's Formula, recall that $$e \le 3v - 6$$for any planar graph with more than 2 vertices. We also know that the degree of the graph is equal to $$2e$$. So, the average degree of any given vertex is $$\frac{2e}{v} \le \frac{2(3v-6)}{v} \le 6 - \frac{12}{v}$$. This proves that there **exists** a vertex with degree at most 5 (due to the property of averages). Let's try removing this vertex and see what happens. Well, now each of the 5 neighbors each are assigned a different color. If we add the vertex back, then it can assume the 6th color. We can use this proof inductively to show that adding any vertex will result in the same thing occurring. ### Five and Four Color Theorem It turns out that 6 is actually not the tightest bound we can put on the number of colors needed! It is possible to color all **vertices** with **5 colors** or less and all **faces** with **4 colors** or less in a **planar graph**. I won't go into the details of these proofs here, but check out the bottom of [Note 5](https://www.eecs70.org/assets/pdf/notes/n5.pdf) for the proof of the 5 color theorem, and [Wikipedia](https://en.wikipedia.org/wiki/Four_color_theorem) has a good introduction to the (highly technical) 4 color theorem proof. # Modular Arithmetic ## What is Modular Arithmetic? Modular arithmetic is "clock math" - that is, when numbers wrap around back to 0 if they get too big. You could think about it like a **remainder:** $$21 \pmod{10}$$ for example can be read as "what is the remainder of 21 when it is divided by 10?" (it's 1, by the way.) This is an important concept in many aspects of computer science, namely [cryptography](/discrete-math/rsa-cryptography) and [error correction](/discrete-math/polynomials) among many others. ## Key Ideas **If d divides x and d divides y, then d divides (y-x)**. $$d \mid x, d \mid y \implies d \mid (y-x)$$\ (Reminder: $$a \mid b \iff (\exists q \in \mathbb{Z})(a = qb)$$) **Modular Equivalence:** If you're looking at a clock and it becomes 25:00, you know it's actually the same as 1:00. Even if they're technically not the same number, they can be treated the same way. * More formally: **x is congruent to y modulo m:** $$x \equiv y \pmod{m}$$\*\*\*\* **Important Notation Distinction:** $$x \pmod{m}$$ is the **class of numbers** that follow the mod rule $$m$$. It can be used to write equivalences ($$10 \equiv 21 \pmod{11}$$). However, $$\mod(x, m)$$is just a number (the remainder when dividing x by m). $$\mod(x,m) = x - \lfloor{\frac{x}{y}}\rfloor \cdot y$$ **Greatest Common Denominator (GCD Mod Corollary):** Modular arithmetic can be used to identify an important property of the GCD, which is that $$GCD(x,y) = GCD(x \mod y, y)$$. ## Arithmetic ### Addition Given that $$a \equiv b \pmod{m}$$, $$a+c \equiv b+c \pmod{m}$$. This result shouldn't be too surprising, and suggests that adding a constant value to both sides won't change the congruence, just like any other equation. ### Multiplication Multiplication works pretty much how you'd expect it to work after seeing how addition works. Formally defined, if $$a \equiv b \pmod{m}$$, then $$ka = kb \pmod{m}$$. Intuitively, this means that if you want to multiply a big number, you can take the mod of the big number before multiplying it, and that will be equivalent to multiplying before taking the mod. As an example, let's try to figure out what day it is in 8 years. We know that there will be 2 leap years with 366 days each, and 6 normal years with 365 days each. We don't really feel like computing $$(365 \cdot 6) + (366 \cdot 2) \pmod{7}$$, so we can instead take the mod of 365 and 366 first. This yields the much simpler expression $$(1 \cdot 6) + (2 \cdot 2) \pmod{7} \equiv 1$$. Therefore, the day in 8 years will be one day after today. ### Division and Inverses In normal number spaces, the **multiplicative inverse** of x is a y such that $$xy = 1$$. This concept still applies to modular arithmetic! If we have $$x \pmod{m}$$, then the multiplicative inverse is defined as a number y such that $$xy = 1 \pmod{m}$$. For example, let's take a look at $$4x = 5 \pmod{7}$$. We can multiply both sides by 2 in order to get $$8x = 10 \pmod{7}$$. At this point, we can use the $$\pmod{7}$$to reduce the 8 into a 1 and the 10 into a 3, resulting in $$x = 3 \pmod{7}$$. There are some values where it's impossible to get an equivalence into the form $$1 \pmod{m}$$. This usually happens when there is a common factor (like $$8x \equiv y \pmod{12}$$). In other words, **if the greatest common divisor of x and m is 1, then x has a multiplicative inverse modulo m. (x is relatively prime to y).** ## Algorithms Now, let's explore three famous algorithms for computing useful information using modular arithmetic: **Euclid's Algorithm** for GCD and inverses, the **Chinese Remainder Theorem**, and **Fermat's Little Theorem.** ## Euclid's Algorithm ![](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFka3X4qx2R0yzli0Ke%2F-MHRhUyMGdkk1Wt8-eIx%2F-MHRtl7zmn3U2WO5_BGD%2Fimage.png?alt=media\&token=a5970aec-813b-4eb7-bb63-eebea203cd36) **Euclid's Algorithm** is a recursive procedure for calculating the greatest common denominator. Remember that $$GCD(x,y) = GCD(x \mod y, y)$$ by the GCD Mod Corollary. We can prove that this works using induction: * Base Case: If y is 0, then any value for x is the GCD since everything can divide 0 to get 0. * Inductive Case: Proof of the GCD Mod Corollary. This is a rather efficient algorithm: at every iteration, the value of x and y decrease dramatically- at least by a factor of 2. This makes it $$\theta(\log\_2(x))$$(in other words, we need one division for each bit that is needed to represent $$x$$). For an example of a computation, check out the Extended Algorithm section below (the computation is extremely similar). ### Using Euclid's Extended Algorithm for Inverses Great! We got the GCD. So what? Remember that **if the GCD of x and m is 1, then there is an inverse of x.** In more concrete terms, we can state **Euclid's Extended GCD Theorem (Bezout's Theorem)** as such: $$ ax + by = gcd(x,y) $$ In other words, the GCD can be written as a scalar multiple of x and y. Since we remember that the definition of the inverse is that $$ax + by = 1$$for some integers a and b, Euclid's Extended Theorem checks out for showing that the inverse exists if the GCD is 1. ![](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFka3X4qx2R0yzli0Ke%2F-MHqVG9Lpr5wN6OHzGr4%2F-MHqVMq5Rzgc0C7tEBbI%2Fimage.png?alt=media\&token=75f8a2aa-0edc-4506-a3e4-88b27b768755) The process can be tedious to compute by hand, but here's a nice video that walks through that process: {% embed url="" %} ## The Chinese Remainder Theorem The **Chinese Remainder Theorem (CRT)** guarantees **existence and uniqueness** of a solution to a system of modular congruences. More formally stated: There is a unique solution $$x \pmod{mn}$$such that $$x = a \pmod{m}$$, $$x = b \pmod{n}$$, and $$gcd(m,n) = 1$$. Here are a few ways to word it (see which one clicks better): #### Formal Statement of CRT: Let $$n\_1 \cdots n\_k$$be positive coprime integers. (Any two of them must be relatively prime.) Then, for any combination of integers $$a\_1 \cdots a\_k$$, a **unique** x exists such that $$x \equiv a\_i \mod n\_i$$for all $$0 < i \le k$$. **Alternative Statement of CRT:** Let $$n\_1, \ldots n\_k$$ be pairwise co-prime, i.e. $$n\_i$$ and $$n\_j$$ are co-prime for all $$i \neq j$$. The Chinese Remainder Theorem (CRT) tells us that there exist solutions to the following system of congruences: $$ \begin{align} x &\equiv a\_1 \pmod{n\_1} \tag{1} \ x &\equiv a\_2 \pmod{n\_2} \tag{2} \ &\vdots \tag{$\vdots$} \ x &\equiv a\_k \pmod{n\_k} \tag{$k$} \end{align} $$ #### Uniqueness of CRT Solution Not only do we know that there is a unique solution $$x$$, but we can actually write out its exact value! Here it is: $$ x = \sum\_{i=1}^k a\_i b\_i \pmod{N} $$ In this sum, $$b\_i = (\frac{N}{n\_i}) \cdot (\frac{N}{n\_i})^{-1} \mod n\_i)$$ , and $$N$$is the product of all primes $$n\_1, \cdots n\_k$$. This sum is congruent to $$a\_i \mod n\_i$$for all valid values of $$i$$. #### Computation The Chinese Remainder Theorem often ties well together with the Extended Euclidean Algorithm, since we would need to find lots of inverse mods for each $$b\_i$$. Also like the Extended Euclidean Algorithm, it's very hard to demonstrate the computation on a static webpage so here's another good video walkthrough! {% embed url="" %} ## Fermat's Little Theorem **Fermat's Little Theorem** (not to be confused with [Fermat's Last Theorem](https://www.youtube.com/watch?v=nUN4NDVIfVI)) makes the observation that **exponentiation is periodic** when modulo is done by a **prime number.** This makes it reasonable to compute obscenely large numbers, like $$2^{65535}$$, when in a mod space. #### The Formal Definition For prime $$p$$ and an integer $$a \in {1, 2, \cdots, p - 1}$$, $$a^{p-1} \equiv 1 \pmod{p}$$. #### An Alternative Definition If we multiply both sides by $$a$$, we can actually drop the restriction to $$a$$ and allow it to be any integer. This version is sometimes more useful than the normal definition: For prime $$p$$ and any integer $$a$$, $$a^p \equiv a \pmod{p}$$. For an application of Fermat's Little Theorem, head over to [RSA Cryptography](/discrete-math/rsa-cryptography)! # RSA Cryptography ## Introduction The internet is built upon the fact that stuff needs to go from point A to point B quickly, accurately, and securely. We'll talk about the **secure** part of that now (the accurate part will be addressed [soon](/discrete-math/polynomials)!). One of the ways we can make sure our top-secret messages can't get intercepted is to **encrypt** them- mix them up to become incomprehensible using some secret code, then decrypt it at the other end. This has a major problem though- how can you agree to use the same secret code as someone else if you've never met them before? **RSA** (named after creators Rivest, Shamir, Adleman) is an encryption scheme that takes advantage of **public keys** to solve this very problem. In the RSA system, everyone broadcasts their public key all over. When encrypting a message, the sender can lock their message using their **private key** paired with the *sender's* public key, such that only the sender themselves can unlock the message using their own private key. This poses yet another problem: how can we choose these public and private keys so that they work nicely with each other? Well, we can use modular arithmetic of course!! :smile: ## The RSA Cheat Sheet **Variables:**\ **-**$$p, q$$are two distinct prime numbers.\ **-** $$e$$is relatively prime to $$(p-1)(q-1)$$.\ **-** $$N = pq$$\ \- $$x$$is the original message; $$y$$is the encrypted message **Public Key:** $$(N, e)$$\ **Private Key:** $$d = e^{-1} \pmod{(p-1)(q-1)}$$ **Encryption:** $$E(x) = x^e \pmod{N}$$\ **Decryption:** $$D(y) = y^d \pmod{N}$$ ## Example Let our two prime numbers be $$p = 5, q = 11$$. (In the real world, these would be much larger for security purposes- but let's not make this too hard on ourselves!) The first step is to **choose our public key.** We know e must be relatively prime to $$(p-1)(q-1) = (4)(10) = 40$$. A small number that satisfies this is $$3$$, so we can go ahead and use that. Therefore, our public key is $$(N, e) = (55, 3)$$. The next step is to **compute the private key.** Using the formula, $$d = 3^{-1} \pmod{40}$$. We could use [Euclid's Extended Algorithm](/discrete-math/modular-arithmetic#using-euclids-extended-algorithm-for-inverses) to compute this value, which ends up being $$27$$. Therefore, $$d = 27$$. After we have computed our keys, we must **encrypt the message.** This yields $$y = x^3 \pmod{55}$$for some arbitrary message $$x$$. Finally, we must **decrypt the message** by passing $$y$$into the decryption formula. This yields $$x = y^{27} \pmod{55}$$. If all goes well, the decrypted message should be the same as the original message! # Polynomials ## Introduction "I learned this in 4th grade", you say, "and I already know how to do Taylor approximations and binomial expansions and get local minima... what else is there to do?" (At least that was my first thought :stuck\_out\_tongue:) Turns out, polynomials are super useful in the world of discrete math. Here, we'll cover two applications in discrete space, which are **secret sharing** and **error correction.** ### Important Properties Gotta do some quick review first! Recall that all polynomials are in the form $$ a\_dx^d + a\_{d-1}x^{d-1} + \cdots + a\_1x + a\_0 $$ where $$d$$is the **degree** of the polynomial (highest power) and $$a\_i$$are the **coefficients.** Polynomials have some nice properties: * A nonzero polynomial of degree $$d$$has at most $$d$$real roots. * If we're given $$d+1$$distinct points (x y pairs), there is exactly one, unique polynomial of degree $$d$$that goes through all of those points. ### Finite Fields Like many things in discrete math, polynomials can be taken to a modulo as well! When this happens and we have $$p(x) \pmod{m}$$where $$p(x)$$is a polynomial and $$m$$is a prime number, we say that we're working in a **Galois Field** $$GF(m)$$. Even when working over a finite field, the two properties of polynomials still apply. Finite fields restrict the number of possible polynomials, which is actually necessary for some of the applications below. ## Lagrange Interpolation We have already established that $$d+1$$points only have one unique degree $$d$$polynomial that goes through all of them. But how do we find this one polynomial? **Lagrange Interpolation** is a method to recover this polynomial given your original points. It has a lot of interesting ties to previously covered concepts like the Chinese Remainder Theorem and linear algebra (which won't be covered here, but explore it further to find out more!). Here's how it works: First, let's find a polynomial that is degree $$d$$ and is equal to $$1$$at point $$x\_1$$, but $$0$$everywhere else. This isn't too hard to do: we can use $$(x-x\_2)(x-x\_3)\cdots(x-x\_{d+1})$$. Note here that we skipped $$x\_1$$because adding that term would make the polynomial degree $$d+1$$! However, this alone would result in a number other than 1 at $$x\_1$$, so we can normalize it by dividing by all $$(x\_1-x\_j)$$: $$ \Delta\_1(x) = \frac{\prod\_{j \ne 1} (x - x\_j)}{\prod\_{j \ne i} (x\_1 - x\_j)} $$ Why are we doing this though? Well, you can think of it like creating a **basis** of polynomials so that we can take a linear combination of all of them to get the original. Since $$\Delta\_1(x\_1) = 1$$, we can multiply it by $$y\_1$$ to ensure that it passes through the original point. Combining all of the delta polynomials for all $$d+1$$original points yields $$ p(x) = \sum\_{i=1}^{d+1} y\_i \Delta\_i(x) $$ ## Secret Sharing Now, let's take a look at a cool application of Lagrange interpolation! Here's the setup: let's say you're in the Super Secret Club and want to create a secret code for your Super Secret Vault™. However, you want to make sure that the Vault™ can only be opened if 30 of your 50 members agree. How would we pull this off? Here's the solution: **create a 29-degree polynomial** and give each person in the club a point on that polynomial $$(x\_i, y\_i)$$. **Make sure none of the x's are 0!** Then, set the secret code equal to $$y\_0$$, the y-value of the polynomial corresponding to $$x=0$$. We know that a 29-degree unique polynomial can be recovered with 30 distinct points. So, if 30 members agree and get together to share their points, we can use Lagrange interpolation to recover the original polynomial! Once you have this original polynomial, it is a simple matter to recover the secret code by plugging in 0 to the polynomial. ## Error Correction Lagrange interpolation can also be used to correct errors in data (if it gets erased or corrupted). There are two main types of errors: **erasure errors,** when the data is simply lost, and **general errors,** where the data is corrupted and displays something other than the original data. ### Erasure Errors Erasure errors aren't too tough to think about once we have a good grasp of polynomial properties. Since we know that a unique polynomial of degree $$d$$can be recovered with $$d+1$$points, we could simply tack on an additional $$k$$points in order to protect the original polynomial from $$k$$erased points. ### General Errors General errors, on the other hand, are slightly more difficult to consider because they could throw off the result wildly if we do not identify them. So how do we figure out which points are the errors? Let us construct an error-locator polynomial $$E(x) = (x-e\_1)(x-e\_2) \cdots (x-e\_k)$$ where an error $$e\_i$$ represents the incorrect value given by one of the spies when in a larger group. For any one point $$i$$ in the original polynomial $$P(i)$$, we know that $$P(i)E(i) = r\_iE(i)$$ where $$r\_i$$ is the original location of the point of the polynomial. If we have $$M$$ original data points, this provides enough points for a $$M-1$$ degree polynomial, which we can call $$Q(x)$$. For any particular point, though, we know that $$Q(i) = P(i)E(i)$$ since the point given is either in the original polynomial, or is in the error-locator polynomial. Therefore, in order to solve for the true polynomial $$P(x)$$, we can take the ratio $$\frac{Q(x)}{E(x)}$$ by definition of $$Q(x)$$. Since we do not know what each value $$e\_i$$ is, we need to solve a system of linear equations for each point to identify what these are. **This requires** $$M + 2k$$ **equations**, because we require the polynomial $$Q(x)E(x)$$ to perform this calculation. # Countability ![But Buzz... which kind of infinity :?](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFka3X4qx2R0yzli0Ke%2F-MOI9GsnfeWRfMFM68x6%2F-MOIot_LBo25hwajIVaB%2Fimage.png?alt=media\&token=f8a3d3f8-d0c7-4ce0-af17-3fe2b308097c) **How big is infinity? Are some infinities bigger than others?** The $$\infty$$is a rather mind-boggling concept; the principles of countability will hopefully make some sense out of it. ## Bijections A **bijection** is a mapping between two sets such that there **exists** a **unique** pairing from a particular element of one set to another. These ideas of **existence** and **uniqueness** can be formalized by considering some different types of maps: An **injection**, otherwise known as a **one-to-one** mapping, is where each element in a set maps to a **unique** element in another set. (This does not, however, guarantee that the same is true the other way around- some elements in the second set may not have any mapping to them!) More formally: $$(\forall x,y \in D)(f(x) = f(y) \implies x = y)$$ A **surjection**, otherwise known as an **onto** mapping, is where there **exists an input corresponding to every output.** More formally: $$(\forall y \in R)(\exists x \in D)( y = f(x))$$ For an injection, $$|A| \le |B|$$: there must be at least one input per output.\ For a surjection, $$|A| \ge |B|$$: there must be at least one output per input. A **bijection,** also known as an **isomorphism,** is a mapping that is **both one-to-one AND onto.** This guarantees that **the two sets must be the same size**, a statement known as the **isomorphism principle** ![Source: http://www.eecs70.org/static/notes/n11.pdf ](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFka3X4qx2R0yzli0Ke%2F-MOI9GsnfeWRfMFM68x6%2F-MOIq5-s9vV4kFWw-eMv%2Fimage.png?alt=media\&token=143b734e-b566-4b5f-9f43-9861f7b994ac) ## Countability A set $$S$$ is **countable** if there is a **bijection from S to the set of natural numbers** $$\mathbb{N}$$**or a subset of N.** In other words, $$S$$and $$\mathbb{N}$$have the **same cardinality.** \ This should make intuitive sense because the natural numbers are, by definition, countable (we can start from 1, then 2, then 3... and hit them all), so if we can somehow number off some elements in a group and count them that way, then those elements are countable! #### Proving that something is countable: * Find a bijection from S to N or N to S (must prove one to one and onto). Note that a bijection in either direction is individually valid. * Find an injection from S to N, AND an injection from N to S. * **Enumeration**: list all elements of S. ## Enumerability Let's now think about some ways we can list every element in a set. \ Some properties to keep in mind: * **Listing a set implies that it is countable.** * Every element must have a unique, finite position on the list. (You can number them off.) * Any infinite set that can be listed is as large as the set of natural numbers. One method of enumerating is to find a **recursive definition** of the set: that is, given any one element in the set, we can define the element that immediately follows it. One example of an enumerable set is the set of all binary strings$$B = {0, 1}^\* = {\emptyset, 0, 1, 00, 01, 10, 11, 000 \cdots }$$ **.** This is enumerable because we can say that a string with $$n$$bits will be guaranteed to appear before position $$2^{n+1}$$. One example of a non-enumerable set is the set of all rational numbers: we can't write fractions in an order such that you can get to the next fraction in a finite number of steps. However, the *are* countably infinite (read on to find out why!) ## Pairs of Natural Numbers A pair of natural numbers $$N \times N$$ has size $$|N| \times |N|$$so it is countably infinite. We can enumerate this: $$(0,0), (1,0), (0,1), (2,0) \cdots$$which guarantees that the pair $$(a,b)$$is in the first $$(\frac{(a+b+1)(a+b)}{2}$$elements in the list. (triangle) ![](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFka3X4qx2R0yzli0Ke%2F-MK8qYwo8VZn62W9wl4c%2F-MK8sNlMSDBx5jUmFPfu%2Fimage.png?alt=media\&token=0a996fdd-22c0-408e-8114-f3a094347f43) ### Rational Numbers Rationals are countably infinite by writing them all in the form $$(p,q)$$for a rational number $$n=\frac{p}{q}$$. We determined that all pairs of natural numbers is countable so rational numbers are as well. ## Cantor's Diagonalization Argument **Proof by contradiction:** assume that a set S is countable (even if it isn't). Then, there must exist a listing that contains all elements in the list (enumeration). We can construct an item that isn't in the set by taking the diagonals of digits in the set: ![](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MFka3X4qx2R0yzli0Ke%2F-MK8qYwo8VZn62W9wl4c%2F-MK8tUqRP-5ncHUVIx20%2Fimage.png?alt=media\&token=9b1ab8f5-8516-41ab-ab6f-a70ca3ef49c5) This can be used to prove that real numbers are not countable. **Formal steps :** * Assume that a set S can be enumerated. * Consider an arbitrary list of all the elements of S. * Use the diagonal from the list to construct a new element t. * Show that t is not in the list, but that t is in S. * This is a contradiction. Here's a demonstration of the diagonalization argument in action: {% embed url="" %} **Continuum hypothesis:** there is no set with cardinality between the naturals and the reals. **Generalized continuum hypothesis:** there is no infinite set whose cardinality is between the cardinality of an infinite set and its power set. (In other words, the power set of the natural numbers is not countable.) # Computability Computability is the study of a massively important question: **do there exist any problems that are impossible for a computer to solve?** ## **The Halting Problem** It turns out that the above question itself is impossible to solve: in other words, **there cannot exist a program HALT which determines if a program can halt in finite time given a particular input.** This was originally proposed by Alan Turing- he proved the nonexistence by attempting to feed the Halting Problem into itself: if the Halting Problem doesn't halt, then it is supposed to output an answer. That means that the Halting Problem would state that the Halting Problem halts, even though it didn't. This paradox led to demonstrating that the Halting Problem simply cannot be solved. {% embed url="" %} ## Reductions **Reducing** a problem A to another problem B means that we can solve problem A if we know how to solve problem B. For instance, we might be able to write psuedocode that has a whole bunch of known components, but rely on the output of problem B in order to determine the final output. One application of reduction is to show that **a program cannot exist if it requires the Halting Problem as a component.** # Overview The probability section of this guide will likely never be fully completed, due to the fact that the [Prob 140 textbook](http://prob140.org/textbook/content/README.html) is such an excellent resource in probability theory. Go read it and do the problems! Instead of a full write-up, the pages in this section will typically just link to relevant sections from the textbook. Personally, I found everything I needed to do well in CS70 probability (and much more) here, including examples that are very similar to problems you might see on the homework. TL;DR don't use this section of the guide, just read the 140 textbook. Here is a running list of topics in this section: * [**Counting**](/probability/counting) provides us an intuitive method of figuring out how many possible ways there are to do something. * [**Discrete probability distributions**](/probability/discrete-probability), such as the Binomial or Geometric distributions, describe the probabilities of a finite set of outcomes. * [**Continuous probability distributions**](/probability/continuous-probability), such as the Poisson or Normal distributions, help us model real values, like lifetime or height. * [**Markov chains**](/probability/markov-chains) model transitions between discrete states. * [**Expectation and variance**](/probability/expectation-and-variance) are tools to describe the characteristics of a random variable or distribution. * [**Concentration inequalities**](/probability/concentration-inequalities) allow us to approximate bounds for random variables when we only know their expectation and/or variance. There is far more to explore in learning the basics of probability- not everything is included in this list! ### Reference | Distribution | Values | Density | Expectation | Variance | Links | | --------------------------------------------------------------------------------------------------------- | -------------------- | ------------------------------------------------------------ | --------------------- | ------------------------------------------ | ----- | | Uniform(m,n) | \[m, n] | $$\frac{1}{n-m+1}$$ | $$\frac{m+n}{2}$$ | $$\frac{(n-m+1)^2-1}{12}$$ | | |

Bernoulli(p)

Indicator

| 0, 1 |

P(X=1) = p

P(X=0) = 1-p

| $$p$$ | $$p(1-p)$$ | | | Binomial(n,p) | \[0, n] | $$\binom{n}{k}p^kq^{n-k}$$ | $$np$$ | $$np(1-p)$$ | | | Poisson($$\mu$$) | $$x\ge0$$ | $$e^{-\mu}\frac{\mu^k}{k!}$$ | $$\mu$$ | $$\mu$$ | | | Geometric(p) | $$x \ge 1$$ | $$(1-p)^kp$$ | $$\frac{1}{p}$$ | $$\frac{1-p}{p^2}$$ | | | Hypergeom.(N,G,n) | \[0, n] | $$\frac{\binom{G}{g}\binom{B}{b}}{\binom{N}{n}}$$ | $$n\frac{G}{N}$$ | $$n\frac{G}{N}\frac{B}{N}\frac{N-n}{N-1}$$ | | | Uniform Continuous | (a, b) | $$\frac{1}{b-a}$$ | $$\frac{a+b}{2}$$ | $$\frac{(b-a)^2}{12}$$ | | | Beta(r,s) | (0, 1) | $$\frac{\Gamma(r+s)}{\Gamma(r)\Gamma(s)}x^{r-1}(1-x)^{s-1}$$ | $$\frac{r}{r+s}$$ | $$\frac{rs}{(r+s)^2(r+s)}$$ | | |

Exponential(\lambda)

(Gamma(1, \lambda))

| $$x\ge0$$ | $$\lambda e^{-\lambda x}$$ | $$\frac{1}{\lambda}$$ | $$\frac{1}{\lambda^2}$$ | | | Gamma(r, $$\lambda$$) | $$x\ge0$$ | $$\frac{\lambda^r}{\Gamma(r)}x^{r-1}e^{\lambda x}$$ | $$\frac{r}{\lambda}$$ | $$\frac{r}{\lambda^2}$$ | | | Normal(0,1) | $$x \in \mathbb{R}$$ | $$\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}$$ | 0 | 1 | | Where $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$and $$\Gamma(r) = \int\_0^\infty x^{r-1}e^{-x}dx = (r-1)\Gamma(r-1) = (r-1)!$$ # Counting ## Introduction If you're reading this, I think it's safe to assume you already know how to count... (1, 2, 3, whatever) so what's the big deal about counting? When we say counting in this context, we mean **counting sequences of decisions.** For example, we might want to get the **total number of ways to choose toppings on a pizza** or something. There are **two main types** of problems: those where **order matters** and those where it doesn't. ## The First Rule of Counting: When the order matters Here's a sample problem: let's try to figure out the total number of unique 5-character strings we can make with the letters 'A' through 'E'. For instance, 'ABCDE' and 'DABBA' are both valid. Lots of these types of problems can be visualized using **slots,** where each slot is one character or option: ![](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MFka3X4qx2R0yzli0Ke%2Fuploads%2FW6BtPsEP6BOifhFEL9aw%2Fimage.png?alt=media\&token=46e3b9fa-04af-410a-93f3-3314875c2bcc) To get the total number of ways to fill the slots, we can **multiply the number of ways each individual slot can be filled together.** So for the problem above, we get that there are 5 ways to fill each slot, and 5 slots in total. So, $$5 \times 5 \times 5 \times 5 \times 5 = 3125$$strings. ## **The Second Rule: When the order doesn't matter** In order to tackle these types of problems, we'll need to introduce the **combinatorial** $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$. When you see this, it means "the number of ways we can choose $$n$$things from $$k$$total elements if order doesn't matter". ## Stars and Bars {% embed url="" %} When we need to split items into groups, it's sometimes nice to add **bars** that separate the items. This is great if there are particular classes of items rather than unique ones (if they're unique, just use slots.) How this works is that we can treat each item as a **star**, and the stars are separated by **bars** that designate one group from another. This means that if there are $$n$$stars and $$k$$groups, then there must be $$\binom{n+k-1}{k-1}$$total ways to split the stars into groups. One application of this is to get the total number of equations $$y\_0 + y\_1 + \cdots + y\_k = n$$for a fixed $$n$$. We can think of there being $$n$$number of ones (our stars), and $$k$$number of plus signs (our bars). There can also be an empty group (representing $$y\_i = 0$$), which bumps us up to $$k+1$$groups. By the Stars and Bars principle, there are $$\binom{n+k}{k}$$such equations for non-negative numbers. ## The Inclusion-Exclusion Principle Used to calculate the probability of the union of events. # Discrete Probability ## Probability Basics * [Adding and subtracting probabilities](http://prob140.org/textbook/content/Chapter_02/01_Addition.html) -[Multiplying probabilities: random draws without replacement, conditional probabilities](http://prob140.org/textbook/content/Chapter_02/03_Multiplication.html) ## Bayes' Rule Bayes' Rule is used to re-express conditional probabilities $$P(A|B)$$. ## Random Variables ### Probability Spaces Probability spaces describe all of the possible values of a random variable, and how likely each of those outcomes are. ### Equality Two variables are equal if $$X(\omega) = Y(\omega)$$ for all $$\omega \in \Omega$$, where $$\Omega$$ is a probability space (all possible values). # Hashing and the Union Bound A hash function assigns a value to each member in a set. It's often useful to determine the probability of collisions: where two different items are assigned the same hash value. An interesting result is explored by the [Birthday Problem](http://prob140.org/textbook/content/Chapter_01/04_Birthday_Problem.html) (sometimes known as the Birthday Paradox, despite not actually being paradoxical), in which the probability of at least two people sharing the same birthday is much higher than expected. # Expectation and Variance The expectation of a random variable, $$E(X)$$, is the average of possible values weighted by their probabilities. Formally, it can be defined in two ways: 1. Domain definition: $$E(X) = \sum\_{\omega \in \Omega} X(\omega) P(\omega)$$. 2. Range definition: $$E(X) = \sum\_x x P(X = x)$$. Expectation has nice properties of linearity: $$E(X + Y) = E(X) + E(Y)$$ and $$E(aX + b) = aE(x) + b$$. # Concentration Inequalities Markov's Inequality: Chebyshev's Inequality: Chernoff Bound:[ http://prob140.org/textbook/content/Chapter\_19/04\_Chernoff\_Bound.html?highlight=chernoff](< http://prob140.org/textbook/content/Chapter_19/04_Chernoff_Bound.html?highlight=chernoff>) # Continuous Probability ![Credit: Huiyi Zhang](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MFka3X4qx2R0yzli0Ke%2Fuploads%2FodECQllh3BwAZSKGta0B%2Fimage.png?alt=media\&token=1b404311-4289-4670-82f3-614f073a8c11) All of the continuous probability distributions are deeply connected. Above is a chart describing some of their relationships. Below are some links: * [Poisson]() * [Beta]() * [Exponential]() * [Normal]() * [Gamma]() * [Chi-Squared](http://prob140.org/textbook/content/Chapter_18/04_Chi_Squared_Distributions.html) # Markov Chains Markov Chains are a type of **stochastic process** (a collection of random variables that evolves over time) that satisfy the **Markov property** (the future state $$n+1$$ only depends on the current state $$n$$, and not any of the past states). Markov chains are often used to model transitions between discrete states. # The Beta Family The Beta distribution is a family of continuous distributions on \[0,1] with two parameters (commonly known as $$\alpha$$ and $$\beta$$, but also $$r$$ and $$s$$). ![Credit: Wikipedia](https://1127028648-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MFka3X4qx2R0yzli0Ke%2Fuploads%2FstoHFZRAEmrwjsNMj3fF%2Fimage.png?alt=media\&token=dc711390-e91c-4775-b4d0-37b8737eaa16) Beta distributions are commonly used in situations where we want to continually update a prior distribution given new information. * The `beta (1,1)` distribution is identical to the uniform distribution. # The Gamma Family # Conditional Expectation and Variance Properties: ### Conditional Expectation $$E(X|Y)$$is the conditional expectation of $$X$$given $$Y$$ * $$E(X|Y=y)$$is a fixed value, but $$E(X|Y)$$is a random variable (it is a function of $$Y$$) * Iterated expectation: $$E(E(X|Y)) = E(X)$$ * Additivity: $$E(Y+Z | X) = E(Y|X) + E(Z|X)$$ * **does not work** on the right hand side: $$E(Y | X+Z) \ne E(Y|X) + E(Y|Z)$$ * Linearity: $$E(aX + b | Y) = aE(X|Y) + b$$ * Conditioning on the same variable: $$E(g(S)T | S) = g(S)E(T|S)$$ ### Conditional Variance If $$Var(Y)$$is difficult to find directly, we can use the **variance decomposition** to condition the variance on another variable. $$ Var(Y) = E(Var(Y|X)) + Var(E(Y|X)) $$