home        


Discrete Math: Resources



Contents
  1. Useful definitions and properties
  2. Propositions, if-then statements, and straightforward proofs
  3. Sets
  4. Proof techniques
    1. Proof by contrapositive, contradiction, and smallest counterexample
    2. Proof by induction
    3. Pigeonhole principle
    4. Non-constructive existence proofs
    5. A few things to avoid
  5. Logic
  6. Binary relations and Functions
  7. Big-O notation
  8. Recurrence relations using big-O
  9. Graphs
    1. Intro
    2. Cliques, Independent sets, Ramsey numbers
    3. Connectivity and trees. Binary trees.
    4. Minimum spanning trees (MST)
    5. Planarity
    6. Vertex coloring
    7. Other graph topics
  10. Summations
  11. Combinatorics
  12. Probability
    1. Intro
    2. Conditional probability
    3. Random variables
    4. Indicator random variables
    5. More fun with probability


  1. Useful definitions and properties (This is reference material, not an actual lesson)
    • Class notes: PDF
    1. Main classification of numbers (just the definitions)
    2. Common functions: pages 53-59 in CLRS.
      • Factorial. (definition)
        • Scheinerman 2(9), Rosen p.151.
      • Floor and ceiling. (definition)
        • Scheinerman 5(29), p.208, Rosen p.149
      • Modular arithmetic. (definition and examples)
        • Scheinerman 7(37), MCS 9.6, Rosen 4.1.
      • Polynomials. (definition and arithmetic)
      • Exponentiation
        • Wiki. Pay attention to "Integer exponents", especially "Identities and properties" (3.1 to 3.4)
        • Rosen, Appendix 2.
      • Logarithm
        • Wiki. Pay attention to "Definition" (1.2), "Examples" (1.3), and identities (2.1, 2.2).
        • Rosen, Appendix 2.
      • Fibonacci numbers
    3. Series (and their sums)


  2. Propositions, if-then statements, and straightforward proofs
    • Prerequisite knowledge: basic exponent rules (see first page of notes)
    • Class notes: full slideshow and condensed
    • Video:
      • Part 1 (propositions, conjectures, notation) [11.5 min]
      • Part 2 (theorems, if-then, IFF, straightforward proofs) [29 min]
    • Textbook chapters:
      • MCS: 1.1 -- 1.7
      • Scheinerman: 1(1-6)
      • Rosen: First 10 pages.


  3. Sets
    • Prerequisite knowledge: none
    • Class notes: full slideshow and condensed
    • Video:
    • Textbook chapters:
      • MCS: 4.1 and 4.2
      • Scheinerman: 2(8,10,12)
      • Rosen: 2.1 and 2.2. Some of 2.5
      • CLRS: Appendix B.1


  4. Proof techniques

    1. Proof by contrapositive, contradiction, and smallest counterexample
      • Prerequisite knowledge: section 2. A couple definitions about prime numbers are mentioned in one proof. See first page of the notes.
      • Class notes: full slideshow and condensed
      • Video:
        • Part 1 (describing proof by contrapositive) [16 min]
        • Part 2 (three proofs by contrapositive, three proofs by contradiction, including that √2 is irrational) [25 min]
        • Part 3 (proof by contradiction: infinite number of primes. Smallest counterexample: sum of odd numbers) [17.5 min]
        • Part 4 (smallest counterexample: 2n > n2, and Fibonacci numbers grow exponentially) [13.5 min]
        • Part 5 (smallest counterexample: empty pentagons) [14min]
      • Textbook chapters:
        • MCS: 1.5, 1.8, 2.2
        • Scheinerman: 4(20,21)
        • Rosen: chapter 1.7, p.83--88


    2. Proof by induction
      • Prerequisite knowledge: section 2. [factorial of zero and sum or zero objects appear in a proof; see first page of notes]
      • Class notes: full slideshow and condensed
      • Video:
        • Part 1 [11min] (intro and a geometric series example)
        • Part 2 [32.5min] (six examples, including strong induction, and integers being products of primes)
        • Part 3 [20min] (three examples, including a lesson about failing and trying again)
        • Part 4 [21min] (two examples, focusing on recurrences)
      • Textbook chapters:
        • MCS: 5
        • Scheinerman: 4(22)
        • Rosen: 5
        • CLRS: Appendix A.2


    3. Pigeonhole principle
      • Prerequisite knowledge: number of subsets in a set, sum of powers. Section 4A. (only for some proofs; see first page of notes).


    4. Non-constructive existence proofs
      • Prerequisite knowledge: None


    5. A few things to avoid


  5. Logic
    • Prerequisite knowledge: Just a couple definitions from section 2 (see first page of notes)
    • Class notes: full slideshow and condensed
    • Video:
    • Textbook chapters:
      • MCS: chapter 3
      • Scheinerman: 1(7) and 2(11)
      • Rosen: A lot of chapter 1 is related to this material. You could look at the beginning of chapter 12 as well.


  6. Binary relations and functions
    • Prerequisite knowledge: definition of set.
    • Class notes:
    • Video:
    • Textbook chapters:
      • MCS: 4.3 and 4.4
      • Scheinerman: Relations are covered in 3(14,15). Functions are covered in 5(24)
      • Rosen: 2.3 for functions, 9.1 for relations.
      • CLRS: Appendix B.2 (for Relations). Appendix B.3 (for Functions). See p.1152 for splitting summations.


  7. Big-O notation
    • Prerequisite knowledge: it helps to be familiar with common functions (e.g., polynomial vs exponential vs logarithmic).
    • Class notes:
    • Video:
      • Spring'19 algorithms lecture. This also includes a description of Insertion sort, as justification for using bigO. You can start at 15:45. You are not responsible for anything in the video that's not in the course notes. [Remaining time: 32min]
      • part 2 of video. You can stop at 10:27. Also, I won't focus much (or at all?) on little-o or little-omega in this course.
      • Exaggerate and Simplify [22min]
    • Textbook chapters:
      • MCS: 14.7
      • Scheinerman: 5(29). Note that the definitions for big-O and big-Omega differ slightly from mine. I assume that functions are positive, which is quite standard for CS.
      • Rosen: 3.2
      • CLRS : 2, p.43-52. This textbook is consistent with how I define things.


  8. Recurrence relations using big-O
    • Prerequisite knowledge: sections 4B and 7. Geometric series.
    • Class notes: full slideshow and condensed. (This also covers Mergesort, which is a simple example of an algorithmic technique called "divide and conquer". Although this isn't a course on Algorithms, I think it's worth keeping this as part of our course material)
    • Video
      • Slideshow with audio (including slightly refreshed course notes)
      • From a 2017 lecture in an algorithms class. (Older than the above slideshow)
    • Textbook chapters:
      • CLRS: chapter 4, p.83-92


  9. Graphs

    1. Intro (examples, representation, degree, regularity, isomorphism, subgraphs)
      • Prerequisite knowledge: very little: e.g., arithmetic series, some notation for sets.


    2. Cliques, independent sets, Ramsey numbers
      • Prerequisite knowledge: section 9A
      • Class notes: full slideshow and condensed.
      • Video:
      • Textbook chapters:
        • Scheinerman: 9(48).
        • Rosen: p.404-405
      • Links
        • Ramsey numbers (cliques vs independent sets)
          • R(x,y) represents the smallest integer N such that in any graph of size at least N there is either a clique of size x or an independent set of size y.
          • Here is a wiki about R(3,3).
          • R(4,3)   Here is a link showing R(4,3)=9, without resorting to a recurrence as in the previous link. (see 2 paragraphs before the 2nd figure).
          • R(4,4): requires knowledge of R(4,3).
          • R(5,5) is unknown!
          • wiki on Ramsey's theorem. Notice that there are also Ramsey numbers with more than 2 parameters.
          • Games
            • "Sim" (wiki) is a game where 2 players take turns coloring the edges of K6. One player uses red and the other uses blue. Whoever completes a triangle of their own color loses. An extended version of the game asks two players to color K18, while avoiding coloring a monochromatic K4. There is a 3-player version as well. Ramsey theory tells us that these games cannot end in a draw.
            • A variant of sim is Hajnal's triangle-free game, discussed here. Two players take turns adding edges, with the restriction that neither can complete a triangle. However, there are no colors in this game. A player wins if the other player cannot add an edge. The game can also be played using a score that is just the total number of edges added. The goal of one player is to maximize the score, and the goal of the 2nd player is to force a configuration where no edge can be added, as quickly as possible. Finally there is also a variant with an additional constraint, where the graph must remain connected at all times.


    3. Connectivity and trees. Binary trees.
      • Prerequisite knowledge:


    4. Minimum spanning trees (MST)
      • Prerequisite knowledge:
      • Class notes: full slideshow and condensed
      • Video:
      • Textbook chapters:
        • MCS: 12.9.4 but I recommend a different source.
        • Rosen: 11.5
        • CLRS: chapter 23, p.624-629.


    5. Planarity
      • Prerequisite knowledge:
      • Class notes: full slideshow and condensed
      • Video:
      • Textbook chapters:
        • MCS: 13.1 -- 13.5
        • Scheinerman: 9(53)
        • Rosen: 10.7
      • Links
        • Euler's formula (for planar graphs)
          • The wiki on planar graphs contains a section on Euler's formula.
          • 20 proofs of Euler's formula
          • The formula V-E+F=2 is just a particular case of a far greater body of work. As mentioned in class, if you were to draw a connected graph on a sphere, you'd get the same relation; The Euler characteristic would be 2. Similarly, count the vertices, edges and faces on any convex polyhedron. Other surfaces have other characteristic numbers.
        • The role of K5 and K3,3
          • The wiki on planar graphs starts out by mentioning the theorems of Kuratowski and Wagner, which essentially say that a graph G is non-planar if and only if the shape of a K5 or of a K3,3 is present in G. See here. Look at the two figures, showing two (non-planar) graphs not directly containing a K5 or a K3,3, but that implicitly contain those shapes.
            The section that follows in the wiki discusses other planarity criteria. Theorem 1 in particular is quite simple, and easy to prove.
          • (advanced) notes on Kuratowski's theorem. The advanced part is proving that any graph not containing K5 or K3,3 as a subgraph -- or as a minor -- must be planar. In other words, non-planarity implies finding such a subgraph/minor. In our class we only discuss the other direction: i.e., that containing one of those subgraphs implies non-planarity.


    6. Vertex coloring
      • Prerequisite knowledge:
      • Class notes: full slideshow and condensed
      • Video:
      • Textbook chapters:
        • MCS: 12.6 and 13.6
        • Scheinerman: 9(52)
        • Rosen: 10.8
      • Links
        • wiki: 4 color theorem
        • wiki: Grotzsch's theorem
        • Hadwiger-Nelson problem: This is an awesome vetex coloring problem, with an infinite number of vertices: all points in the plane. It is explained nicely in this wiki.
        • Edge coloring
          • The idea here is to color edges of a graph, so that no vertex is incident to 2 edges of the same color. Of course, you must minimize the number of colors used.
          • wiki     (see the applications section).


    7. Other graph topics (if time permits)
      • Eulerian paths (covered in Scheinerman chapter 9(51), Rosen 10.5)
      • Hamiltonian paths (covered in Rosen 10.5)
      • Binary trees.


  10. Summations
    • Prerequisite knowledge: notation and some identities about summations


  11. Combinatorics
    • Prerequisite knowledge: none, but some previous results are mentioned, without affecting this topic


  12. Probability

    1. Intro
      • Prerequisite knowledge:


    2. Conditional probability
      • Prerequisite knowledge:
      • Class notes:
      • Video:
      • Textbook chapters:
        • MCS: 17-18
        • Scheinerman: 6(32)
        • Rosen: 7.2, 7.3
        • CLRS: Appendix C.2
      • Links
        • The birthday problem
          • wiki.
          • Other versions of this problem exist, e.g., how many people must be in a room for us to expect at least one birthday match? Or, if we ask people iteratively, at what point do we expect to find the first match? See the note in Section 13C, below.
          • Another question is: how many people do we expect to ask before recording all possible birthdays?
            This is known as the Coupon Collector's Problem. Here, we have n "coupons". The answer is Theta(nlogn).
          • Calculators: Wolfram, bdayprob, dcode
          • Various numbers in the universe. Near the very bottom of the table, you'll find 1080, the estimated number of particles in the universe.
        • Bayes' theorem
          • Wiki intro and examples.
          • betterexplained.com "intuitive and short explanation". I would start reading at "Anatomy of a Test". This link includes a calculator for the disease problem.
        • Monty Hall problem
          • xkcd 1282 ... some people can win this game 100% of the time.
          • BBC intro to the problem. Includes an introductory video. Read the last 3 short paragraphs on diagnostic tests.
          • Simulator. If you find a neater one, let me know.
          • Another description, including video of a lecture, and an explanation of how the conditional probability formula can be misused.
          • Blinky Monty. A variation of the game, involving some prior knowledge.
          • A research paper on an extension of the game: many doors and many offers to switch.
        • TED talk about coins, diagnosing diseases, and statistics in court cases.
        • Law of total probability


    3. Random variables
      • Prerequisite knowledge:
      • Class notes full slideshow and condensed
      • Video: Slideshow with audio [18min]
      • Textbook chapters:
        • MCS: chapter 19.1, 19.2, 19.5 (and some other small parts of chapter 19)
        • Scheinerman: 6(33,34)
        • Rosen: 7.2, 7.4
        • CLRS: Appendix C.3


    4. Indicator random variables
      • Prerequisite knowledge:
      • Class notes: full slideshow and condensed
      • Video: Slideshow with audio [32min]
      • Textbook chapters:
        • MCS: chapter 19.1, 19.2, 19.5 (and some other small parts of chapter 19)
        • CLRS: chapter 5.1, 5.2
      • Links:
        1. The hat check problem.
          • FYI - Link 1 and link 2 calculate the probability of an outcome for this problem, without IRVs.
        2. The hiring problem.
          • Link. Note that the second problem in this link, involving birthdays, is mentioned below.
          • Harmonic series (related to the hiring problem).
        3. Finding local maxima in permutations.
          • Jump to the 30:00 mark in this youtube video, which is part of Harvard's Stat 110 course. This part of the lecture lasts 9 minutes. After that is an explanation of the St. Petersburg paradox which is fun to think about. Here's the wiki on that.
        4. Counting inversions in permutations. (involves IRVs with 2 subscripts)
          • Broken link
        5. Various birthday problems.
        6. A problem with balls and bins.
          • See the second example in this link. Evaluation of the expected value of each IRV is a bit more complicated in this example than in previous ones. Note that the first example in this link is equivalent to the hat check problem. It deals with fixed points in permutations. In a permutation of the integers 1...n, a fixed point occurs when integer k is placed at position k.


    5. More fun with probability