This course is part of the Introduction to Discrete Mathematics for Computer Science Specialization

Offered By

University of California San Diego

National Research University Higher School of Economics

Introduction to Discrete Mathematics for Computer Science Specialization

University of California San Diego

About this Course

4.6

168 ratings

•

36 reviews

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

Start instantly and learn at your own schedule.

Reset deadlines in accordance to your schedule.

Suggested: 6 weeks, 3-5 hours/week ...

Subtitles: English

Random VariableProbability InterpretationsProbabilityCombinatorics

Start instantly and learn at your own schedule.

Reset deadlines in accordance to your schedule.

Suggested: 6 weeks, 3-5 hours/week ...

Subtitles: English

Week

1Suppose we need to count certain objects. Can we do anything better than just list all the objects? Do we need to create a list all phone numbers to check whether there are enough phone numbers for everyone? Is there a way to tell whether 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 module we will give an introduction to this field that will help us to answer basic versions of the above questions....

12 videos (Total 54 min), 4 readings, 9 quizzes

Rule of Sum3m

How Not to Use the Rule of Sum3m

Convenient Language: Sets4m

Generalized Rule of Sum3m

Number of Paths4m

Rule of Product3m

Back to Recursive Counting3m

Number of Tuples5m

Licence Plates3m

Tuples with Restrictions5m

Permutations9m

Slides1m

Slides1m

Listing All Permutations5m

Slides1m

Rule of Sum in Programming4m

Numbers Divisible by 2 or 38m

Operations with Sets10m

Generalized Rule of Sum18m

Rule of Product in Programming10m

Applications of the Rule of Product12m

Tuples5m

Counting with Restrictions20m

Week

2In 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 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!...

8 videos (Total 76 min), 4 readings, 6 quizzes

Number of Games in a Tournament10m

Combinations8m

Pascal's Triangle9m

Symmetries4m

Row Sums10m

Binomial Theorem12m

Practice Counting13m

Generating Combinatorial Objects: Code10m

Slides10m

Slides10m

Slides10m

Number of Segments and Diagonals20m

Forming Sport Teams15m

Number of Iterations of Nested For Loops4m

Sum of the First Six Rows of Pascal's Triangle2m

Expanding (3a-2b)^k20m

Practice Counting10m

Week

3We have already considered most of the most 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....

8 videos (Total 36 min), 3 readings, 8 quizzes

Review3m

Salad5m

Combinations with Repetitions7m

Distributing Assignments Among People3m

Distributing Candies Among Kids3m

Numbers with Fixed Sum of Digits4m

Numbers with Non-increasing Digits2m

Splitting into Working Groups4m

Salads10m

Slides1m

Slides1m

Salads10m

Combinations with Repetitions10m

Distributing Assignments Among People10m

Distributing Candies Among Kids15m

Numbers with Fixed Sum of Digits15m

Numbers with Non-increasing Digits7m

Splitting into Working Groups10m

Problems in Combinatorics45m

Week

4The 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....

17 videos (Total 126 min), 4 readings, 11 quizzes

Galton Board6m

Natural Sciences and Mathematics6m

Rolling Dice7m

More Probability Spaces10m

Not Equiprobable Outcomes4m

More About Finite Spaces6m

Mathematics for Prisoners7m

Not All Questions Make Sense10m

What Is Conditional Probability?7m

How Reliable Is The Test?8m

Bayes' Theorem8m

Conditional Probability: A Paradox7m

Past and Future8m

Independence8m

Monty Hall Paradox8m

`Our Position'6m

Slides

Slides

Slides

Slides

Concentration for Galton Board10m

Computing Probabilities for Two Dice12m

Computing Probabilities: More Examples12m

Fair Decisions and Imperfect Coins20m

Inclusion-Exclusion Formula10m

Computing Conditional Probabilities16m

Prisoner, King and Conditional Probabilities10m

More Conditional Probabilities8m

More About Independence20m

Monty Hall Gone Crazy20m

4.6

36 Reviewsgot a tangible career benefit from this course

By ZB•Oct 13th 2018

I really enjoyed taking this course. The teaching was pretty good and some of the quiz questions will challenge you if you haven't done Combinatorics before.

By CZ•Sep 11th 2018

The final project is hard for me cuz I don't have Python experience. and the logic is a little bit complicated. That's not for absolutely beginners!

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

National Research University - Higher School of Economics (HSE) is one of the top research universities in Russia. Established in 1992 to promote new research and teaching in economics and related disciplines, it now offers programs at all levels of university education across an extraordinary range of fields of study including business, sociology, cultural studies, philosophy, political science, international relations, law, Asian studies, media and communications, IT, mathematics, engineering, and more.
Learn more on www.hse.ru...

Discrete Math is needed to see mathematical structures in the object you work with, and understand their properties. This ability is important for software engineers, data scientists, security and financial analysts (it is not a coincidence that math puzzles are often used for interviews). We cover the basic notions and results (combinatorics, graphs, probability, number theory) that are universally needed. To deliver techniques and ideas in discrete mathematics to the learner we extensively use interactive puzzles specially created for this specialization. To bring the learners experience closer to IT-applications we incorporate programming examples, problems and projects in our courses....

When will I have access to the lectures and assignments?

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.

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. If you only want to read and view the course content, you can audit the course for free.

What is the refund policy?

Is financial aid available?

More questions? Visit the Learner Help Center.

Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.