Transcript Lecture note 9

Discrete Structures
Li Tak Sing (李德成)
mt263f-9.ppt
Pigeonhole principle
If m pigeons fly into n pigeonholes where
m>n, then one pigeonhole will have two or
more pigeons.
Examples in pigeonhole principle
 How many people are needed in a group to say
that three were born on the same day of the
week?
 How many people are needed in a group to say
that four were born in the same month?
 Why does any set of 10 nonempty strings over
{a,b,c} contain two different strings whose
starting agree and whose ending letters agree?
 Find the size needed for a set o nonempty
strings over {a,b,c,d} to contain two strings
whose starting letters agree and whose ending
letters agree.
The Mod function and inverses
Let n>1 and let f:NnNn be defined as
follows, where a and b are integers.
f(x)=(ax+b)mod n.
Then f is a bijection iff gcd(a,n)=1. When
this is the case, the inverse function f-1 is
defined by
f-1(x)=(kx+c) mod n
where c is an integer such that f(c)=0, and
k is an integer such that 1=ak+nm for
some integer m.
1=ax+by
Given that gcd(a,b)=1, then there are x,y
such that 1=ax+by
For example, gcd(10,7)=1,
first we have 10=1*7+3
then we have 7=3*2+1
therefore we have 2*10=2*7+(7-1)
2*10=3*7-1
1=3*7-2*10
Example
Find a,b so that 7a+5b=1
Find a,b so that 7a+11b=1
Simple ciphers
N26={0,1,..25} represents letters {a,...,z}
We can use a function to transform a letter
to another. For example
f: N26N26, f(x)=(x+5) mod 26
The inverse of f, denoted as f-1, is:
f-1(x)=(x-5) mod 26
f is known as a cipher which would
transform a letter into another letter to hide
secret.
Multiplicative cipher
The previous cipher is called an additive
cipher because addition is use.
A multiplicative cipher is one that
multiplication is used.
An example is:
g(x)=3x mod 26
the inverse is g-1(x)=9x mod 26
Example
Determine where the following functions
define a cipher. If a function is a cipher,
then find the inverse function
f(x)=2x mod 6
f(x)=2x mod 5
f(x)=5x mod 6
f(x)=(3x+2) mod 6
f(x)=(2x+3) mod 7
Hash function
A hash function is a function that maps a
set S of keys to a finite set of table
indexes, which we'll assume are 0,1,...,n1. A table whose information is found by a
hash function is called a hash table.
Hash example
For example, let S be the set of threeletter abbreviations for the months of the
year. We might define a hash function
f:S{0,1,..,11} in the following way.
f(XYZ)=(ord(X)+ord(Y)+ord(Z))mod 12.
where ord(X) represents the ASCII code
for X.
One use of hash functions
 Assume that you have a table of m entry and
you want to store some items in the table. Each
item has a key which can be used to uniquely
identify it. Now, we can use a hash function so
that it will generate an index for the item to be
stored in the corresponding entry.
 This method has an advantage that when we
know of the key, we can find the position where
the item is stored.
Collisions
If the numbers of objects to be stored is
greater than the size of the table, then
collision must occur.
One technique to solve the problem of
collision is called linear probing. With this
technique the program searches the
remaining locations in a linear manner.
Hash examples
Let S={Monday, Tuesday, Wednesday,
Thursday, Friday, Saturday, Sunday} and
suppose that f:SN7 is the hash function
defined by f(x)=lenght(x) mod 7 where
length(x) is the number of letters in x. Use
h to place each day of S into a hash table
indexed by {0,1,..,6} starting with Monday,
then Tuesday, and so on until Sunday.
Resolve collisions by linear probing with a
gap of 2.