– Sets and subsets
– Power set
– Common notations
– How to specify a set
Lecture 2
– The penny problem
– Set operations: union, intersection, difference and complement
– Disjoint sets
– Venn diagram
– (A \cup B)^c = A^c \cap B^c
Lecture 3
– Cardinality
– Inclusion–exclusion principle
– Cartesian plane and cartesian product
– Notation for intervals
– Functions: definition, domain, codomain and image
– Graph representation
– Absolute value
– Bounded functions
Lecture 4
– Injective, surjective and bijective functions
– Composition of functions
– The inverse of a bijective function
– Floor and ceiling
Lecture 5
– Algorithms: definition and general properties
– Linear search
– Binary search
Lecture 6
– Binary search (continuation)
– Bubble sort
– Insertion sort
– The greedy change-making algorithm
Lecture 7
– The halting problem
– The growth of functions (Big-oh, Omega and Theta)
Lecture 8
– how to show that a function is not big-oh of another function
– Exponential, logarithmic and polynomial growth
– Time complexity of the maximum search and the linear search Algorithms
Lecture 9
– Time complexity of the binary search algorithm
– Principle of mathematical induction
– Sum of the first n positive integers
– Sum of the first n positive odd numbers
Lecture 10
In this lecture, we proved the following identities:
- For every n \in \mathbb{N}, we have 1+2+\ldots+2^n = 2^{n+1}-1
- For every a \in \mathbb{R}, \, r \in \mathbb{R}\setminus \{1\} and n \in \mathbb{N}, we have a + ar + \ldots + ar^n = \dfrac{ar^{n+1}-a}{r-1}
- For every n \in \mathbb{N}, we have 1 + \dfrac{1}{2} + \ldots + \dfrac{1}{n} \ge 1 + \dfrac{n}{2}
- For every n \in \mathbb{N}, we have 3 \vert (n^3 - n)
Lecture 11
– Strong induction
– Every integer greater than 1 can be written as a product of primes
– Simplified version of the Nim game (two piles with the same number of matches)
– Well-ordering principle
Lecture 12
– Euclidean division (Example 5, page 341)
If a \in \mathbb{Z} and d \in \mathbb{N}, then there are unique integers q and r such that 0 \le r < d and a=dq+r .
– The product rule (page 386)
– Example 2 (page 386)
– Examples 6 and 7 (page 387)
Lecture 13
– Solving questions of the mock exam
Lecture 14
– Recalling the product rule (page 386)
– The sum rule (page 389)
– Example 12 (page 389)
– Example 16 (page 391)
– Principle of inclusion–exclusion (subtraction rule, page 393)
– Example 18 (page 393)
Lecture 15
– The division rule (page 394)
– Example 20 and its generalization (page 394)
– Tree diagrams (page 394)
– Example 22, finding the solution with the tree diagram and without it (page 395)
– Pigeonhole principle (page 399)
– Example 3 (page 400)
– The generalized pigeonhole principle (page 401)
Lecture 16
– Recalling the generalized pigeonhole principle (page 401)
– Example 5 (page 401). Note that the same holds if the number of people was 97,98,\ldots, 108.
– Introduction to Ramsey theory (page 404)
– Permutations (page 407)
– Theorem 1 and corollary 1 (page 408)
Lecture 17
– Theorem 2 (page 410)
– Corollary 2 (page 411)
– The binomial theorem (page 416)
– Corollary 1 (page 417)
– Corollary 2 (page 417)
Lecture 18
– Theorem 2: Pascal’s identity (page 418)
– Pascal’s Triangle (page 419)
– Curiosity: Singmaster’s conjecture (see Wikipedia and The Open Problem Garden)
– Vandermonde’s identity (page 420)
– Corollary 4 (page 420)
Lecture 19
– Theorem 1 (page 423)
– Number of strings of size n containing only 0’s and 1’s: 2^n
– Number of strings of size n containing only 0’s and 1’s and exactly r number 1’s : \binom{n}{r}
– Number of solutions for the equation x_1+x_2+\ldots+x_n = r when all variables are non-negative numbers: \binom{n+r-1}{r}
(This is Theorem 2 (page 425) in the book)
In class we made a bijection from this set of solutions to the set of sequences of 0’s and 1’s with exactly r-1 number 1’s.
– Example 4 (page 426)
– Example 5 (page 426)
Lecture 20
– Example 7 (page 427)
– Theorem 3 (page 428)
– Probability space (sample space, sigma-algebra and probability measure). See the definition here.
Observations:
– As we are dealing with discrete structures, in our case the sigma-algebra will always be the power set of the sample space;
– In most cases our probability measure will be just the uniform probability measure.
That is, the probability measure of a set E (which we call event E) is \mathbb{P}(E) = |E|/|S|, where S is the sample space.
Recall that |A| denotes the number of elements in a set A.
– Definition 1 (page 446)
– Example 1 (page 446)
– Example 2 (page 446)
Lecture 21
– Example 4 (page 447)
– The Monty Hall Three-Door Puzzle and its One-Hundred-Door variation
– Theorem 1 (page 449)
– Theorem 2 (page 449)
Lecture 22
– Example 7, page 448
– Probabilities of complements: theorem 1, page 449
– Probability of the union of two events: theorem 2, page 449
– Conditional probability: definition 3, page 456
– Example 3, page 456
– Independent events: definition 4, page 457
– Example 5, page 457
Lecture 23
– Definition of mutual independence: definition 5, page 458
– Definition of random variable:
A random variable in a probability space (\Omega, \mathcal{F},\mathbb{P}) is a function X: \Omega \to \mathbb{R} such that
the set \{\omega \in \Omega: X(\omega) \le t\} belongs to \mathcal{F} for every t \in \mathbb{R}.
– Definition of Bernoulli and binomial random variables. See these notes. Ignore what it is written about variance and expectation. We will see this later.
– Theorem 2, page 459
Lecture 24
– Solution of the problems in the mock exam.
Lecture 25
– Recalling what is a Binomial random variable and what is a Bernoulli random variable
– Lemma (revisited): If B \sim \text{Bin}(n,p), then \mathbb{P}(B = j) = \binom{n}{j}p^{j}(1-p)^{n-j}
– Definition of expected value for discrete random variables ( definition 1 in page 478 and theorem 1 in page 479)
– Examples: expected value of Bernoullis and Binomial random variables (theorem 2 in page 479)
Lecture 26
– Linearity of expectations (theorem 3, page 480)
– Example 4, page 481: expected value of the sum of the two numbers that appear when a pair of fair dice is rolled
– Example 5, page 481: calculating the expected value of a binomial random variable using linearity of expectation
– Markov’s inequality. See these notes.
Lecture 27
– Definition of Variance
– Chebychev’s inequality
– The tail-sum formula. See the proof here
– Example 10, page 485
– Definition 2, page 485 (Geometric distribution)
– Expectation of geometric random variables. See the proof here (Theorem 15.3 is just the tail-sum formula)
Lecture 28
– Definition of clique on n vertices. Notation: K_n
– Definition of G(n,p)
– Expected number of edges in G(n,p) is p\binom{n}{2}
– Expected number of K_{\ell} in G(n,p)
– Theorem 4, page 465 (Lower bound on the Ramsey number R(\ell).
Lecture 29
– Basic terminology. Pages 651 and 652, Definitions 1, 2 and 3.
– The handshaking lemma, page 653, Theorem 1.
– The number of graphs with vertex set \{1,2,\ldots,n\} is 2^{\binom{n}{2}}. See here.
– What is a bipartite graph, page 656, Definition 6.
– Page 657, Theorem 4
Lecture 30
– Extremal number of a graph. See here until slide 7.
– Mantel’s theorem. In class, we gave the 4th proof in these notes.
Lecture 31
– Definition of path
– Definition of cycle
– A graph is bipartite if and only if all the cycles have even length. See here or here.
Lecture 32
– Matchings, page 659
– The size of a perfect matching
– Let G(X,Y) be a bipartite graph with parts X and Y.
Then, the largest matching in G(X,Y) has size at most \min\{|X|,|Y|\}.
– Necessary conditions for perfect matchings in bipartite graphs
Lecture 33
– Proof of Hall’s theorem.
The proof is in Wikipedia. See the section ‘Graph theoretic formulation’
Lecture 34
– Definition of subgraph
– We say that a graph G contains a copy of a graph H if there exists a function f:V(H)\to V(G) such that \{f(a),f(b)\} \in E(G) whenever \{a,b\} \in E(H).
– Definition of connected component
– Definition of connected graph
– Definition of vertex and edge cuts
– The size of the smallest vertex cut is at most the size of the smallest edge cut