Combinatorics and Probability

Type product
Logo van Coursera (CC)
Opleiderscore: starstarstarstar_halfstar_border 7,2 Coursera (CC) heeft een gemiddelde beoordeling van 7,2 (uit 6 ervaringen)

Tip: meer info over het programma, prijs, en inschrijven? Download de brochure!

Beschrijving

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

About 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 course we discuss most standard combinatorial settings that can help to answer questions of this type. We will especially conce…

Lees de volledige beschrijving

Veelgestelde vragen

Er zijn nog geen veelgestelde vragen over dit product. Als je een vraag hebt, neem dan contact op met onze klantenservice.

Nog niet gevonden wat je zocht? Bekijk deze onderwerpen: Statistiek, Excel, Big Data, Data Science en Microsoft R.

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

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

Created by:  University of California, San Diego, Higher School of Economics
  • Taught by:  Alexander S. Kulikov, Visiting Professor

    Department of Computer Science and Engineering
  • Taught by:  Vladimir Podolskii, Associate Professor

    Computer Science Department
Basic Info Course 2 of 5 in the Introduction to Discrete Mathematics for Computer Science Specialization Level Beginner Commitment 6 weeks, 3-5 hours/week Language English How To Pass Pass all graded assignments to complete the course. Coursework

Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.

Help from your peers

Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.

Certificates

Earn official recognition for your work, and share your success with friends, colleagues, and employers.

University of California, San Diego 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. Higher School of Economics 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

Syllabus


WEEK 1


Basic Counting



Suppose 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, 4 readings, 1 practice quiz expand


  1. Video: Why counting
  2. Video: Rule of Sum
  3. Practice Quiz: Numbers Divisible by 2 or 3
  4. Video: How Not to Use the Rule of Sum
  5. Video: Convenient Language: Sets
  6. Video: Generalized Rule of Sum
  7. Reading: Slides
  8. Video: Number of Paths
  9. Video: Rule of Product
  10. Video: Back to Recursive Counting
  11. Reading: Slides
  12. Video: Number of Tuples
  13. Video: Licence Plates
  14. Video: Tuples with Restrictions
  15. Video: Permutations
  16. Reading: Listing All Permutations
  17. Reading: Slides

Graded: Rule of Sum in Programming
Graded: Operations with Sets
Graded: Generalized Rule of Sum
Graded: Puzzle: Number of Paths
Graded: Rule of Product in Programming
Graded: Applications of the Rule of Product
Graded: Tuples
Graded: Counting with Restrictions

WEEK 2


Binomial Coefficients



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 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, 4 readings, 1 practice quiz expand


  1. Video: Previously on Combinatorics
  2. Reading: Generating Combinatorial Objects: Code
  3. Video: Number of Games in a Tournament
  4. Video: Combinations
  5. Practice Quiz: Number of Iterations of Nested For Loops
  6. Reading: Slides
  7. Video: Pascal's Triangle
  8. Video: Symmetries
  9. Video: Row Sums
  10. Video: Binomial Theorem
  11. Reading: Slides
  12. Video: Practice Counting
  13. Reading: Slides

Graded: Number of Segments and Diagonals
Graded: Forming Sport Teams
Graded: Sum of the First Six Rows of Pascal's Triangle
Graded: Expanding (3a-2b)^k
Graded: Practice Counting

WEEK 3


Advanced Counting



We 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, 3 readings, 5 practice quizzes expand


  1. Video: Review
  2. Video: Salad
  3. Video: Combinations with Repetitions
  4. Reading: Salads
  5. Reading: Slides
  6. Practice Quiz: Distributing Assignments Among People
  7. Video: Distributing Assignments Among People
  8. Practice Quiz: Distributing Candies Among Kids
  9. Video: Distributing Candies Among Kids
  10. Practice Quiz: Numbers with Fixed Sum of Digits
  11. Video: Numbers with Fixed Sum of Digits
  12. Practice Quiz: Numbers with Non-increasing Digits
  13. Video: Numbers with Non-increasing Digits
  14. Practice Quiz: Splitting into Working Groups
  15. Video: Splitting into Working Groups
  16. Reading: Slides

Graded: Salads
Graded: Combinations with Repetitions
Graded: Problems in Combinatorics

WEEK 4


Probability



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.


17 videos, 4 readings expand


  1. Video: The Paradox of Probability Theory
  2. Video: Galton Board
  3. Video: Natural Sciences and Mathematics
  4. Video: Rolling Dice
  5. Video: Probability Spaces
  6. Reading: Slides
  7. Video: Not Equiprobable Outcomes
  8. Video: About Finite Spaces
  9. Video: Mathematics for Prisoners
  10. Video: Not All Questions Make Sense
  11. Reading: Slides
  12. Video: What Is Conditional Probability?
  13. Video: How Reliable Is The Test?
  14. Video: Bayes' Theorem
  15. Video: Conditional Probability: A Paradox
  16. Video: Past and Future
  17. Video: Independence
  18. Reading: Slides
  19. Video: Monty Hall Paradox
  20. Video: `Our Position'
  21. Reading: Slides

Graded: Concentration for Galton Board
Graded: Computing Probabilities for Two Dice
Graded: Computing Probabilities: Examples
Graded: Fair Decisions and Imperfect Coins
Graded: Prisoner and King
Graded: Inclusion-Exclusion Formula
Graded: Computing Conditional Probabilities
Graded: Prisoner, King and Conditional Probabilities
Graded: Conditional Probabilities
Graded: About Independence
Graded: Monty Hall Gone Crazy

WEEK 5


Random Variables



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.


9 videos, 6 readings expand


  1. Video: Random Variables
  2. Video: Average
  3. Reading: Average Value of a Dice Throw: Experiment
  4. Video: Expectation
  5. Reading: Slides
  6. Video: Linearity of Expectation
  7. Video: Birthday Problem
  8. Reading: Slides
  9. Video: Expectation is Not All
  10. Reading: Dice Game Experiment
  11. Reading: Slides
  12. Video: From Expectation to Probability
  13. Video: Markov’s Inequality
  14. Video: Application to Algorithms
  15. Reading: Slides

Graded: Random Variables
Graded: Average
Graded: Expectations
Graded: Linearity of Expectation
Graded: Bob’s Party
Graded: Linearity
Graded: Average Income
Graded: Bob’s Party Revisited
Graded: Alice’s tests

WEEK 6


Project: Dice Games



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.


3 videos, 3 readings expand


  1. Video: Dice Game
  2. Video: Playing the Game
  3. Reading: Experiment: Dice Game
  4. Reading: Slides
  5. Video: Project Description
  6. Reading: Slides

Graded: Final Project: Dice Game

Blijf op de hoogte van nieuwe ervaringen

Er zijn nog geen ervaringen.
  • Vraag informatie aan over deze cursus. Je ontvangt vanaf dan ook een seintje wanneer iemand een ervaring deelt. Handige manier om jezelf eraan te herinneren dat je wilt blijven leren!
  • Bekijk gerelateerde producten mét ervaringen: Statistiek.

Deel je ervaring

Heb je ervaring met deze cursus? Deel je ervaring en help anderen kiezen. Als dank voor de moeite doneert Springest € 1,- aan Stichting Edukans.

Er zijn nog geen veelgestelde vragen over dit product. Als je een vraag hebt, neem dan contact op met onze klantenservice.

Download gratis en vrijblijvend de informatiebrochure

Aanhef
(optioneel)
(optioneel)
(optioneel)
(optioneel)
(optioneel)

Heb je nog vragen?

(optioneel)
We slaan je gegevens op om je via e-mail en evt. telefoon verder te helpen.
Meer info vind je in ons privacybeleid.