Math 213

• Syllabus

• Course Calendar
  (Note that this calendar is potentially subject to revision, based on the needs of the class)

• Lecture 1: Motivation, set definition and notation

• Lecture 2: Set equality, subsets, power sets, cartesian products, relations, visualization with Venn diagrams

• Lecture 3: Union, intersection, set difference, complement, set identities

• Lecture 4: Proof strategies for set identities, membership tables, basic definitions for functions

• Lecture 5: Injections, surjections, bijections, inverses and compositions of functions, graphs of functions, definitions of floor/ceiling/factorial functions

• Lecture 6: Algorithms, pseudocode, and the greedy-change problem

• Lecture 7: Greedy-change problem continued, scheduling problem, introduction to big-O notation

• Lecture 8: Growth of combinations of functions, Big-Omega notation, Big-Theta notation, complexity of algorithms

• Lecture 9: Principle of mathematical induction, structure of inductive proofs, summation formula and inequality examples

• Lecture 10: More examples of inductive proofs (divisibility and set identities), common errors in inductive proofs

• Lecture 11: Strong induction, well-ordering property

• Lecture 12: Introduction to counting (product and sum rules)

• Lecture 13: Subtraction rule, division rule, pigeonhole principle

• Lecture 14: Generalized pigeonhole principle, permutations, combinations

• Lecture 15: Permutation and combination examples, binomial coefficients, binomial theorem, examples of combinatorial proofs

• Lecture 16: Proofs by double-counting, Pascal's Triangle, Pascal's Identity, Vandermonde's Identity, introduction to combinations and permutations with repetition

• Lecture 17: Multichoose and multiset notation, more combinations with repetition, indistinguishable objects, modeling counting problems with boxes and balls

• Lecture 18: Modeling counting problems with boxes and balls, introduction to discrete probability

• Lecture 19: Examples of computing discrete probabilities, sampling with and without replacement, complementary events, unions and intersections of events

• Lecture 20: Probability distributions, uniform probability, examples of non-uniform probability distributions

• Lecture 21: Pairwise independence, mutual independence, conditional probability, Bernoulli trials, binomial distribution

• Lecture 22: Binomial distribution example, Bayes' Theorem

• Lecture 23: Sequences, recurrence relations, Fibonacci's rabbit problem, Tower of Hanoi problem

• Lecture 24: Finding closed formulas via iteration, more recurrence relation examples, classifying recurrence relations

• Lecture 25: Definition of characteristic equation, solving linear homogenous recurrence relations with constant coefficients

• Lecture 26: Examples of solving linear homogeneous recurrence relations, linear nonhomogeneous recurrence relations

• Lecture 27: Particular solutions to nonhomogeneous recurrence relations, motivating the principle of inclusion-exclusion

• Lecture 28: Principle of Inclusion-Exclusion, basic examples of applying the PIE to enumerative questions

• Lecture 29: Applications of Inclusion-Exclusion, including the hatcheck problem

• Lecture 30: Definition of a relation, basic properties (symmetric, antisymmetric, reflexive, transitive), many examples

• Lecture 31: Composites of relations, matrix representations of relations (properties and computing unions/intersections)

• Lecture 32: Matrix representations of composites of relations, digraph representations of relations, definition of equivalence relations

• Lecture 33: Examples and non-examples of equivalence relations, equivalence classes, partitions

• Lecture 34: Introduction to Graph Theory, basic definitions and many examples

• Lecture 35: Degree, in-degree, out-degree, neighborhoods, Handshake Theorem, Directed Handshake Theorem, common types of simple undirected graphs

• Lecture 36: Bipartite and complete bipartite graphs, definition of a graph isomorphism, some graph invariants, definition of adjacency matrices

• Lecture 37: Definition of adjacency matrices for directed graphs, properties of adjacency matrices, isomorphisms via adjacency matrices, definition of incidence matrices

• Lecture 38: Incidence matrices for directed graphs, paths, circuits, connected and disconnected graphs, subgraphs

• Lecture 39: Vertex connectivity, edge connectivity, Whitney's Theorem

• Lecture 40: End of the proof of Whitney's Theorem, connectivity for directed graphs, counting paths with adjacency matrices, logistical information about the final exam and other end-of-semester matters

• Writing Inductive Proofs

• Errors in Inductive Proofs: PDF, TEX, Solutions

• Flow chart for solving linear recurrence relations with constant coefficients

As mentioned in the syllabus, I highly encourage typesetting assignments rather than writing by hand. You may wish to do so using Overleaf, which is free and cloud-based. If you would find it helpful, I have created a basic template for homework in this course (the TeX code is available here). You are not required to use this template or to use LaTeX.

• Homework 1: PDF, TeX (UPDATED 1/26)
  Solutions: PDF, TeX

• Homework 2: PDF, TeX
  Solutions: PDF, TeX

• Homework 3: PDF, TeX
  Solutions: PDF, TeX
  Induction Handout: PDF

• Homework 4: PDF, TeX
  Solutions: PDF, TeX

• Homework 5: PDF, TeX
  Solutions: PDF, TeX

• Homework 6: PDF, TeX
  Solutions: PDF, TeX

• Homework 7: PDF, TeX (NOW DUE WEDNESDAY, MARCH 30TH)
  Solutions: PDF, TeX
  Linear recurrence relation flow chart: PDF

• Homework 8: PDF, TeX
  Solutions: PDF, TeX

• Homework 9: PDF, TeX (NOW DUE MONDAY, APRIL 18TH)
  Solutions: PDF, TeX

• Homework 10: PDF, TeX (NOW DUE WEDNESDAY, APRIL 27th)
  Solutions: PDF, TeX

• Quiz 1: Key

• Quiz 2: Key

• Quiz 3: Key

• Quiz 4: Key

• Quiz 5: Key

• Quiz 6: Key

• Quiz 7: Key

• Quiz 8: Key

• "Guidelines for good mathematical writing," by Francis Su.

• Detexify, a web app for identifying the LaTeX command(s) for various symbols.

• Overleaf, a cloud-based LaTeX editor.

• GraTeX, a free tool for generating TikZ code for graphs.