Transcript s04.1 - Electrical and Computer Engineering

Discrete Structures & Algorithms
More about sets
EECE 320 — UBC
Reminder: How to specify sets?
• Explicit enumeration: {John, Paul, George, Ringo}
• Implicitly: {1,2,3,…}, or {2,3,5,7,11,13,17,…}
• Using predicates: { x : P(x) is true },
– where P(x) is some predicate that is true for all elements of
the set
– Example: { x : x is prime }
• Recursive definitions
– Example: The set of integers divisible by 3 can be specified
as.
• Basis step: 3 S3
• Recursive step: If x, y S3 then x+y S3
7
Recursive set definitions
Assume S is a an alphabet . (for example S={0,1})
What set does this definition specifies?
• Basis step:  S*
(where  is the notation for the null string)
• Recursive step: If w S* and x S then wx  S*
8
Cardinality of sets
If S is finite, then the cardinality of S, |S|, is the
number of distinct elements in S.
If S = {1,2,3}, |S| = 3.
If S = {3,3,3,3,3},
|S| = 1.
If S = ,
|S| = 0.
If S = { , {}, {,{}} },
|S| = 3.
If S = {0,1,2,3,…}, |S| is infinite. (more on this later)
9
Inclusion/Exclusion
Example:
There are 250 ECE students.
100 are taking ECE 320.
120 are taking ECE 315.
50 are taking both.
ECE320
ECE315
How many people are taking ECE320 or ECE315?
100 + 120 – 50 = 170
|A  B| = |A| + |B| - |A  B|
10
Inclusion/Exclusion
Example:
There are 250 ECE students.
100 are taking ECE 320.
150 are taking ECE 315.
50 are taking both.
ECE320
ECE315
How many are taking neither ECE320 nor ECE315?
250 - (100+120-50) = 80
11
Generalized Inclusion/Exclusion
Suppose we have:
B
A
C
And we want to know |A U B U C|
|A U B U C| = |A| + |B| + |C|
- |A  B| - |A  C| - |B  C|
+ |A  B  C|
This intersection has been
counted thrice here
But has been subtracted
thrice here!
We have counted these
intersections twice here
Therefore, add it back
once to ensure it is
correctly counted.
12
Wrap up
• The principle of
inclusion/exclusion allows us
to compose sets for smaller
sets and to reason about the
size of the new set.
• Solve examples in the
textbook to become
comfortable with
inclusion/exclusion.
13
Set representations
14
Sets as bit strings
Let U = {x1, x2,…, xn}, and let A  U.
Then the characteristic vector of A is the
n-vector whose elements, xi, are 1 if xi  A,
and 0 otherwise.
Example: If U = {x1, x2, x3, x4, x5, x6},
and A = {x1, x3, x5, x6}, then the
characteristic vector of A is
(101011)
15
Sets as bit strings
Example: If U = {x1, x2, x3, x4, x5, x6},
A = {x1, x3, x5, x6}, and B = {x2, x3, x6},
then we have a quick way of finding the
characteristic vectors of A  B and A  B.
A 1 0 1 0 1 1
B 0 1 1 0 0 1
Bit-wise OR
Bit-wise AND
AB 1 1 1 0 1 1
AB 0 0 1 0 0 1
16
Representing sets
• Are bit strings always sufficient?
• What assumptions do we make when we adopt
the bit string representation?
– That we know the universe of possible elements.
– We also need to keep a list of all possible elements.
– If we are storing a set of names using a bit string, we
may need to also store information such as “Smith is bit
0, Rogers is bit 2, …”
17
Representing sets
• Alternative representations of sets?
– Arrays
– Linked lists
– …
• What is the primary operation to be supported?
– Set membership
– And, how do we implement such an operation? Search.
18
Sets as arrays
Smith
Rogers
Paul
Brown
…
Campbell
• What is the primary operation?
• Set membership.
• How do we test if “Scott” is in the set?
• Elements are in arbitrary positions.
• What is the maximum number of comparisons needed?
• If n is the cardinality (size) of the set?
• Maximum comparisons: n
• What is the minimum number of comparisons needed?
• What is the average number of comparisons needed?
• n/2. Why?
19
Complexity of search
Smith
Rogers
Paul
Brown
…
Campbell
• If the set is represented as an unordered list, we have
to search through all elements.
• Let f(n) be the time required to search for an element in
a list of size n.
• Let t be the time taken per comparison.
• Then: f(n)  (t)(n), and this is expressed as f(n)=O(n), or
the time complexity of sequential search is O(n).
• More about the big-O notation in another lecture.
20
Binary search
What if the array or the list were kept ordered?
Suppose we were searching for “Brown”.
Brown
Campbell
Dali
Rogers
…
Scott
• Compare with the middle element of the array.
• If “Brown” is smaller (lexicographically) then we
need to search only in the left half of the list, else
we need to search only in the right half of the list.
• We then proceed, iteratively, to make a
comparison with the middle element of the search
region.
21
How many comparisons? (binary search)
Brown
Campbell
Dali
Rogers
…
Scott
• For simplicity, assume N, the size of the array, is 2k.
• After each comparison, we reduce the size of our search
to a smaller array that is half the size of the initial array.
• Therefore: the maximum number of steps needed is …
– At worst, we need to bring the size of the search region to 1.
– How many steps would that take?
– Diminishing array sizes: 2k, 2k-1, …, 20
• k+1 = log2N+1.
22
How many comparisons? (binary search)
Brown
Campbell
Dali
Rogers
…
Scott
• If g(n) denotes the time required to search for an element
using binary search in an array of size n, then
– g(n)  (log2n+1)t,
– where t is the time needed per comparison/iteration.
• g(n) = O(log2n), is what we say.
23
What do you need to know?
(as good engineers)
• To understand how to perform computations
efficiently, we need to know
–
–
–
–
How to count!
How to sum a sequence of steps.
Reason about the complexity/efficiency of an algorithm.
Prove the correctness of our analysis.
•
•
•
•
•
Logic
Methods of inference
Proof strategies
Induction
…
– (and eventually, how to create better algorithms.)
24