– 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