Transcript Recursive Algorithm (4.4)

Counting Internet Addresses
• In IPv4 (Version 4 of the Internet Protocol) an address is a
string of 32 bits: network number (netid) + host number (hostid).
• Three forms of addresses:
– Class A: 0 + 7-bit netid + 24-bit hostid (largest network).
– Class B: 10 +14-bit netid + 16-bit hostid (medium-sized
network).
– Class C: 110 +21-bit netid + 8-bit hostid (small network).
– 1111111 is not available as netid of a class A network.
– No hostids with all 0s or all 1s.
• How many different IPv4 addresses are
available?
Counting Internet Addresses
• xa, xb and xc, denote the number of Class A, Class B
and Class C addresses available, respectively.
• Three forms of addresses:
– Class A: 0 + 7-bit netid + 24-bit hostid (largest network)
– Class B: 10 +14-bit netid + 16-bit hostid (medium-sized
network)
•
•
•
•
– Class C: 110 +21-bit netid + 8-bit hostid (small network)
xa= (27-1)*(224-2)=2,130,706,178.
xb=214*(216-2)=1,073,709,056.
xc=221*(28-2)=532,676,608.
Total=xa+xb+xc=3,737,091,842.
E1
E1∩ E2
E2
| E | = | E1 U E2 | = |E1| + |E2| - | E1∩ E2 |
How many bit strings of length eight either start with an 1 bit
or end with the two bits 00?
E= { all such bit strings }
E1 = { bit strings start with 1} { 1 xxxxxxx }
E2 = { bit strings end with 00} {xxxxxx00}
E1∩ E2 = {bits start with 1 and end with 00} {1xxxxx00}
|E1| = 27
|E2| = 26 | E1∩ E2 | = 25
| E | = | E1 U E2 | = |E1| + |E2| - | E1∩ E2 | = 128+64-32=160.
A tree
Problem
• How many positive integers between 100
and 999 inclusive
–
–
–
–
–
–
–
–
are divisible by 7?
are odd?
have the same three decimal digits?
are not divisible by 4?
are divisible by 3 or 4
are not divisible by either 3 or 4
are divisible by 3 but not by 4?
are divisible by 3 and 4?
Problem
• How many functions are there from the set
{ 1, 2, . . ., n }, where n is a positive
integer to the set { 0, 1 }
-- that are one-to-one?
– that assign 0 to both 1 and n?
– that assign 1 to exactly one of the positive integers
less than n?
Problem
• A Palindrome is a string whose reversal is
identical to itself (e.g., madam, tenet) How
many bit strings of length n are
palindromes?
n is even,
n is odd
Pigeonhole
Pigeonhole
Pigeonhole
Pigeonhole
Pigeonhole
Pigeonhole
Pigeonhole
Pigeonhole
Pigeonhole
Pigeonhole
Example (Application of pigeonhole principle)
Among any n+1 positive integers not exceeding
2n, there must be an integer that divides one of
the other integers.
Take n =5, n+1 =6, 2n=10
{1 4 7 8 9 10}
4 divides 8
Take n=10, n+1 =11, 2n=20
{1 3 4 6 8 9 11 15 17 19 20} 3 divides 6
Among any n+1 positive integers not exceeding 2n, there
must be an integer that divides one of the other integers.
Solution: a1, a2, … an+1
Write
aj = 2kj qj
qj are odd numbers less than 2n, and there are at most
n such qs.
So by pigeonhole principle, two of the qs must be
equal (say qi = qj)
ai = 2ki qi
aj = 2kj qj
if ki < kj, then ai divides aj
1. What is the minimum number of students, each of whom
comes from one of the 50 states, who must be enrolled in a
university to guarantee that there are at least 100 who come
from the same state?
2. How many numbers must be selected from the set {1, 2, 3,
4, 5, 6} to guarantee that at least one pair of these numbers
add up to 7?
3. Show that among any group of five (not necessarily
consecutive) integers, there are two with the same remainder
when divided by 4.
Announcement
1. 2nd Midterm next Monday (any objection?).
2. Grade worksheet and extra credit assignment will be
available next Monday.
3. One more chapter to cover (Chapter 9).
Today
6
7
8
9
10
13
14
15
16
17 18
20
5th quiz
21
22
28 29 30
2nd Midterm
11
12
All grades
except final
19
Final Exam
EC assignment
due
3 Florida has 16 million people. At least N people in Florida
have the same three initials and were born on the same day
of the year (not necessarily in the same year). What is N?
4 Let (xi, yi), i= 1, 2, 3, 4, 5, be a set of five distinct points
with integer coordinates in the xy plane. Show that the
midpoint of the line joining at least one pair of these points
has integer coordinates.
(3, 2)
(-2, 1)
(0.5, 1.5)
(2, 0.5)
(-0.5, 0)
(1,- 1)
Three midpoints all have fractional
coordinates
5.3 Permutations and Combinations
Permutation (of a set of n distinct objects) is an ordered
arrangement of these objects. (The number of all possible
permutations is denoted as P(n).)
r-Permutation is an ordered arrangement of r elements of a
set. (The number of r-permutations is denoted as P(n, r).)
The set (of 6 elements)
2 different permutations
2 different 3-permutations
5.3 Permutations and Combinations
In how many ways can we select three students from a group
of five students to stand in line for a picture? In how many
ways can we arrange all five of these students in a line for a
picture?
(a) 5 ways to select the first student, 4 ways to select
the second student, 3 ways to select the last student
…… 5*4*3=60
(b) 5 ways to select the first student, 4 ways to select
the second student …… 5*4*3*2*1 = 5!
5.3 Permutations and Combinations
Theorem: P(n, r) = n *(n-1)*(n-2) …. (n-r+1).
Corollary 1: P(n, r) = n! / (n-r)!.
Problem: How many ways are there to select a first-prize
winner, a second-prize winner and a third-prize winner
from 100 different people who have entered a contest?
Problem: How many permutations of the letters
ABCDEFGH contain the string ABC?
5.3 Permutations and Combinations
r-combination (of a set of n distinct elements) is an unordered
selection of r elements from the set. (The number of all
r-combinations is denoted as C(n, r).)
The set (of 6 elements)
3 different 3-permutations
2 different 3-combinations
Same selection (different ordering)
5.3 Permutations and Combinations
For example C(4, 2)= 6
{a, b, c, d } => {a, b}, {a, c}, {a, d}, {b, d}, {b, c} {c, d}
6 = 4! / (2! (4-2)! )
There are 4*3 r-permutations: each combination gives 2
2-permutations
Theorem: C(n, r) = n! / (r ! (n-r) ! )
Proof: r-permutations of the set can be obtained by forming
the C(n, r) r-combincations of the set and then ordering the
elements in each r-Combination.
P(n, r)= C(n, r) * P(r, r)
5.3 Permutations and Combinations
Corollary C(n, r) = C(n, n-r).
C(n, r) = n! /(r! (n-r)! ) = C(n, n-r).
Picking r-elements from the set is the same as picking the
remaining n-r elements.
Example: How many poker hands of five cards can be
dealt from a standard deck of 52 cards? Also, how many
ways are there to select 47 cards from a standard deck of
52 cards?
C(52, 5) for both.
5.3 Permutations and Combinations
How many bit strings of length n contain exactly r 1s?
(Each such bit string is determined by the positions of 1s
in the bit string)
How many ways are there for 5 women and 3 men to
stand in a line so that no two men stand next to each
other?
P(5, 5)*P(6, 3)