|
Discrete Math II (Fall 2024) |
Lecture Notes |
||
| Notes | Video | |
|
8/19/2024: We discussed graphs and graph models. Notes from 8/19/24 |
Video from 8/19/24 | |
|
8/21/2024: We discussed the traveling salesman problem, degrees of vertices in graphs, and complete graphs. Notes from 8/21/24 |
Video from 8/21/24 | |
|
8/23/2024: We defined the neighborhood of a vertex or set of vertices and adjacent vertices in a graph, introduced cyclic, bipartite, and complete bipartite graphs, and we discussed the Handshake Theorem. Notes from 8/23/24 |
Video from 8/23/24 | |
|
8/26/2024: We defined the adjacency matrix of a graph, and also we defined what it means for graphs to be isomorphic. Notes from 8/26/24 |
Video from 8/26/24 | |
|
8/28/2024: We looked at ways of determining when two graphs are isomorphic or not, and we determined what that means for the adjacency matrix of each graph. Notes from 8/28/24 |
Video from 8/28/24 | |
|
8/30/2024: We defined path, circuit, simple path, and we defined what it means for a
graph to be connected. We proved that in a connected graph, there exists a simple path between any two vertices. We defined vertex cuts and edge cuts, and we stated the inequality relating minimum numbers of vertices and edges required to disconnect a graph. We defined matrix multiplication. Notes from 8/30/24 |
Video from 8/30/24 | |
|
9/4/2024: We showed how to count the number of paths and circuits of certain lengths on a graph using the adjacency matrix. Notes from 9/4/24 |
Video from 9/4/24 | |
|
9/6/2024: We discussed Eulerian circuits and paths and proved a theorem on how to determine if Eulerian paths or circuits exist on a given multigraph. Notes from 9/6/24 |
Video from 9/6/24 | |
|
9/9/2024: We examined Hamiltonian circuits and paths in graphs and stated Dirac's Graph theorem. We then looked at questions about finding shortest paths in weighted graphs and the traveling salesman problem. We then began discussing planar graphs. Notes from 9/9/24 (corrected 9/13/24) |
Video from 9/9/24 | |
|
9/11/2024: Discussed graphs on the plane and sphere. We defined the stereographic projection. We showed how $K_5$ can be embedded in the torus. Notes from 9/11/24 |
Video from 9/11/24 | |
|
9/13/2024: Discussed questions about calculating cut vertex and edge invariants and looked at planar graphs and the Euler characteristic. Notes from 9/13/24 |
Video from 9/13/24 | |
|
9/18/2024: We showed the the Euler characteristic of a graph on a surface does not
change with subdivision and does not depend on the choice of graph with faces on the surface. We stated Kuratowski's theorem on planar graphs. Notes from 9/18/24 |
Video from 9/18/24 | |
|
9/20/2024: We discussed chromatic numbers of graphs, trees, and rooted trees. Notes from 9/20/24 |
Video from 9/20/24 | |
|
9/23/2024: We worked examples of finding chromatic numbers, and we proved theorems about trees, discussing induction. Notes from 9/23/24 |
Video from 9/23/24 | |
|
9/25/2024: We discussed facts abouts rooted m-ary trees, their numbers of edges and leaves and heights. Notes from 9/25/24 |
Video from 9/25/24 | |
|
9/27/2024: We discussed binary searches and tree traversal algorithms. Notes from 9/27/24 |
Video from 9/27/24 | |
|
9/30/2024: We discussed depth-first and breadth-first algorithms for finding spanning trees of connected graphs. We also learned Prim's algorithm and Kruskal's algorithm for finding minimal spanning trees in connected, weighted graphs. Notes from 9/30/24 |
Video from 9/30/24 | |
|
10/2/2024: We stated the product rule for counting and used induction to prove the generalized product rule. We also defined permutations, stated the sum rule, and we used the rules in computing examples. Notes from 10/2/24 |
Video from 10/2/24 | |
|
10/3/2024: We solved several counting problems, and we introduced and used the Principle of Inclusion-Exclusion and the Pigeonhole Principle. Notes from 10/3/24 |
Video from 10/3/24 | |
|
10/7/2024: We solved some counting questions, and we asked some new ones. We reviewed Prim's Algorithm and Kruskal's Algorithm. Notes from 10/7/24 |
Video from 10/7/24 | |
|
10/14/2024: We counted permutations and combinations. Notes from 10/14/24 |
Video from 10/14/24 | |
|
10/16/2024: We showed how to count stars and bars. We also showed the binomial
theorem. Notes from 10/16/24 |
Video from 10/16/24 | |
|
10/18/2024: We discussed the binomial theorem and the Pascal identity. Notes from 10/18/24 |
Video from 10/18/24 | |
|
10/21/2024: We discussed more counting techniques with binomial coefficients, such as
the van der Monde identity. Notes from 10/21/24 Sagemath code used |
Video from 10/21/24 | |
|
10/23/2024: We did more examples of counting. Notes from 10/23/24 |
Video from 10/23/24 | |
|
10/25/2024: We solved a few counting questions with stars and bars, and we began talking
about recursion relations. Notes from 10/25/24 |
Video from 10/25/24 | |
|
10/28/2024: We discussed examples of recursion relations, the Tower of Hanoi, and deriving
closed form formulas from recurrence relations. Notes from 10/28/24 |
Video from 10/28/24 | |
|
10/30/2024: We looked at more examples of recursive formulas used to calculate/count quantities. Fixed Notes from 10/30/24 |
Truncated Video from 10/30/24 | |
|
11/1/2024: We derived the characteristic equation for solving linear homogeneous recurrence relations, and we
used it to calculate a closed-form formula for the nth Fibonacci number. Fixed Notes from 11/1/24 |
Video from 11/1/24 | |
|
11/4/2024: We solved some linear homogeneous recursion formulas, and related them to linear homogeneous
differential equations. Notes from 11/4/24 |
Video from 11/4/24 | |
|
11/6/2024: We solved linear homogeneous recursion formulas with multiple roots, and inhomogeneous recursions. We also derived Euler's formula for $e^{i\theta}$. Notes from 11/6/24 |
Video from 11/6/24 | |
|
11/8/2024: Review problems for Test #3. Notes from 11/8/24 |
Video from 11/8/24 | |
|
11/13/2024: We worked a complicated example of solving an inhomogeneous linear recursion. We also introduced the generalized inclusion-exclusion principle. Notes from 11/13/24 |
Video from 11/13/24 | |
|
11/15/2024: More work on inhomogeneous linear recursions, and using sagemath to check the work. We also did an example of the generalized inclusion-exclusion formula. Notes from 11/15/24 |
Video from 11/15/24 | |
|
11/18/2024: We discussed relations, equivalence relations, operations on relations. Notes from 11/18/24 |
Video from 11/18/24 | |
|
11/20/2024: We discussed examples of compositions of relations and equivalence relations. Notes from 11/20/24 |
Video from 11/20/24 | |
|
11/22/2024: We discussed equivalence relations as partitions of a set. We looked at the example of modular arithmetic. We also discussed graphical and matrix representations of relations in general. Notes from 11/22/24 Examples of correct proofs in Nov 22 homework: Homework Solution 1 Homework Solution 2 |
Video from 11/22/24 | |
|
12/2/2024: We discussed graphs associated to equivalence relations, an application of equivalence relations to image processing, and modular arithmetic. Notes from 12/2/24 |
Video from 12/2/24 | |
|
12/4/2024: We discussed the RSA algorithm for encryption and reviewed solving inhomogeneous recursions. Notes from 12/4/24 |
Video from 12/4/24 | |