When you enroll in this course, you'll also be enrolled in this Specialization.
Learn new concepts from industry experts
Gain a foundational understanding of a subject or tool
Develop job-relevant skills with hands-on projects
Earn a shareable career certificate
There are 6 modules in this course
Counting is one of the basic mathematically related tasks we encounter on a day to day basis. The main question here is the following. If we need to count something, can we do anything better than just counting all objects one by one? Do we need to create a list of all phone numbers to ensure that there are enough phone numbers for everyone? Is there a way to tell that our algorithm will run in a reasonable time before implementing and actually running it? All these questions are addressed by a mathematical field called Combinatorics.
In this online course we discuss most standard combinatorial settings that can help to answer questions of this type. We will especially concentrate on developing the ability to distinguish these settings in real life and algorithmic problems. This will help the learner to actually implement new knowledge. Apart from that we will discuss recursive technique for counting that is important for algorithmic implementations.
One of the main ‘consumers’ of Combinatorics is Probability Theory. This area is connected with numerous sides of life, on one hand being an important concept in everyday life and on the other hand being an indispensable tool in such modern and important fields as Statistics and Machine Learning. In this course we will concentrate on providing the working knowledge of basics of probability and a good intuition in this area. The practice shows that such an intuition is not easy to develop.
In the end of the course we will create a program that successfully plays a tricky and very counterintuitive dice game.
As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.
Counting is one of the basic mathematically related tasks we encounter on a day to day basis. The main question here is the following: can we count the number of objects without listing all of them? This question arises naturally in various scenarios both in real life and in Computer Science. What is the number of different phone numbers or license plates? What is the number of different combinations one needs to brute force in order to crack a password? Is there a way to tell that an algorithm will run in a reasonable time before implementing and actually running it? All these questions are addressed by a mathematical field called combinatorics. In this module, we consider the basic building blocks of combinatorics. All of them are easy to understand and at the same time are powerful enough to handle various non-trivial questions. To help you to develop an intuition, we consider short Python code snippets for generating the objects to be counted.
What's included
13 readings11 assignments
Show info about module content
13 readings•Total 143 minutes
Companion e-book•3 minutes
Why Counting•10 minutes
Rule of Sum•10 minutes
How Not to Use the Rule of Sum•10 minutes
Convenient Language: Sets•20 minutes
Generalized Rule of Sum•10 minutes
Number of Paths•20 minutes
Rule of Product•10 minutes
Back to Recursive Counting•10 minutes
Number of Tuples•10 minutes
Licence Plates•10 minutes
Tuples with Restrictions•10 minutes
Permutations•10 minutes
11 assignments•Total 150 minutes
Numbers Divisible by 2 or 3•8 minutes
Puzzle: Number of Paths•30 minutes
Number of passwords•30 minutes
Rule of Sum in Programming•4 minutes
Operations with Sets•10 minutes
Generalized Rule of Sum•18 minutes
Rule of Product in Programming•10 minutes
Applications of the Rule of Product•12 minutes
Tuples•5 minutes
License Plates•3 minutes
Counting with Restrictions•20 minutes
Binomial Coefficients
Module 2•4 hours to complete
Module details
In how many ways one can select a team of five students out of ten students? What is the number of non-negative integers with at most five digits whose digits are decreasing? In how many ways one can get from the bottom left cell to the top right cell of a 5x5 grid, each time going either up or to the right? And why all these three numbers are equal? We'll figure this out in this module!
What's included
8 videos4 readings6 assignments
Show info about module content
8 videos•Total 76 minutes
Previously on Combinatorics•6 minutes
Number of Games in a Tournament•11 minutes
Combinations•9 minutes
Pascal's Triangle•10 minutes
Symmetries•4 minutes
Row Sums•11 minutes
Binomial Theorem•13 minutes
Practice Counting•13 minutes
4 readings•Total 40 minutes
Generating Combinatorial Objects: Code•10 minutes
Slides•10 minutes
Slides•10 minutes
Slides•10 minutes
6 assignments•Total 119 minutes
Number of Iterations of Nested For Loops•4 minutes
Number of Segments and Diagonals•20 minutes
Forming Sport Teams•15 minutes
Sum of the First Six Rows of Pascal's Triangle•30 minutes
Expanding (3a-2b)^k•20 minutes
Practice Counting•30 minutes
Advanced Counting
Module 3•3 hours to complete
Module details
We have already considered most of the standard settings in Combinatorics that allow us to address many counting problems. However, successful application of this knowledge on practice requires considerable experience in this kind of problems. In this module, we will address the final standard setting in our course, combinations with repetitions, and then we will gain some experience by discussing various problems in Combinatorics.
What's included
7 readings8 assignments
Show info about module content
7 readings•Total 70 minutes
Review•10 minutes
Salads•10 minutes
Combinations with Repetitions•10 minutes
Distributing Assignments•10 minutes
Distributing Candies Among Kids•10 minutes
Counting Credit Card PINs•10 minutes
Splitting into Working Groups•10 minutes
8 assignments•Total 122 minutes
Distributing Assignments Among People•10 minutes
Distributing Candies Among Kids•15 minutes
Numbers with Fixed Sum of Digits•15 minutes
Numbers with Non-increasing Digits•7 minutes
Splitting into Working Groups•10 minutes
Salads•10 minutes
Combinations with Repetitions•10 minutes
Problems in Combinatorics•45 minutes
Probability
Module 4•5 hours to complete
Module details
The word "probability" is used quite often in the everyday life. However, not always we can speak about probability as some number: for that a mathematical model is needed. What is this mathematical model (probability space)? How to compute probabilities (if the model is given)? How to judge whether the model is adequate? What is conditional probability and Bayes' theorem? How our plausible reasoning can be interpreted in terms of Bayes' theorem? In this module we cover these questions using some simple examples of probability spaces and real life sutiations.
What's included
17 videos4 readings11 assignments
Show info about module content
17 videos•Total 126 minutes
The Paradox of Probability Theory•4 minutes
Galton Board•6 minutes
Natural Sciences and Mathematics•6 minutes
Rolling Dice•8 minutes
More Probability Spaces•10 minutes
Not Equiprobable Outcomes•5 minutes
More About Finite Spaces•6 minutes
Mathematics for Prisoners•8 minutes
Not All Questions Make Sense•10 minutes
What Is Conditional Probability?•7 minutes
How Reliable Is The Test?•8 minutes
Bayes' Theorem•9 minutes
Conditional Probability: A Paradox•7 minutes
Past and Future•8 minutes
Independence•8 minutes
Monty Hall Paradox•8 minutes
`Our Position'•6 minutes
4 readings
Slides•0 minutes
Slides•0 minutes
Slides•0 minutes
Slides•0 minutes
11 assignments•Total 168 minutes
Concentration for Galton Board•10 minutes
Computing Probabilities for Two Dice•12 minutes
Computing Probabilities: More Examples•12 minutes
Fair Decisions and Imperfect Coins•20 minutes
Puzzle: Prisoner and King•30 minutes
Inclusion-Exclusion Formula•10 minutes
Computing Conditional Probabilities•16 minutes
Prisoner, King and Conditional Probabilities•10 minutes
More Conditional Probabilities•8 minutes
More About Independence•20 minutes
Monty Hall Gone Crazy•20 minutes
Random Variables
Module 5•4 hours to complete
Module details
In the previous module we discussed how to compute probabilities of random events. But in many practical situation we are interested not only in positive or negative outcome, but also in some quantitative characteristics of an outcome. Among these cases are number of steps of an algorithms, number of points that one can win in the games involving any kind of randomness, all quantitative characteristics of a random person in some group of people. Basically settings of this kind arise in all situations when (a) any kind of uncertainty is presented (b) we are interested in quantitative characteristics. The mathematical model for this is called random variables. And we will discuss them in this module.
What's included
8 readings10 assignments1 ungraded lab
Show info about module content
8 readings•Total 80 minutes
Random Variables•10 minutes
Average•10 minutes
Expectation•10 minutes
Linearity of Expectation•10 minutes
Birthday Problem•10 minutes
Expectation is Not All•10 minutes
From Expectation to Probability•10 minutes
Markov’s Inequality•10 minutes
10 assignments•Total 91 minutes
Birthday Problem•10 minutes
Random Variables•8 minutes
Average•15 minutes
Expectations•10 minutes
Linearity of Expectation•15 minutes
Bob’s Party•5 minutes
More Linearity•10 minutes
Average Income•8 minutes
Bob’s Party Revisited•5 minutes
Alice’s tests•5 minutes
1 ungraded lab•Total 60 minutes
Birthday Problem Simulation•60 minutes
Project: Dice Games
Module 6•2 hours to complete
Module details
In this module, we will apply accumulated knowledge to create a project solving a certain dice game. The game is very simple: two players pick a dice each from a given pool of dices with various numbers on their sides. Then each player throws his dice and the one with the greater number on his dice wins. The game looks very simple and it seems that it is very easy to play this game optimally once we know our pool of dices. Yet it turns out that this intuition is overwhelmingly wrong: the game turns out to be very counterintuitive. In this module we will discuss the game in detail and create a program that finds an optimal strategy to play the game on a given pool of dices.
What's included
2 readings1 assignment
Show info about module content
2 readings•Total 20 minutes
Dice Game Problem•10 minutes
Optimal Strategy•10 minutes
1 assignment•Total 120 minutes
Final Project: Dice Game•120 minutes
Earn a career certificate
Add this credential to your LinkedIn profile, resume, or CV. Share it on social media and in your performance review.
Instructors
Instructor ratings
Instructor ratings
We asked all learners to give feedback on our instructors based on the quality of their teaching style.
UC San Diego is an academic powerhouse and economic engine, recognized as one of the top 10 public universities by U.S. News and World Report. Innovation is central to who we are and what we do. Here, students learn that knowledge isn't just acquired in the classroom—life is their laboratory.
OK
Explore more from Algorithms
RecommendedSpecializationsRelated
T
The Hong Kong University of Science and Technology
"To be able to take courses at my own pace and rhythm has been an amazing experience. I can learn whenever it fits my schedule and mood."
Jennifer J.
Learner since 2020
"I directly applied the concepts and skills I learned from my courses to an exciting new project at work."
Larry W.
Learner since 2021
"When I need courses on topics that my university doesn't offer, Coursera is one of the best places to go."
Chaitanya A.
"Learning isn't just about being better at your job: it's so much more than that. Coursera allows me to learn without limits."
Learner reviews
4.6
870 reviews
5 stars
69.95%
4 stars
20.06%
3 stars
6.88%
2 stars
1.26%
1 star
1.83%
Showing 3 of 870
F
FF
4·
Reviewed on Jul 31, 2020
Great course. The final Project unclear had instructions on how to provide input. I spent a lot of time trying to troubleshoot it even though I already have a correct solution
J
JC
5·
Reviewed on Sep 8, 2020
It's a perfect introduction to combinatorics and probability, short, fun, and easy to understand. I would like to see more puzzles, those are extremely fun and interesting
D
DC
5·
Reviewed on Jan 22, 2021
It was pretty interesting. Although, the requirement to know the python programming in the last course task was really unexpected to me.
When will I have access to the lectures and assignments?
To access the course materials, assignments and to earn a Certificate, you will need to purchase the Certificate experience when you enroll in a course. You can try a Free Trial instead, or apply for Financial Aid. The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
What will I get if I subscribe to this Specialization?
When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile.
Is financial aid available?
Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.