Notes
Schedule: Wednesdays 6pm9pm and Saturdays 10am4pm.
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 nonnegative 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 ksubsets of an nset is n(n1)…(nk+1)
 Or, n! / (nk)!

The number of ksubsets of an nset is n! / (k!(nk)!)
 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 (n1 choose k1)
 n1 points where you can swap out a child for another child, we have to select k1 of those points (since first child always starts at beginning)
 ** The number of ways to distribute n identical pennies to k children is (n+k1 choose k1)
 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’sEye View
 It’s symmetrical
 Entries increase until middle, then decrease
 Identity: (n choose k+1) / (n choose k) = (nk) / (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 doublecounting 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 onetoone 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 onetoone 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
 New information updates your model of the world!
 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 fractionlike, 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 deadends, 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:
 State your game plan
 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 ifpart is false or the
thenpart 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 nphard
 “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 (p21p27)

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(m1) 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 (p73p81)

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 (p98p110)
 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
 nphard to find them
 Not a ton known
7  Linear algebra crash course
Essence of Linear Algebra Videos 17
https://www.youtube.com/watch?v=kjBOesZCoqc&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab&index=1
 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
 Tranformation analogous to function; in linear algebra,
generally a vector input and vector output
 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, matrixvector 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
Threedimensional 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 nongeometric definitions of vector  still need to conceptualize a 26dimensional 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 (p5573)
 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: Onetime pads (p117123)
 Safer cryptography
 Onetime 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
 Chess move example, read and intake please
 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^(p1) ~= 1 (mod p)
 Okay, now for RSA
 Rewrite Fermat: a^((k)(p1)) = 1 (mod p)
 Because 1^(anything) is 1
 Then a^((k)(p1) + 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 (p1)(q1))
 So, ed = k(p1)(q1)
 Combine all this, need to prove:

p m^(k(p1)(q1)+1)  m 
q m^(k(p1)(q1)+1)  m
