Chapter 4 : Discrete Probability Flashcards
What is the Applications of using Discrete Probability in Computer Science? ( 3 )
- Probability theory plays important role in study of the complexity of algorithms
- Counting is required to determine enough telephone numbers, internet protocol addresses
- Programmers use probability to measure the success of the program before running it
List out 2 basic counting rules and when to use
- The Sum Rule
- If the task can’t be done at the same time
- The Product Rule
- If the task can be done at the same time
- Procedure can be broken down into 2 tasks
A student can choose a computer project from one of three lists. The three lists contain 23, 15 and 19 possible projects respectively. How many posible projects are there to choose from?
- 23 + 15 + 19 = 57 Projects
- The student need to choose a project from 1 of 3 lists so he may just choose 1 from 23 , 15 or 19 which the task can’t be done at the same time, he is required to choose 1 project on any one list
A student can choose a computer project from one of every lists. The three lists contain 23, 15 and 19 possible projects respectively. How many posible projects are there to choose from?
- 23 * 15 * 19 = 6555 Projects
- The student need to choose a project from every lists so he need to choose 1 from 23 , 15 or 19 which the task needed to be done at the same time.
How many different 8 - letter ( uppercase ) password are there?
1. With repetitions
2. Without repetitons
- 26 x 26 x 26 x 26 x 26 x 26 x 26 x 26 = 26^8
- 26 x 25 x 24 x 23 x 22 x 21 x 20 x 19 = 62990928000
- It uses the Product rule since we need to choose uppercase letters ( A - Z ) and put it in the first place and so on
How many difference license plates are available if each plate contains a sequence of 3 letters followed by 3 digits?
- 26 x 26 x 26 x 10 x 10 x 10 = 17576000
If there are 6 men and eight women auditioning for the leading male and female roles, how many ways the director can cast his leading couple?
- 6 x 8 = 48 ways
There are 7 different introductory books each on C++, Java and Perl. How many books that can be recommended to a student who is interested in learning a first programming language?
- 7 + 7 + 7 = 21 Books
A bag containes nince dics numbered from 1 to 9
If the number is even, a coin is tosses. If the number is odd, then a dice is thrown.
- 4 x 2 + 5 x 6 = 38
- 4 ( Even 2 , 4 , 6 , 8 ) x 2 ( Coin - Head , Tail )
5 ( Odd 1 , 3 , 5 , 7 , 9 ) x 6 ( Dice )
What does a Tree Diagram consists?
- Branch
- Branch is used to represent each possible choice
- Leaves
- Leaves is used to represent possible outcome
What is the definition of Permutation ( nPa ) ?
- Any linear arrangement of n discinct objects
A class has 4 students A , B , C , D , 4 students are to be chosen and steated in a row for a picture, How many such linear arragements are possible?
- 4! = 24
What does n! involves?
- Involve arrangement of all items
- Students A B C D form in a row to take picture
4!
What does P ( n , r ) involves?
- Involve arrangement of some items
- Form password uppercase ( A - Z ) with the length of 8 without repeating
P ( 26 , 8 )
What does n^r involves?
- Involve arrangement of repetition
- Form password uppercase ( A - Z ) with the length of 8
26^8
There are 6 children in a drawing class
1. In how many ways can all these 6 children be arranged in a line?
2. In how many ways can 4 children from the class be arranged in a line?
- 6! = 720
- P ( 6 , 4 ) = 6! / 2! = 360
If repetitions of letters are allowed, how many 5 - letter sequences are possible for letters CDE?
- 3^5
n = 3 ( C , D , E )
r = 5 ( 5 - letter sequence )
Does sequence / arrangement matter in Combination?
- No
How to press 1. P ( 26 , 8 ) and 2. C ( 26 , 8 ) in calculator ?
- Shift x ( Multiplication )
- Shift / ( Division )
What does 1. n and 2 . r represent in Permutation and Combination?
- Total Items
- Selection
What is the outcome for C ( n , 0 ) ? ( 2 )
- 1
- C ( n , n )
C ( n , 0 ) = 1
= C ( n , n )
What is the outcome for C ( n , 1 ) ? ( 2 )
- n
- C ( n , n-1 )
C ( n , 1 ) = n
= C ( n , n-1 )
There are 5 women and 4 men in a club. A team of four has to be chosen. How many different teams can be chosen if there must be either one women or exactly 2 women on the team?
5C1 x 4C3 + 5C2 x 4C2
5C1 x 4C3 ( Either One Women )
One Women x 3 Men
5C2 x 4C2 ( Exactly 2 Women )
2 Women x 3 Men
Automobiles comes in 4 models, 12 colors, 3 engine sizes and 2 transmission types
( i ) How many distinct automobiles can be manufactured?
( ii ) IF one of the available color is blue, how many different blue automobiles can be manufactured?
i. 4 x 12 x 3 x 2 = 288
ii. 4 x 3 x 2 = 24
A collection of eight different books consists of 2 books on artificial intelligence, 3 books on operating systems , and 3 books on data structures.
1. How many ways can the books arranged on a shelf so that all books on a single subject are together?
2. How many ways can the books arranged on a shelf so that the three books on operating systems are together?
3. How many ways can the books be arranged on a shelf so that the two books on artificial intelligence occur at the right end of the arrangement?
- 2! x 3! x 3! x 3!
- 6! x 3!
- 6! x 2
- 2! . 3! . 3! . 3! ( AI , DS , OS can re-arrange)
_ _ _ _ _ _ _ _
25 buses are running between two places P and Q. In how many ways can a person go from P to Q and return by a different bus?
- 25 x 24 = 600 ways
x 24 since the quesion ask ways can a person go from P to Q and return by a different bus
- If same bus is 25 x 25
There are 30 laptops in a computer center. Each laptop has 14 ports. How many different ports to a laptops in the center are there?
- 30 x 14 = 420 ports
Each laptop has 14 ports, so we need to x by 30 ( laptop )
30^14 would mean that each of the 30 laptops has 14 sets of 30 ports.
How many strings of 4 English letter are there if
1. No letter can be repeated.
2. Starts with letter “X”, and if letters can be repeated.
3. Starts and ends with vowels, if no letter can be repeated
- 26P4
- 1 x 26^3
- 5P2 x 24P2
A bag contains 2 white balls, 3 black balls and 4 red balls. In how many ways can 3 balls be drawn from the bag, if at least one black ball is to be included in the draw?
- 3C3 + 3C2 x 6C1 + 3C1 x 6C2
3C3 = Taken out 3 black ball
3C2 x 6C1= Taken out 2 black ball
3C1 x 6C2 = Taken out 1 black ball
- Since the questions is asking at least 1 black ball is to be included in the draw
Jennifer has 6 jeans, 8 blouses, and 5 hair dressers. How many outfits can she select if her outfit consists of one jeans, one blouse and one hair dresser?
- 6C1 x 8C1 x 5C1 = 240
Among the seven nominees for two vacancies on the city council are three men and four women. In how many ways these vacancies can be filled
1. with any two of the nominees?
2. with any two of the women?
3. with one of the men and one of the women?
- 7C2
- 4C2
- 3C1 x 4C1
A student has to answer 10 questions, choosing at least 4 from each of Parts A and B. If there are 6 questions in Part A and 7 in Part B, in how many ways can the student choose 10 questions?
- 6C4 x 7C6 + 6C6 x 7C4 + 6C5 x 7C5
A B
4 6 = 6C4 x 7C6
6 4 = 6C6 x 7C4
5 5 = 6C5 x 7C5
In a class of 12 students, a project is assigned in which the students will work in groups. Three groups are to be formed, consisting of five, four and three students.
Calculate the number of ways in which the groups can be formed.
- 12C5 x 7C4 x 3C3 = 27720
Given a committee of 4 people has to be chosen from a panel of 10 people.
1. If two certain persons must be on the committee, in how many ways can the
committee be chosen?
2. If two certain persons must not be on the committee, in how many ways can the
committee be chosen?
- 8C2
- 8C4
What is probabilty?
- Is the likehood or chance of something happening
What is the format for probability?
- P(E) = Number of way that E can occur / Number of Possible Outcomes = m / n
P(E) = N(E) / N(S)
What is the rules of probability?
- The value must be between 0 and 1 inclusive
- 0 <= P(E) <= 1
- If the event is impossible, it will be P(E) = 0
- If the event is certain, it will be P(E) = 1
- Add all probability P(e1) + P(e2) + … + P(en) , the probability will be 1
A fair dice is tossed, what is the probability of getting number greater than 4?
- 2 / 6
What is the probability of selecting 9 balls from 6 red balls, 5 white balls and 5 blue balls if each selection consists of 3 balls of each color?
- ( 6C3 x 5C3 x 5C3 ) / 16C9
When does a mutually exclusive events occur?
- Occurs when 2 events of the same experiment are said to be mutually exclusive if their respective events do not overlap
P ( Aces and Kings ) = 0
* Cards can’t be both Aces and Kings
- When the experiment is performed, events that are mutually exclusive cannot happen at the same time
How to calculate P ( A ∪ B ) using the addition rule giving the condition
1. Mutually Exclusive Event
2. Not Mutually Exclusive Event
- P ( A ∪ B ) = P( A ) + P( B )
- P ( A ∪ B ) = P( A ) + P( B ) - P ( A ⋂ B )
- P ( A ⋂ B ) from not mutually exclusive event is to prevent overlap from intersection values
A bag contain 4 red marbles, 7 white marbles, 5 black marbles and 2 blue marbles. What is the probability that a marble picked form the bag randombly is either a red or white marble?
- P ( W ∪ R ) = 7 / 18 + 4 / 18 = 11 / 18
Find the probability of getting a number greater than 3 or multiple of 2 when we throw a dice
- P ( G ∪ M ) = 3 / 6 + 3 / 6 - 2 / 6 = 2 / 3
Greater than 3 Multiple of 2
4 2
5 4
6 6
A computer company receives 350 applications from computer graduates for a job planning a line of new Webservers. Suppose that 220 of these applicants majored in computer science,147 majored in business, and 51 majored both in computer science and in business. Find the probability of these applicants majored neither in computer science nor in business?
350 Applications
- 169 CS ( 220 - 51 )
- 147 B ( 147 - 51 )
- 51 Both
- 34 Not major in both
Solution 1
1. 34 / 250
* Represent with Venn Diagram
Solution 2
P[ ( C U B )’ ]
= 1 - P ( C U B )
= 1 - ( 169 / 350 + 147 / 350 + 51 / 350 )
= 1 - 316 / 350
= 34 / 350
What is the rule used in Independent and Dependent Events ? ( Sum Rule , Product Rule )
- Product ( Multiplication Rule )
P ( A ⋂ B ) - The AND rule
Mutualy Exclusive is Sum Rule
P ( A U B ) - The OR rule
- And and Or will be shown in the Question
What is the definition of independent events?
- If the occurrence of 1 event has no effect on whether or not the other event occurs
P ( A ⋂ B ) = P ( A ) x P ( B )
What is the definition of dependent events?
- If the occurrence of 1 event has some effect on whether or not the other event occurs
P ( A ⋂ B ) = P ( A ) x P ( B / A )
Suppose you spin each of these 2 spinners. What is the probability of spinning an even number and a vowel? ( Independent Events )
Spinner 1 - 1 , 2 , 3 , 4 , 5 , 6
Spinner 2 - P , O , R , S , T
- ( 3 / 6 ) x ( 1 / 5 ) = ( 1 / 2 ) x ( 1 / 5 )
3 / 6 - 2 , 4 , 6 in Spinner 1 ( Even Number )
1 / 5 - O in Spinner 2 ( Vowel )
What is the probability to get 7 heads in a row when tossing a coin 7 times? ( Independent Events )
- ( 1 / 2 ) ^ 7
= 1 / 128
What is the probability that the next toss is also a head, given that we have just got 6 heads in a row?
- 1 / 2
A bag contains 5 red marbles, 4 green marbles and 1 blue marble. A marble is chosen at random from the bag and then not returned to the bag before second marble is chosen. What is the probability both marbles are green? ( Dependent Event )
- P ( G1 And G2 ) = ( 4 / 10 ) x ( 3 / 9 ) = 12 / 90
A bag contains 3 black balls and 5 white balls. Paul picks a ball at random from the bag and replaces it back in the bag. He mixes the balls in the bag and then picks another ball at random from the bag.
- Construct a probability tree of the problem.
- Calculate the probability that Paul picks
( a ) Two Black Balls
( b ) One ball is black and other ball is white
_ 3 / 8 _ B _ 3 / 8 _ B ( B , B )
_ 5 / 8 _ W ( B , W )
_ 5 / 8 _ W _ 3 / 8 _ B ( W , B )
_ 5 / 8 _ W ( W , W )
2 ( a ) P ( Two Black Balls ) = ( 3 / 8 ) x ( 3 / 8 ) = 9 / 64
( b ) P ( B , W ) + P ( W , B ) = ( 3 / 8 x 5 / 8 ) + ( 5 / 8 + 3 / 8 ) = 30 / 64
A jar consists of 21 sweets. 12 are green and 9 are blue. William picked two sweets at randomly one by one. He ate the sweet.
1. Draw a tree diagram to represent the experiment.
2. Calculate the probability that
( a ) Both sweets are blue
( b ) One sweet is blue and other sweet is green
- _ 12 / 21 _ G _ 11 / 20 _ G ( G , G )
_ 9 / 20 _ B ( G , B )
_ 9 / 21 _ B _ 12 / 20 _ G ( B , G )
_ 8 / 20 _ B ( B , B ) - ( a ) P ( Both sweets are blue ) = P ( B , B ) = 9 / 21 x 8 / 20 = 6 / 35
( b ) P ( One sweet is blue and one sweet is green ) = P ( G , B ) + P ( B , G ) = ( 12 / 21 x 9 / 20 ) + ( 9 / 21 x 12 / 20 ) = 18 / 35
