Transcript Functions, Sequence and Relations

Chapter 3
Functions
 Definitions
 Cartesian product
 Domain
 Range
 Examples
 Hash function
 Modulus operator
 One to One Injective
 Onto Subjective
Functions
 Mathematics and Engineering subjects rely on the use
of functions, Sequence and Relations.
 Functions are used in Discrete Math, example to
analyze the execution of an algorithm.
Sequences
 A special kind of functions
 A list of letters as they appear in a word is an example
of sequence.
 Sequence takes order in account
 The word from is different from the word form
Will be covered in next lecture
Relations
 A set of ordered pairs.
 The existence or the presence of the order pair (a, b)
indicates that there is a relationship from a to b.
 The relational Dbase among records in a data base is
based on the Relations concept.
Will be covered in next lecture
Functions and the Cartesian
product
If X = {1,2,3} and Y = {a, b}
Then X * Y = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
X*Y is called the Cartesian product of X and Y
In General X * Y ≠ Y * X
Y * X ={(a, 1), ( b, 1), ( a, 2), ( b, 2), ( a, 3), ( b, 3)}
Draw graph to see the difference
An ordered pair
 (a, b) is considered distinct from (b, a) unless a = b
In other words (a, b) = (c, d)
Precisely when a = b and c = d
What is a function (f) ?
 A function assigns to each member of set X EXACTLY one
member of set Y, the sets X and Y may not be the same.
 Let X and Y be sets, a function (f) from X to Y is a subset of the
Cartesian product of X * Y
 For each x ∈ X there is EXACTLY one y ∈ Y, with (x, y) ∈ f
we denote the function f from x to y as
f: X Y
The set X is called the domain of f and the
set Y is called the codomain or range of f
{y | (x, y) ∈ f}
The arrow diagram
 The set f = {(1, a), (2, b), (3, a)} is a function from
X = { 1, 2, 3} to Y = {a, b, c}
For each element of X is assigned a unique value in Y
1
a
2
b
3
c
1 is assigned the unique value a
2 is assigned the unique value b
1 is assigned the unique value a
f
X
Y
An arrow from X to Y means we assign the
letter x to the integer j and we call the
For each arrow diagram to be a
function requires exactly one arrow
from each element in the domain .
Remember X is the domain
Notes
 The definition allows us to reuse elements in y such as
a in the previous diagram.
 The definition does NOT require us to use all elements
in y example c in the previous diagram.
 The domain of f is X and the range of f is (a, b)
Example of using The arrow diagram while the set
is NOT a function from XY
 The set f = {(1, a), (2, b), (3, a)} is NOT a function from
X = { 1, 2, 3, 4 } to Y = {a, b, c}
Because the element 4 is not assigned an element in Y
1
a
2
b
3
4
c
X
Y
NOTE :
1 is assigned the unique value a
2 is assigned the unique value b
1 is assigned the unique value a
4 is NOT assigned a e unique value
For each arrow diagram to be a function
requires exactly one arrow from each
element in the domain , in this case there is
no arrow from 4 .
Remember X is the domain
But the set X’ = {1, 2, 3} is a f to Y ={ a, b, c}
Example 2 of using The arrow diagram while the
set is NOT a function from XY
 The set {(1, a), (1,b)(2, b), (3, c)} is NOT a function from
X = { 1, 2, 3 } to Y = {a, b, c}
Because the element 1 is not assigned a uniqe n element in Y
1
a
2
b
3
c
X
Y
1 is assigned the value s a and b
2 is assigned the unique value b
1 is assigned the unique value a
4 is NOT assigned a e unique value
For each arrow diagram to be a function
requires exactly one arrow from each
element in the domain , in this case there is
no arrow from 4 .
Remember X is the domain
How to use the function notation
to define a function
 Le f(x) = x2
f(2) = 4
f(-3.5) =12.25
F(0) = 0
In this case the definition is incomplete because the
domain is not specified.
But if we were told that the domain is the set of all real
numbers in ordered pair notation we would have
f = {(x, x2 ) | X is areal number
The range of f is the set of all real numbers
Visualizing a function
 Another way to visualize a function is to draw a graph
 The graph of a function whose domain and range are a
subset of the real numbers is obtained by plotting the
points
x
x2
0
0
1
1
2
4
3
9
-1
1
-2
4
The Modulus Operator % mod
 If x is an integer and y is a positive integer we define
x mod y ( x % y ) to be the remainder when x is divided by y
x
y
X%Y
6
2
0
12
3
0
9
2
1
11
5
1
Hashing Concept
 To find where is data and to go to it directly with one
test.
 Hash search: the key, through an algorithm function
determines the location of the data.
 A key to address transformation, maps the key to an
address in a list
Hash
function
 Objective: transform the key into a component
number that is an integer with a limited range:
Large Key space
(Hash function domain)
Black box
Small Address Space
(hash function range)
Transforms a large key Space into a small Address Space
Hashing Methods
1.
2.
3.
4.
5.
6.
7.
8.
Direct Hashing
Subtract method
Modulo Method
Digit Extraction
Mid Square
Folding
Rotation
Pseudo random
Figure 2-6
Example
 Student numbers
Key Space: 0 to 999999999 (1 billion values)
Hash function: f (key) = f (stu#) = stdu# % 1000
Example: f(142731245) = 142731245 % 1000 = 245
Record with key 142731245 is placed in component: 245
Address Space: 0 to 999 (1 thousand values)
Modulo Method or Division Remainder
Method
 Divide the key by the array size or by a prime number and
use the remainder for the address.
Example: for a company of 100 employees expected to grow
to 300, create a numbing system to handle 1,000,000
employees.
The first prime number after 300 is 307
For the number 121267 % 307  2 (the address will be 2)
For the number 045128 % 307  306 (the address will be 306)
Collision And Collisions Resolution
 Collision occurs when there is no one to one mapping,
 Direct and subtraction hashing methods result in no
collisions but limited
 All other hashing methods create collisions
 Because of the collisions:
 There must be empty elements all times.
 A hashing list should not be allowed to become more
than 75% full
Figure 2-13
Some Collision Resolution Methods
Open Addressing
 When a collision occurs, the prime area (the area that
contains all home addresses) is searched for an open
or an unoccupied element where the new data can be
placed.
 Four different methods for searching
 Linear probe
 Quadric probe
 Double hashing
 Key offset
Linear Probe
If a collision occurs, add 1 to the address and store in the
next location.
If next location is occupied add 1 again
Keep adding 1 until an empty space is found.
Quadric probe
 The increment is the collision probe number squared
 For the first probe add 1
2
 For the second probe add 2
2
 Until an empty location is found
Double hashing or pseudorandom hashing
 Use a random number generator to rehash the address
A pseudorandom number generator (PRNG), also
known as a deterministic random bit generator
(DRBG),[1] is an algorithm for generating a sequence of
numbers that approximates the properties of random
numbers.
One to One or Injective functons
 If for each y ∈ Y there is at most x ∈ X with f(x) = y
The function is said to be One to One.
The function f ={(1,b), (3,a) ,(2,c)}
From X= {1, 2, 3} and Y = {a, b, c} is One to One
Because each element in Y has one arrow pointing to
it from x
1
a
2
b
3
c
x
f
Y
Not One to One
If some elements in y have more than one arrow pointing
to them then it is not One to One , not Injective
1
a
2
b
3
Not
x
f
c
Y
One To One and Onto
 If f is a function from X to Y and the range of f is Y, Y
is said to be Onto Y or Onto function.
f ={(1,b), (3,b) ,(2,c)}
X= {1, 2, 3} and Y = {a, b, c} is One to One and
Onto
Because each element in Y has one arrow pointing to
it from x
1
a
2
b
3
c
x
f
Y
Onto
This function is One to One, each
element in Y has at most one
arrow pointing to it from X.
This function is NOT Onto Y
because there is no arrow
pointing to d
This function is not One to One
because a has 2 arrows pointing
to it, This function is NOT Onto
Y because there is no arrow
pointing to c
1
a
1
a
2
b
2
b
3
C
d
3
C
x
f
Y
bijection
 A function that is One to One and Onto is also called
a bijection
Same Size and Same Cardinality
.
 If
f is a bijection from a finite set X to a finite set Y, then |X| =|Y|,
means that the sets have the same cardinality (number of elements of
the set) and are the same size.
f ={(1,a), (2,b) ,(3,c, 4,d)}
X= {1, 2, 3,4 } and Y = {a, b, c, d}, both sets have the four
elements, f counts the elements in Y: f(1)= a, f(2) =b in the second element
Y and so on.
1
a
2
3
4
x
b
f
C
d
Y
Inverse
If f is One to One and Onto function from X to Y, it can
be shown that {(y, x) | (x, y) ∈ f} is a one to one function
from Y to X and denoted as f -1 and is called f inverse.
For the function f ={(1,a), (2, c) ,(3,b)}
f -1 ={(a,1), (c, 2) ,(b, 3)}
a
1
b
2
3
C
Y
f
x
Homework and Lab
 Section Review Exercises Page 131 and 132