    Schedule: Wednesdays 6pm-9pm and Saturdays 10am-4pm.

### 1 - Counting Things

#### LL Ch 2: Let us count!

##### Sets and the like
• Gg, combinatorials and permutations, okay
• Formalize these counting operations using a set, made up of elements. Deck of cards, people in a group are both sets
• R for real numbers, Q for rational numbers, Z for all integers, Z+ for all non-negative integers, N for all positive integers, 0 for empty set
• b ∈ A if b is in A
•  Cardinality of A (number of items) is A
• Denote items in set with curly braces
• B is subset of C if every element of B is also an element of C. Would say B ⊆ C
• Intersection is set consisting of elements that are in both sets
• Disjoint sets have the empty set as their intersection
##### The number of subsets
• A set with n elements has 2^n subsets
• Can use a binary representation of integers (on/off) to represent whether or not item is in a given subset. Helps you prove the above theorem
• Useful to play around with powers of 2 and 10 to get a ballpark estimate of the order of magnitude of a number or set
##### Sequences
• Number of strings of length n composed of k given elements is k^n
• Suppose that we want to form strings of length n so that we can use any of a given set of k1 symbols as the first element of the string, any of a given set of k2 symbols as the second element of the string, etc., any of a given set of kn symbols as the last element of the string. Then the total number of strings we can form is k1 ·k2 ·…·kn
##### Permutations
• Permuting an ordered list of n objects is rearranging it in a different order. Each rearrangement is a permutation
• The number of permutations of n objects is n!
• Stirling’s Formula: n! ∼ (n/e)^n(√2πn)

#### Lecture

• When in doubt about naive set theory/properties, draw the venn diagram inside the universe and look at it

### 2 - Advanced counting things

#### - LL Book Ch 4 - Binomial Theorem

##### Binomial stuff
• The number of ordered k-subsets of an n-set is n(n-1)…(n-k+1)
• Or, n! / (n-k)!
• The number of k-subsets of an n-set is n! / (k!(n-k)!)
• Call this n choose k
• We overcounted by k!, duhhhhhhh
• N choose K are binomial coefficients
• The Binomial Theorem: https://gyazo.com/231b62be4247dc22294f42387d585611
##### Distributing presents
• What if you need to distribute things
• Number of ways to distribute n things between k children is n! / (n1!n2!…nk!). You overcounted all of the permutations (n!) where each child still got the same set of presents
##### Distributing money
• Presents are distinguishable, pennies are not. Thus, fewer distinct ways to distribute pennies
• The number of ways to distribute n identical pennies to k children, so that each child gets at least one, is (n-1 choose k-1)
• n-1 points where you can swap out a child for another child, we have to select k-1 of those points (since first child always starts at beginning)
• ** The number of ways to distribute n identical pennies to k children is (n+k-1 choose k-1)
• Man, my poor brain

#### LL Book Ch 5 - Pascal’s Triangle

• I’ve seen this before
• Formula for finding the proportion between the middle entry and the entry at index t
##### Identities
• Every number is the sum of the two numbers immediately above it
##### Bird’s-Eye View
• It’s symmetrical
• Entries increase until middle, then decrease
• Identity: (n choose k+1) / (n choose k) = (n-k) / (k+1)
• This got real deep real fast fam

#### Lecture

• Draw out the combinations thing by with m or n = 3
• Every time you choose down first, you’re double-counting blah blah
• Note: function in math and function in programming are NOT equivalent
• Function is mapping of inputs to outputs; programming “functions” are more like procedures
• Function maps each item from set X to precisely one value of set Y
• X is domain, Y is range
• Surjective “on to”: every value of X maps on to a value of Y. The entire output range is covered/reachable
• Injective “one to one”: every value of X maps one-to-one to Y
• Real numbers->Real numbers for a squaring function is injective but not surjective - it’s a one to one mapping, but negative real numbers in the range are not reachable
• Bijective: both surjective and injective
• Bijection: a one-to-one mapping that covers the entire output space

### 3 - Probability

#### LL Book Ch 7

• Probability theory: way of modeling dependence of outcomes on chance
• Probability space or sample space is the set of possible outcomes
• We only consider uniform spaces, where each outcome has the same probability
##### Independent repetition
• Independence of events: information about one doesn’t influence probability of other
• Null set independent from every event
##### The Law of Large Numbers
• Let 0 ≤ t ≤ m. Then the probability that out of 2m independent coin tosses, the number of heads is less than m − t or larger than m + t, is at most m/t2.
• Corollary: With probability at least .99, the number of heads among 2m independent coin tosses is between m − 10√m and m + 10√m. -

#### Lecture

• Bayes Bayes Bayes

### 4 - Logic

#### MCS Ch 1 (25 pages)

• A mathematical proof of a proposition is a chain of logical deductions leading to the proposition from a base set of axioms
• A proposition is a statement (communication) that is either true or false.
• Up to us to prove or disprove
• For programmers, very important to be able to prove correctness of programs and systems if possible
• A predicate can be understood as a proposition whose truth depends on the value of one or more variables
• e.g. “n is a perfect square”
• Axioms are things that are accepted as true
• Theorems are important true propositions
• Lemmas are preliminary propositions useful for proving later propositions
• Corollaries are propositions that follow in just a few logical steps from a theorem

• Hard to tell if you should or should not be assuming something, so best practice is to be very up front about your assumptions
• Inference rules, or logical deductions, are used to prove new propositions using previously proved ones
• Modus ponens: a proof of P + proof that P implies Q equals a proof of Q
• Written fraction-like, where antecedents are above the line and conclusion is below the line
• Sound inference rule: assignment that makes all antecedents true must also make the conclusion true
• Woohoo, some proof templates. See book
• You’ll often need to do some scratchwork while you’re trying to figure out the logical steps of a proof. Your scratchwork can be as disorganized as you like—full of dead-ends, strange diagrams, obscene words, whatever. But keep your scratchwork separate from your final proof, which should be clear and concise.
• Proofs typically begin with the word “Proof” and end with some sort of de- limiter like [square] or “QED.” The only purpose for these conventions is to clarify where proofs begin and end.
• Read through the different types of proofs
• Proof by contradiction, by cases, etc.
• Proofs are tough. Some tips:
• Keep a linear flow
• A proof is an essay, not a calculation
• Avoid excessive symbolism
• Revise and simplify
• Introduce notation thoughtfully
• Structure long proofs
• Be wary of the “obvious”
• Finish!
• Come back and do problems?

#### MCS Ch 3 - Logical Formulas (21 pages)

• Need a special language for precise communication because of ambiguities in other written/spoken language
• Not/And/Or change or combine propositions, just like in boolean logic
• iff is if and only if: true if both sides are the same
• An implication is true exactly when the if-part is false or the then-part is true. Okay
• “If pigs could fly, then your account won’t get hacked” is a valid mathematical implication, but remember that it ignores causal connections :)
• This stuff comes up all the time as boolean (or otherwise) logic in computer programs
• Simplifying these boolean expressions is nice
• Bleh, some cryptic notation
• Implications and their contrapositives are logically equivalent - “If I am hungry, then I am grumpy” == “If I am not grumpy, then I am not hungry”
• Converse (If I am grumpy, then I am hungry) is not necessarily true though
• Formula is valid iff it is equivalent to T
• Formula is satisfiable if it can be equivalent to T under certain circumstances
• E.g. if you need to fit all of the specs, the set of specs must be satisfiable (the && of all specs must be achievable)
• Disjunctive form of a propositional formula is pretty much the most naive way to write it - expand all of its terms and write it as ORs of all the AND terms: (true evaluation) || (true evaluation) …
• Conjunctive form is the expansion of all terms that evaluate to false: (false evaluation) || (false evaluation) …
• Using truth tables works for small expressions, but for larger ones may need to use algebra to prove equivalence
• Use properties of booleans and such
• Problem of deciding whether a proposition is satisfiable is SAT
• This is np-hard
• “For all”, “sometimes” are statements that quantify how often a predicate is true. An assertion that a predicate is always true is a universal quantification, assertion that predicate is sometimes true is existential quantification
• Changing order of quantifiers changes meaning of proposition most of the time
• Ayyah, okay, lots of this was over my head, but at least I got a somewhat general idea

#### Lecture

• All the set stuff translates to logic: the truth set is the set of values that satisfy a predicate or something

### 5 - Induction

#### LL Ch 3 (p21-p27)

• Mathematical induction: say you want to prove a property of positive integers, and you can prove:
• 1 has the property
• Whenever n - 1 has the property (n >= 1), then n has the property as well
• Principle of induction says that if you meet these two criteria every positive integer fits these criteria
• Process: try to prove statement for n, allowing to use that the statement is true if n is replaced by n - 1. If can’t do this, can’t prove :)
• Do exercises
• Okay, walkthrough of counting regions
• The +1 comes from the bottom of the blackboard - if 4 intersections, 5 regions

#### Lecture

• Reason through stuff! Use more rigor than “hackers” might
• Rational numbers: basically, every possible pair of integers that can be expressed as a fraction
• Isomorphic: bijection between these two things
• Induction: prove base case + continuation over anything that’s countable
• Countable: bijection with natural numbers
• Aliph naught (X0) is the size of a countably infinite set
• Can use induction to prove things about aliph naught sets

• Proof format
• Theorem: blah blah
• Proof: we use mathematical induction
• Base case: …..
• Inductive case: suppose that [base case]. Then, [prove inductive case using inductive hypothesis] as required. Therefore, the theorem holds true

• Strong induction: basically, prove more stuff
• Induction step: If P(m), P(m+1), P(m+2)… P(k) is true then P(k+1) is true as well for some k > m.
• Prove more stuffs
• Use strong induction if P(m-1) doesn’t directly help you solve P(m)
• Graph with K connected components, number of edges is bounded by Sum from 1 to k of (ni choose 2) where ni is the cardinality of the ith copmonent’s vertices

### 6 - Graph Theory

#### LL Ch 9 (p73-p81)

• Graph is nodes connected by edges
• Each edge is a set {u, v}
• Use graphs whenever you have a “relation” between certain objects (atoms, connections, descendence, etc.)
• In every graph, the number of nodes with odd degree is even
• The sum of degrees of all nodes in a graph is twice the number of edges
• Empty graph: nodes but no edges
• Complete graph (clique, strongly connected component): make all th edges
• Cycle: connect consecutive nodes until you get back to the first
• H is subgraph of G if you can get H from G by deleting notes
• Connected graph: every 2 nodes can be connected by apath
• Cool, playing around with graphs and such

#### LL Ch 12 (p98-p110)

• Ok
• Bipartite graph has two sides, connected from side to side in a given way, nodes on the same side don’t have connections
• Perfect matching: set of edges in bipartite graph such that each node is incident with exactly one of them
• Degree is how many nodes each node is connected to
• If every node of a bipartite graph has the same degree d>=1, then it contains a perfect matching
• Or, for every k nodes on the left, there must be at least k nodes on the right connected to at least one of them (see below)
• Marriage Theorem: A bipartite graph has a perfect matching if and only if |A| = |B| and for any subset of k nodes of A there are at least k nodes in B that are connected to one of them
• Proof: try and prove that if a “good” (satisfying conditions of marriage theorem) bipartite graph then it can be partitioned into two good bipartite graphs, broken down so on and so forth
• Ayyah, okay
• Okay, now you can see if a bipartite graph has a perfect matching - but how to actually find it?
• Matching: a set of edges that have no endpoint in common
• Becomes perfect when edges cover all the nodes as well, but regular matchings can be much smaller
• Augmenting path: path that starts and ends at nodes that are unmatched by your matching M; every second edge of P belongs to M
• If we find one, delete edges of P that are in M an dreplace them by edges of P that are not in M
• Keep doing augmenting path until you find perfect matching or there’s no more augmenting path
• If no more augmenting path, no perfect matching!
• Almost augmenting: everything but the last edge in augmenting path; ends with a node in M
• Hamiltonian cycle is a cycle that contains all nodes of a graph
• In perfect matching every node belongs to one edge, in Hamiltonian cycle every node belongs to two edge
• np-hard to find them
• Not a ton known

### 7 - Linear algebra crash course

#### Essence of Linear Algebra Videos 1-7

• People end up understanding linear algebra on a numerical level (i.e. how to do a matrix multiplication from memory), but you’d rather have a geometric understanding so that you have an intuition for which tools to use when
• Core visual intuitions underlie the subject
##### Vectors, what even are they?
• Physics definition: arrow pointing in space; defined by length + direction
• CS definition: ordered list of numbers, i.e. [square footage, price] tuple for houses
• Math definition: generalizes both of these; anything that can be sensibly joined or added. Use more concrete setting most of the time
• When you hear vector, think about arrow in coordinate system starting at the origin
• Then, coordinates can be used to translate into a list of numbers :)
• Pair of numbers is a bijection with vectors: (x, y)
• In 3D, just add one more number
• Every topic in linear algebra centered around vector addition and multiplication by numbers
• To add: move tail of 2nd to head of 1st, then draw new vector from tail of 1st one to new head of 2nd one, new vector is the sum. Cool. Visual :)
• To multiply: Stretch out to be a multiple of original length
• Called “scaling” –> scalar is the factor you stretch out by
• Visual visual
##### Linear combinations, span, and basis vector
• Subtlety to thinking about vector coordinates: think of both the x and y coordinates as scalars on the ^i (1, 0) and ^j (0, 1) vectors
• Cool
• ^i and ^j are the basis vectors (the things that are scaled by the coordinates zzz)
• Can reach any possible vector from any basis vectors
• Linear combination is scaling and then adding
• Span of two scalars is the set of all their linear combinations
• Span of most pairs of 2D vectors is all 2D vectors
• Unless they line up, then it’s all vectors whose tip lines on that line
• Tip: Think of individual vectors as lines, think of sets of vectors as points
• What is the span of two 3D vectors?
• A 2D plane? Yes
• Span of three 3D vectors is the entire 3D space
• Linearly dependent vectors: one vector in a set of three can be expressed in terms of the linear combinations of the other two vectors
• If this isn’t the case, they’re linearly independent
• The basis of a vector space is a set of linearly independent vectors that span the full space
• okay
##### Linear transformations and matrices
• Linear transformations* relationship to matrices :thinking_face:
• Linear transformation
• Tranformation analogous to function; in linear algebra, generally a vector input and vector output
• In 2D: think of transformation as operation on the entire 2D grid
• Linear ones: all lines must remain lines, origin remains fixed in place
• How to describe linear transformation numerically? Just give the new basis vectors :)
• Ez visualization
• Any 2D linear transformation is described by the coordinates of new ^i and new ^j, woohoo
• Whoa, matrix-vector multiplication explained :)
• Any transformation can be described by a 2x2 matrix
• This is intuitive! Columns in 2x2 matrix are the new basis vectors, and the 2x1 vector is just the original coordinates
• Matrices transform space!!!!!!!!!!!!
##### Matrix multiplication as composition
• Composition can be defined by recording where ^i and ^j land after two successive transformations
• This is matrix multiplication: applying one transformation after another
• How to get composition without looking at animation? 2x2 matrix multiplication. zzz. Ayyah
• Apply first transformation to ^i, then multiply by second to get the final spot for ^i
• Order doesn’t matter
• Good explanation > symbolic proof
##### Three-dimensional linear transformations
• Whew, [3x3][3x1]. Okay
• Zuggly
##### The determinant
• ¿Cuál es?
• How are areas squished or scaled by a linear transformation?
• Measure factor by which area of given region increases or decreases
• If the area bounded by the basis vectors goes from 1->6, then you say the transformation scaled the space by 6
• Whatever happens to one square must happen to every other square!
• The determinant is the scaling factor of a transformation
• If determinant is 0, you got squeezed into a smaller dimension
• Focus on 1x1x1 cube for 3 dimensions, focus on 1x1 square for 2 dimensions
• In 3D, slant object that cube turns into is parallelepiped
• How to compute determinant?
• ad - bc where matrix is [a b, c d]
• With 3D, • Why does det(M1M2) = det(M1)det(M2)
• Basis vectors end up in same place, so the area scale is the same

#### Lecture

• Don’t get too attached to geometric or non-geometric definitions of vector - still need to conceptualize a 26-dimensional vector sometimes!
• Dot product is the projection of one vector onto another (using right angle yaya)
• Fractal is an object with infinite surface area, bounded volume

### 8 - Cryptography

#### LL Ch 8: Integers, divisors, and primes (p55-73)

• Properties of integers, AKA Number Theory
•  *1 a* means a is divisible by 1
• Primes are not divisible by any other integer than 1, -1, p, and -p
• Lots to understand still!
• Every number has a unique basic prime factoring :)
• Difficulty of prime factorization and finding new primes is still ridiculous
• Fundamental Theorem of Number Theory: Every positive integer can be written as the product of primes, and this factorization is unique up to the order of the prime factors
• No integer can have two different prime factorizations
• The number sqrt(2) is irrational (cannot be written as the ratio of two integers)
• There are infinitely many primes
• For every positive integer k, there exist k consecutive composite integers
• Big gaps between primes!
• Composite Integer: integer n > 1 that is not a prime
• Twin primes: primes that are two apart
• Prime number theorem: number of primes among 1, 2, …n is ~ (n/ln(n))
• Sketchy
• More, more, more!
• Fermat’s Little Theorem: If p is a prime and a is an integer, then a^p - a is divisible by p

• So what do we do with these primes and prime factors?
• Find the GCF (greatest common factor) - biggest thing that is a common factor
• Relatively prime numbers have a GCF of 1
• LCD is the least common divisor, can get it from the common prime factors, okay
• Ugh I remember this shitty way to find the GCD using Euclidean algorithm. Fine maybe it’s not shitty I just didn’t much enjoy doing it
• The number of steps of the euclidean algorithm, applied to two positive integers a and b, is at most log2(a) + log2(b)

• How to test number for primality?
• Whew

#### LL Ch 15: A glimpse of cryptography (p117)

• Cryptography: the science of secret communication
• Message to send is plaintext
• Key is what unlocks the translation from ciphertext to plaintext
• Naive/simple: substitution code, replace each letter of alphabet with another one :)

#### LL Ch 16: One-time pads (p117-123)

• Safer cryptography
• One-time pad is randomly generated string of 0’s and 1’s
• Both parties share the pad, do a bitwise operation on the plaintext to produce ciphertext, and vice versa
• Primes!
• It is easy to test whether a number is a prime (and thereby it is easy to compute the encryption), but it is difficult to find the prime factors of a composite number (and so it is difficult to break the cryptosystem)

• RSA encryption
• K

#### Lecture

• Use a clock metaphor for modulo arithmetic
• The multiplicative inverse of a(mod b) exists if gcd(a, b) is 1

• Oz walking through RSA
• “RSA is computer science’s most successful bijection”; function from set of all possible plaintext messages to all ciphertext messages
• D(E(m)) = m; for there to be an equivalent D for E, E must be a bijection
• Generaate two large primes p and q
• n = p * q
• Message will be integer m so that 0 less than m less than n
• Encryption: E(m) = x; x = rem(m^e, n)
• Decryption: D(x) = m; m = rem(x^d, n)
• GCD: tiling problem (biggest tiles you can use to perfectly tile a rectangular space?)
• Fermat: you can always construct a bijection because if p is prime, then a and p must be coprime. Now you can check if a number is prime
• a^(p-1) ~= 1 (mod p)
• Okay, now for RSA
• Rewrite Fermat: a^((k)(p-1)) = 1 (mod p)
• Because 1^(anything) is 1
• Then a^((k)(p-1) + 1) = a (mod p)
• Can’t find private key given public key!
• Used extended Euclid (GCD) algorithm (or the Pulverizer) to find the multiplicative inverse of e, which is d, which is part of the private key
•  Need to show that n (m^(ed) - m)
• Know that n is the product of two primes p and q
• So if p and q both individually divide into that expression, then n must divide into that expression
• Remember, ed ~= 1 (mod (p-1)(q-1))
• So, ed = k(p-1)(q-1)
• Combine all this, need to prove:
•  p m^(k(p-1)(q-1)+1) - m
•  q m^(k(p-1)(q-1)+1) - m