课程信息
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.
Globe

100% 在线课程

立即开始,按照自己的计划学习。
Intermediate Level

中级

Clock

完成时间大约为46 小时

建议:11 weeks of study, 3-5 hours per week.
Comment Dots

English

字幕:English
Globe

100% 在线课程

立即开始,按照自己的计划学习。
Intermediate Level

中级

Clock

完成时间大约为46 小时

建议:11 weeks of study, 3-5 hours per week.
Comment Dots

English

字幕:English

Syllabus - What you will learn from this course

1

Section
Clock
5 hours to complete

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....
Reading
2 videos (Total 27 min), 3 quizzes
Video2 videos
Sets, Relations, Functions10m
Quiz1 practice exercises
Sets, relations, and functions30m

2

Section
Clock
4 hours to complete

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....
Reading
2 videos (Total 28 min), 2 quizzes
Video2 videos
Mirsky's and Dilworth's Theorem14m
Quiz1 practice exercises
Partial orders, maximal and minimal elements, chains, antichains0m

3

Section
Clock
5 hours to complete

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....
Reading
3 videos (Total 35 min), 2 quizzes
Video3 videos
Evaluating Simple Sums8m
Pascal's Triangle14m
Quiz1 practice exercises
Counting Basic Objects0m

4

Section
Clock
4 hours to complete

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....
Reading
3 videos (Total 55 min), 3 quizzes
Video3 videos
Estimating the Binomial Coefficient22m
Excursion to Discrete Probability: Computing the Expected Minimum of k Random Elements from {1,...,n}18m
Quiz1 practice exercises
An Eagle's View of Pascal's Triangle8m

5

Section
Clock
5 hours to complete

Asymptotics and the O-Notation

...
Reading
1 video (Total 14 min), 3 quizzes
Quiz1 practice exercises
The Big-O-Notation18m

6

Section
Clock
5 hours to complete

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....
Reading
3 videos (Total 41 min), 3 quizzes
Video3 videos
Graph Isomorphism, Degree, Graph Score13m
Graph Score Theorem16m
Quiz1 practice exercises
Graphs, isomorphisms, and the sliding tile puzzle30m

7

Section
Clock
5 hours to complete

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....
Reading
3 videos (Total 36 min), 3 quizzes
Video3 videos
Cycles and Trees15m
An Efficient Algorithm for Isomorphism of Trees12m
Quiz1 practice exercises
Cycles and Trees30m

8

Section
Clock
3 hours to complete

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....
Reading
2 videos (Total 27 min), 2 quizzes
Video2 videos
Hamilton Cycles - Ore's and Dirac's Theorem16m
Quiz1 practice exercises
Hamiltonian Cycles and Paths0m

9

Section
Clock
5 hours to complete

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....
Reading
2 videos (Total 29 min), 3 quizzes
Video2 videos
The Number of Trees on n Vertices15m
Quiz1 practice exercises
Spanning Trees40m

10

Section
Clock
3 hours to complete

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....
Reading
2 videos (Total 29 min), 2 quizzes
Video2 videos
Flow Networks: The Maxflow - Mincut Theorem15m
Quiz1 practice exercises
Network flow8m

11

Section
Clock
3 hours to complete

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....
Reading
3 videos (Total 46 min), 1 quiz
Video3 videos
Matchings in Bipartite Graphs: Hall's and König's Theorem16m
Partial Orders: Dilworth's Theorem on Chains and Antichains15m
3.7

Top Reviews

By JCAug 20th 2017

Very interesting and motivating.\n\nRather standard English that is easily to be understood for non-English students.

By NPOct 23rd 2017

Fantastic course. Fascinating material, presented at a reasonably fast pace, and some really challenging assignments.

Instructor

Avatar

Dominik Scheder

Assistant Professor

About 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....

Frequently Asked Questions

  • Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.

  • If you pay for this course, you will have access to all of the features and content you need to earn a Course Certificate. If you complete the course successfully, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. Note that the Course Certificate does not represent official academic credit from the partner institution offering the course.

  • Yes! Coursera provides financial aid to learners who would like to complete a course but cannot afford the course fee. To apply for aid, select "Learn more and apply" in the Financial Aid section below the "Enroll" button. You'll be prompted to complete a simple application; no other paperwork is required.

More questions? Visit the Learner Help Center