Discrete Mathematics 3
A total of more than 53 hours of lectures
This is the third part of our series of three courses in Discrete Mathematics. It covers number sequences, solving linear recurrences, generating functions, an introduction to graph theory, and some chosen applications of discrete mathematics.Â
Prerequisites
Curriculum
Make sure that you check with your professor what parts of the course you will need for your exam. Such things vary from country to country, from university to university, and they can even vary from year to year at the same university.
Discrete Mathematics 3
Get the outline
A detailed list of all the lectures in part 3 of the course, including which theorems will be discussed and which problems will be solved. If you are looking for a particular kind of problem or a particular concept, this is where you should look first.
Get Discrete Mathematics 3 on Udemy
When you buy the course on Udemy, you get access to it for life. There is just a one-time fee. The prices do vary a lot on Udemy, but if you use our link by clicking on this panel, you will get the best current price. See also our page on “coupon codes” in the menu (the current code is TPOT_AUG26).
Course Objectives & Outcomes
Mathematical modelling and finding recursive formulas.
Arithmetic progressions and arithmetic sums.
Monotone sequences with some examples (arithmetic and geometric progressions and their monotonicity).
Polynomial sequences and their sequences of differences; a complete characterisation of such sequences and a method of finding their closed formula (Ansatz).
An elementary introduction to some basic concepts in Graph Theory: isomorphic graphs, subgraphs, induced subgraphs, degree of a vertex, adjacency, cycles.
Trees and their basic properties.
Euler trails and circuits, Hamilton paths and cycles.
Chromatic number (defined by proper vertex coloring with minimal number of colors) of certain graphs.
Relations and graphs (covered in DM1).
Some applications of DM: Chinese Remainder Theorem, cryptography, quick arithmetic.
Some advice for further studies of DM.
The concept of number sequences: how we can define them (in various way: explicitly, recursively, verbally, …) and depict them (as functions from N to R).
Famous sequences (Fibonacci sequence, triangular numbers, tetrahedral numbers, perfect squares, powers of two) and their place in Pascal’s Triangle.
Sequences of differences and sequences of partial sums.
Geometric progressions and geometric sums.
Periodic sequences with some examples (all of them based on elementary Number Theory and modulus).
Solving linear recursion with help of characteristic polynomials: the case of real zeros of various multiplicities; homogenous and non-homogenous.
Some identities involving the Fibonacci numbers.
Special graphs: trees, complete graphs K_n, paths P_n, cycles C_n, bipartite graphs, complete bipartite graphs K_(m,n), the Tutte Graph, the Petersen Graph.
Planar graphs: Euler’s Formula.
An introduction to graph coloring; monochromatic triangles.
Chromatic index (defined by proper edge coloring with minimal number of colors) of certain graphs.
A word about matching in bipartite graphs.
Sequences in algorithms: polynomial and exponential sequences as studied in Sec. 6&7.