Discrete Mathematics from Coursera

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.

What's inside

Syllabus

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.

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.

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.

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.

Asymptotics and the O-Notation

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.

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.

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.

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.

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.

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.

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

Explores discrete mathematics, a fundamental cornerstone of computer science, with an emphasis on mathematical maturity

Develops a level of mathematical maturity, enabling learners to understand formal statements and proofs, create rigorous proofs of their own, and unearth fresh insights

Taught by instructors with expertise in discrete mathematics, ensuring learners are instructed by experienced professionals in the field

Covers core topics in discrete mathematics, including sets, functions, relations, graphs, enumerative combinatorics, graph theory, network flows, and matchings

Presents a balanced approach between rigor and accessibility, introducing complex concepts with real-world examples and visuals

Designed for learners with backgrounds in mathematics, preferably with some exposure to abstract mathematics

Reviews summary

Mixed discrete math course

Students say Discrete Mathematics is an interesting and challenging course. According to learners, exercises, assignments, and quizzes are difficult, especially for those lacking background knowledge. Some observe that proof-writing is not well established, and that there are significant gaps between lectures and assessments. Overall, however, students say it's an engaging experience with plenty of knowledge to offer.

Students enjoy the learning process.

"interesting"

"engaging"

"You spent more than 10 hrs per week to solve them"

May not be best for learning proof-writing.

"proof-writing hasn't even been established as a concept"

"I do not understand the notation used in the sets"

Material is challenging, especially for beginners.

"very difficult"

"difficult"

"some background knowledge of mathematics"

Assumes knowledge that may not be clear.

"This course assumes certain knowledge about mathematical notation that is not taught or stipulated one must have."

"set theory in perhaps 16 years"

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in Discrete Mathematics with these activities:

Review basic concepts of set theory

Show steps

Ensure a solid foundation in set theory, essential for understanding discrete mathematics.

Browse courses on Set Theory

Show steps

Revisit notes or textbooks on set theory.
Solve practice problems to reinforce core concepts.

Practice with sample enumerative combinatorics problems

Show steps

Enhance your understanding of enumerative combinatorics concepts and problem-solving techniques.

Show steps

Find practice problems on reputable websites or textbooks.
Attempt to solve the problems independently.
Review your solutions and identify areas for improvement.

Participate in online discussion forums related to discrete mathematics

Show steps

Engage with peers, share knowledge, and clarify concepts.

Show steps

Join online forums or discussion groups focused on discrete mathematics.
Actively participate in discussions, asking and answering questions.
Review the discussions and reflect on the insights gained.

Six other activities

Expand to see all activities and additional details

Show all nine activities

Explore tutorials on graph algorithms

Show steps

Gain a deeper understanding of graph algorithms and their applications.

Show steps

Identify specific graph algorithms you want to learn.
Find high-quality tutorials or online courses on those algorithms.
Work through the tutorials, implementing the algorithms yourself.

Walkthrough video tutorials on flow networks and matchings

Show steps

Gain visual and interactive understanding of these complex topics.

Show steps

Find reputable video tutorials on flow networks and matchings.
Watch the tutorials, taking notes and pausing to understand concepts.
Implement the concepts in simple coding exercises.

Solve challenging problems involving partial orders and lattices

Show steps

Test and deepen your understanding of partial orderings and lattice structures.

Show steps

Identify textbooks or online resources with advanced problems.
Attempt to solve the problems independently, focusing on constructing rigorous proofs.

Create a visual representation of a graph theory concept

Show steps

Enhance your grasp of graph theory by visualizing and explaining key concepts.

Show steps

Choose a graph theory concept to illustrate.
Decide on a visual representation (e.g., diagram, animation).
Create the visual representation and accompany it with clear explanations.

Attend a workshop on mathematical proof techniques

Show steps

Gain exposure to advanced proof techniques and enhance your mathematical maturity.

Show steps

Research and identify suitable workshops.
Attend the workshop, actively participating and taking notes.
Apply the techniques learned to solve challenging problems.

Volunteer as a tutor for students struggling with discrete mathematics concepts

Show steps

Reinforce your understanding by explaining concepts to others and providing guidance.

Show steps

Contact your instructor or a local tutoring center to offer your services.
Prepare lessons and materials to help students grasp complex topics.
Regularly meet with students, providing support and answering their questions.

Career center

Learners who complete Discrete Mathematics will develop knowledge and skills that may be useful to these careers:

Computer Scientist

Computer Scientists use their knowledge of discrete mathematics to develop new algorithms and data structures. This course teaches the mathematical foundations of computer science, which are essential for understanding how computers work. Additionally, the course's focus on proofs and rigor will develop your analytical skills, which are essential for success in computer science.

See salaries and explore the career path for Computer Scientist

Operations Research Analyst

Operations Research Analysts use their knowledge of discrete mathematics to solve problems in a variety of industries, including manufacturing, logistics, and healthcare. This course teaches the mathematical foundations of computer science, which are essential for understanding how to model and solve real-world problems. Additionally, the course's focus on proofs and rigor will develop your problem-solving skills, which are essential for success in operations research.

See salaries and explore the career path for Operations Research Analyst

Software Engineer

Software Engineers use their knowledge of discrete mathematics to design and develop software applications. This course teaches the mathematical foundations of computer science, which are essential for understanding how software works. Additionally, the course's focus on proofs and rigor will develop your problem-solving skills, which are essential for success in software engineering.

See salaries and explore the career path for Software Engineer

Statistician

Statisticians use their knowledge of discrete mathematics to collect, analyze, and interpret data. This course teaches the mathematical foundations of computer science, which are essential for understanding how to collect and analyze data. Additionally, the course's focus on proofs and rigor will develop your analytical skills, which are essential for success in statistics.

See salaries and explore the career path for Statistician

Data Analyst

Data Analysts use their knowledge of discrete mathematics to turn raw data into structured data, which can then be analyzed to extract insights. This course teaches the mathematical foundations of computer science, which are essential for working with data. Additionally, the course's focus on proofs and rigor will develop your critical thinking skills, which are essential for success in data analysis.

See salaries and explore the career path for Data Analyst

Financial Analyst

Financial Analysts use their knowledge of discrete mathematics to develop and analyze financial models. This course teaches the mathematical foundations of computer science, which are essential for understanding how to model and analyze financial data. Additionally, the course's focus on proofs and rigor will develop your analytical skills, which are essential for success in financial analysis.

See salaries and explore the career path for Financial Analyst

Product Manager

Product Managers use their knowledge of discrete mathematics to develop and manage products. This course teaches the mathematical foundations of computer science, which are essential for understanding how to develop and manage products. Additionally, the course's focus on proofs and rigor will develop your problem-solving skills, which are essential for success in product management.

See salaries and explore the career path for Product Manager

Quantitative Analyst

Quantitative Analysts use their knowledge of discrete mathematics to develop and analyze financial models. This course teaches the mathematical foundations of computer science, which are essential for understanding how to model and analyze financial data. Additionally, the course's focus on proofs and rigor will develop your analytical skills, which are essential for success in quantitative analysis.

See salaries and explore the career path for Quantitative Analyst

Actuary

Actuaries use their knowledge of discrete mathematics to assess and manage risk. This course teaches the mathematical foundations of computer science, which are essential for understanding how to model and assess risk. Additionally, the course's focus on proofs and rigor will develop your analytical skills, which are essential for success in actuarial science.

See salaries and explore the career path for Actuary

Risk Manager

Risk Managers use their knowledge of discrete mathematics to assess and manage risk. This course teaches the mathematical foundations of computer science, which are essential for understanding how to model and assess risk. Additionally, the course's focus on proofs and rigor will develop your analytical skills, which are essential for success in risk management.

See salaries and explore the career path for Risk Manager

Management Consultant

Management Consultants use their knowledge of discrete mathematics to analyze and solve business problems. This course teaches the mathematical foundations of computer science, which are essential for understanding how to model and solve business problems. Additionally, the course's focus on proofs and rigor will develop your analytical skills, which are essential for success in management consulting.

See salaries and explore the career path for Management Consultant

Data Scientist

Data Scientists use their knowledge of mathematics, including discrete mathematics, to turn raw data into structured data, which can then be analyzed to extract insights. This course teaches the mathematical foundations of computer science, which are essential for working with data. Additionally, the course's focus on proofs and rigor will develop your critical thinking skills, which are essential for success in data science.

See salaries and explore the career path for Data Scientist

Business Analyst

Business Analysts use their knowledge of discrete mathematics to analyze and solve business problems. This course teaches the mathematical foundations of computer science, which are essential for understanding how to model and solve business problems. Additionally, the course's focus on proofs and rigor will develop your analytical skills, which are essential for success in business analysis.

See salaries and explore the career path for Business Analyst

Technical Writer

Technical Writers use their knowledge of discrete mathematics to write clear and concise technical documentation. This course teaches the mathematical foundations of computer science, which are essential for understanding how to write technical documentation. Additionally, the course's focus on proofs and rigor will develop your communication skills, which are essential for success in technical writing.

See salaries and explore the career path for Technical Writer

User Experience Designer

User Experience Designers use their knowledge of discrete mathematics to design and evaluate user interfaces. This course teaches the mathematical foundations of computer science, which are essential for understanding how to design and evaluate user interfaces. Additionally, the course's focus on proofs and rigor will develop your problem-solving skills, which are essential for success in user experience design.

See salaries and explore the career path for User Experience Designer