Discrete Mathematics
link Source: www.coursera.org
list 11 sequences
assignment Level : Intermediate
chat_bubble_outline Language : English
card_giftcard 330 points
Logo My Mooc Business

Top companies choose Edflex to build in-demand career skills.

Get started
Users' reviews
2.3
starstarstarstarstar
6 reviews

Key Information

credit_card Free access
verified_user Fee-based Certificate
timer 33 hours in total

About the content

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.

more_horiz Read more
more_horiz Read less
dns

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 ...
  • 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 i...
  • 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 probabilit...
  • 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.
  • Week 5 - Asymptotics and the O-Notation
     
  • 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...
  • 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.
  • 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.
  • 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.
  • 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.
  • 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 surpr...
record_voice_over

Instructors

Dominik Scheder
Assistant Professor
The Department of Computer Science and Engineering

store

Content Designer

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

Platform

Coursera

Coursera is a digital company offering massive open online course founded by computer teachers Andrew Ng and Daphne Koller Stanford University, located in Mountain View, California. 

Coursera works with top universities and organizations to make some of their courses available online, and offers courses in many subjects, including: physics, engineering, humanities, medicine, biology, social sciences, mathematics, business, computer science, digital marketing, data science, and other subjects.

Reviews
2.3 /5 Average
starstarstarstarstar
1
starstarstarstarstar
1
starstarstarstarstar
0
starstarstarstarstar
1
starstarstarstarstar
3
Content
2.3/5
Platform
2.3/5
Animation
2.3/5
Best Review

The level is advanced undergraduate. It contains challenging excersises. You spent more than 10hr per week to solve them and typesetting them(at least for me).And you can make friend with your peers. It is for me a unique experience!

Anonymous
Published on October 19, 2017
You are the designer of this MOOC?
What is your opinion on this resource ?
Content
5/5
Platform
5/5
Animation
5/5
December 16, 2017
starstarstarstarstar

Actually I haven't finished course in the eleventh week yet, I've only done all the tests:). However, I'd like to say that I like this course very much, it's inspiring and difficult enough. Though I always have to struggle a lot to find the cocepts and meaning of the notations online, there have been enough hints. The only pity was that sometimes there's something which can't be shown normally in exercise, this has caused me some trouble. Overall it's great, and thanks a lot, professor Scheder.

October 19, 2017
starstarstarstarstar

The level is advanced undergraduate. It contains challenging excersises. You spent more than 10hr per week to solve them and typesetting them(at least for me).And you can make friend with your peers. It is for me a unique experience!

September 28, 2017
starstarstarstarstar

Poor presentation of material. Peer reviewed material with no solutions given and no explanation or solutions to any problems. The instructor is teaching this as a review course instead of for people who are taking this for their first time. You cannot learn in this course. Very poor. Remove this course its a waste of time.

June 5, 2017
starstarstarstarstar

Other than the issue of peer grading, I took the course of the first week and found the course material is missing and quiz of week 1 needs the materials of week 2.This is not a preliminary discrete math course. I was trying to learn part of the MIT discrete math course then jump on this course to catch up but I found that the first week's content is about 15 week content in MIT so I guess I will just quit.In the forum there are people seems can't find enough companies for peer grading and almost no posts after week 2.

April 27, 2017
starstarstarstarstar

Course materials are poorly prepared and the method of peer review of proofs in fundamentally flawed. Hopefully, once there are some teaching and explanatory materials available and an improved scheme for assignment marking, the course will be worth taking. Unfortunately it is a bit of a mess at the moment.