Transcript Counting1

Counting
1
Situations where counting
techniques are used
You toss a pair of dice in a casino game.
You win if the numbers showing face up
have a sum of 7.
Question: What are your chances of
winning the game?
2
Situations where counting
techniques are used
To satisfy a certain degree requirement,
you are supposed to take 3 courses from
the following group of courses:
CS300, CS301, CS302, CS304,
CS305, CS306, CS307, CS308.
Question: In how many different ways the
requirement can be satisfied?
3
Situations where counting
techniques are used
 There are 4 jobs that should be processed
on the same machine.
(Can’t be processed simultaneously).
Here is an example of a possible schedule:
Job 3
Job 1
Job 4
Job 2
 Question: What is the number of all possible
schedules?
4
Situations where counting
techniques are used
 Consider the following nested loop:
for i:=1 to 5
for j:=1 to 6
[ Statement 1 ;
Statement 2 . ]
next j
next i
 Question: How many times the statements in the
inner loop will be executed?
5
Counting and Probability
Suppose we toss two coins.
Question. What are the chances of getting
0, 1, 2 heads?
The set of all possible outcomes:
S = {(H,H), (H,T), (T,H), (T,T)}
Event of getting exactly one head
corresponds to the subset {(H,T), (T,H)} .
Thus, chances of getting exactly one head is
2 / 4 = .5 ( which is the same as 50% ).
Random Processes,
Sample Space and Events
 A process is called random if
 a set of different outcomes are possible;
 one of the outcomes is sure to occur;
 but it is impossible to predict with certainty
which outcome that will be.
 A sample space is the set of all possible outcomes
of a random process or experiment.
 An event is a subset of a sample space.
7
Probability
 If S is a finite sample space
(in which all outcomes are equally likely),
E is an event in S,
then the probability of E is
the number of outcomes in E
P( E ) 
the total number of outcomes in S
 Notation: For any finite set A,
n(A) denotes the number of elements in A.
Then P( E )  n( E )
n( S )
8
Example on Probability
 You toss a pair of dice in a casino game.
You win if the numbers showing face up
have a sum of 7.
 Question: What are your chances of
winning the game?
 Solution.
Sample Space: S = { (1,1), (1,2), …, (6,6) }
= { (i,j) |  i, j 1,…,6 }
The event that the sum is 7:
E = { (i,j) | i, j 1,…,6 and i+j=7 }
= { (1,6), (2,5), (3,4), (4,3), (5,2), (6,1) }
n(S) = 62 = 36 , n(E) = 6.
Thus, chances of winning = P(E) = 6/36 = 1/6 .
Applying the dice example in Monopoly Game
• Your opponent’s token is in one of the squares
• His turn consists of rolling two dice and moving the token
clockwise on the board the number of squares indicated by
the sum of dice values
• When his token lands on a property
that is owned by you, you collect rent
• It is more advantageous to have houses or
hotels on your properties because rents are
much higher than for unimproved properties
• You might build houses or hotels on
your properties before your opponent rolls the dice
• Suppose you own most of the squares following (clockwise)
your opponent’s token.
In which square should you build houses or hotels?
Number of Elements in a List
If m and n are integers and m ≤ n ,
then there are n-m+1 integers
from m to n inclusive.
Example:
a) How many elements are there in the array
A[12], A[13], …, A[75], A[76] ?
b) What is the probability
that a randomly chosen element of the array
has a subscript which is divisible by 7 ?
11
Number of Elements in a List
• Example (cont.):
Solution: a) 76 – 12 + 1 = 65 .
b) Sample space:
S = { A[i] | 12 ≤ i ≤ 76 } .
Event that the index is divisible by 7:
E = { A[i] | 12 ≤ i ≤ 76 and 7|i } .
n(S) = 65 from part (a).
14=7∙2, 21=7∙3, …, 70=7∙10 .
Thus, n(E) = 10-2+1 = 9 .
Hence the probability that the index is divisible by 7:
P(E) = n(E) / n(S) = 9 / 65 ≈ .14
12