Discrete Mathematics

About this course: Discrete mathematics forms the mathematical foundation of computer and information science. It is also a fascinating subject in itself. Learners will become familiar with a broad range of mathematical objects like sets, functions, relations, graphs, that are omnipresent in computer science. Perhaps more importantly, they will reach a certain level of mathematical maturity - being able to understand formal statements and their proofs; coming up with rigorous proofs themselves; and coming up with interesting results. This course attempts to be rigorous without being overly formal. This means, for every concept we introduce we will show at least one interesting and non-trivial result and give a full proof. However, we will do so without too much formal notation, employing examples and figures whenever possible. The main topics of this course are (1) sets, functions, relations, (2) enumerative combinatorics, (3) graph theory, (4) network flow and matchings. It does not cover modular arithmetic, algebra, and logic, since these topics have a slightly different flavor and because there are already several courses on Coursera specifically on these topics.

Who is this class for: The main target audience of this course is undergraduate students from Computer Science, Mathematics, and other related subjects. It is also suited for people with an interest in maths but without much prior formal education therein.

Created by:  Shanghai Jiao Tong University

• Taught by:  Dominik Scheder, Assistant Professor

  The Department of Computer Science and Engineering

Level Intermediate Commitment 11 weeks of study, 3-5 hours per week. Language English How To Pass Pass all graded assignments to complete the course. User Ratings 3.6 stars Average User Rating 3.6See what learners said Coursework

Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.

Help from your peers

Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.

Certificates

Earn official recognition for your work, and share your success with friends, colleagues, and employers.

Shanghai Jiao Tong University Shanghai Jiao Tong University, a leading research university located in Shanghai, China, has been regarded as the fastest developing university in the country for the last decade. With special strengths in engineering, science, medicine and business, it now offers a comprehensive range of disciplines in 27 schools with more than 41,000 enrolled students from more than one hundred countries.

Syllabus


WEEK 1


Introduction - Basic Objects in Discrete Mathematics



This module gives the learner a first impression of what discrete mathematics is about, and in which ways its "flavor" differs from other fields of mathematics. It introduces basic objects like sets, relations, functions, which form the foundation of discrete mathematics.


2 videos expand

1. Video: Introduction to the course
2. Video: Sets, Relations, Functions

Graded: Exercises for introduction lesson
Graded: Sets, Relations, Functions
Graded: Sets, relations, and functions

WEEK 2


Partial Orders



Even without knowing, the learner has seen some orderings in the past. Numbers are ordered by <=. Integers can be partially ordered by the "divisible by" relation. In genealogy, people are ordered by the "A is an ancestor of B" relation. This module formally introduces partial orders and proves some fundamental and non-trivial facts about them.


2 videos expand

1. Video: Partial orderings: basic notions
2. Video: Mirsky's and Dilworth's Theorem

Graded: Partial orders, maximal and minimal elements, chains, antichains
Graded: Partial orders, maximal and minimal elements, chains, antichains

WEEK 3


Enumerative Combinatorics



A big part of discrete mathematics is about counting things. A classic example asks how many different words can be obtained by re-ordering the letters in the word Mississippi. Counting problems of this flavor abound in discrete mathematics discrete probability and also in the analysis of algorithms.


3 videos expand

1. Video: How to Count Functions, Injections, Permutations, and Subsets
2. Video: Evaluating Simple Sums
3. Video: Pascal's Triangle

Graded: Counting Basic Objects
Graded: Counting Basic Objects

WEEK 4


The Binomial Coefficient
The binomial coefficient (n choose k) counts the number of ways to select k elements from a set of size n. It appears all the time in enumerative combinatorics. A good understanding of (n choose k) is also extremely helpful for analysis of algorithms.


3 videos expand

1. Video: Combinatorial Identities
2. Video: Estimating the Binomial Coefficient
3. Video: Excursion to Discrete Probability: Computing the Expected Minimum of k Random Elements from {1,...,n}

Graded: Combinatorial Identities
Graded: Digging Into Pascal's Triangle

WEEK 5


Asymptotics and the O-Notation



1 video, 1 practice quiz expand

1. Video: Asymptotics and the O( )-Notation
2. Practice Quiz: The Big-O-Notation

Graded: Basic Facts
Graded: Classes that often occur in complexity theory

WEEK 6


Introduction to Graph Theory



Graphs are arguably the most important object in discrete mathematics. A huge number of problems from computer science and combinatorics can be modelled in the language of graphs. This module introduces the basic notions of graph theory - graphs, cycles, paths, degree, isomorphism.


3 videos expand

1. Video: Basic Notions and Examples
2. Video: Graph Isomorphism, Degree, Graph Score
3. Video: Graph Score Theorem

Graded: Graphs and Isomorphisms
Graded: Graphs, isomorphisms, and the sliding tile puzzle
Graded: The Graph Score Theorem

WEEK 7


Connectivity, Trees, Cycles
We continue with graph theory basics. In this module, we introduce trees, an important class of graphs, and several equivalent characterizations of trees. Finally, we present an efficient algorithm for detecting whether two trees are isomorphic.


3 videos expand

1. Video: Graphs and Connectivity
2. Video: Cycles and Trees
3. Video: An Efficient Algorithm for Isomorphism of Trees

Graded: Cycles and Trees
Graded: Cycles and Trees
Graded: Spanning Tree Exchange Graph

WEEK 8


Eulerian and Hamiltonian Cycles
Starting with the well-known "Bridges of Königsberg" riddle, we prove the well-known characterization of Eulerian graphs. We discuss Hamiltonian paths and give sufficient criteria for their existence with Dirac's and Ore's theorem.


2 videos expand

1. Video: Eulerian Cycles
2. Video: Hamilton Cycles - Ore's and Dirac's Theorem

Graded: Hamiltonian Cycles and Paths
Graded: Hamiltonian Cycles and Paths

WEEK 9


Spanning Trees
We discuss spanning trees of graphs. In particular we present Kruskal's algorithm for finding the minimum spanning tree of a graph with edge costs. We prove Cayley's formula, stating that the complete graph on n vertices has n^(n-2) spanning trees.


2 videos expand

1. Video: Minimum Spanning Trees
2. Video: The Number of Trees on n Vertices

Graded: Minimum Spanning Trees
Graded: Minimum Spanning Trees
Graded: Counting Trees on n Vertices

WEEK 10


Maximum flow and minimum cut
This module is about flow networks and has a distinctively algorithmic flavor. We prove the maximum flow minimum cut duality theorem.


2 videos expand

1. Video: Flow Networks, Flows, Cuts: Basic Notions and Examples
2. Video: Flow Networks: The Maxflow - Mincut Theorem

Graded: Network Flows

WEEK 11


Matchings in Bipartite Graphs



We prove Hall's Theorem and Kőnig's Theorem, two important results on matchings in bipartite graphs. With the machinery from flow networks, both have quite direct proofs. Finally, partial orderings have their comeback with Dilworth's Theorem, which has a surprising proof using Kőnig's Theorem.


3 videos expand

1. Video: Matchings in Bipartite Graphs - Basic Notions and an Algorithm
2. Video: Matchings in Bipartite Graphs: Hall's and König's Theorem
3. Video: Partial Orders: Dilworth's Theorem on Chains and Antichains

Graded: Matchings in Bipartite Graphs