Transcript Discrete Structure - Open University of Hong Kong

Discrete Structure
Li Tak Sing(李德成)
Lectures 20-22
1
Section 4.3.3 Well-founded orders
Well-founded
A poset is said to be well-founded if every
descending chain of elements is finite. In this
case, the partial order is called a well-founded
order.
2
Examples of well-founded poset
The < relations of N.
100>90>78>.. This chain must end with finite
terms.
<{a,b}*, shorter>
aa shorter aab shorter abaaa
3
Examples of posets that are not wellfounded.
The < relation of Z.
30>28>21>2>-4>......
The < relation of R+
30.2>29.2>20.4>15.8>....>0.004>0.00058>....
4
The minimal Element Property
If A is a well-founded set, then every
subset of A has a minimal element.
Conversely, if every nonempty subset of A
has a minimal element, then A is wellfounded.
5
Lexicograhic or ordering of tuples
The linear ordering < on N can be used to
create the lexicographic order on Nk, which
is defined as follows.
(𝑥1 , … , 𝑥𝑛 ) ≺ (𝑦1 , … , 𝑦𝑛 )
if and only if there is an index 𝑗 ≥ 1 such that
𝑥𝑗 < 𝑦𝑗 and for each 𝑖 < 𝑗, 𝑥𝑖 = 𝑦𝑖 . This
ordering is a total ordering on Nk. It is also
well-ordering.
6
Example
For each set S, show that the given partial
order on S is well-founded.
1. Let S be a set of trees. Let 𝑠 ≺ 𝑡 means that s
has fewer nodes.
2. Let S be a set of trees. Let 𝑠 ≺ 𝑡 means that s
has fewer leaves than t.
7
Solution
1. Consider an arbitrary binary tree with n
nodes. A descending chain starting from
the tree cannot have more than n+1
elements. Therefore the descending
chain must be finite. Therefore the poset
is well-founded.
8
Solution
2. Consider an arbitrary binary tree with n
nodes. A descending chain starting from
the tree cannot have more than n+1
elements. Therefore the descending
chain must be finite. Therefore the poset
is well-founded.
9
Example
Suppose we define the relation ≺ on NN as
follows:
(𝑎, 𝑏) ≺ 𝑐, 𝑑 iff max 𝑎, 𝑏 < max{𝑐, 𝑑}
Is NN well-founded with respect to ≺?
10
Solution
Yes, it is well-founded.
For any (𝑎, 𝑏) ∈ 𝑁 × 𝑁, any descending
chain can only contain at most max 𝑎, 𝑏 + 1
elements, hence it is finite. Therefore the
poset is well-founded.
11
Chapter 5 Analysis Techniques
We need to see if an algorithm is efficient
or not.
Least time and least space. Which one is
more important? Generally, time is a more
important factor because you can buy
space but not time.
12
Worst-case running time
 The running time is measured by counting the
number of operations instead of doing the real
timing during the execution of a program.
 The number of operations performed by an
algorithm usually depends on the size or
structure of the input.
 Some algorithm also depends on the structure of
the input. For example some sorting algorithms
perform poorly when the original list is already
sorted.
13
Worst-case running time
 An input of size n is a worst-case input if, when
compared to all other inputs of size n, it causes
an algorithm A to execute the largest number of
operations.
 For any input I we'll denote its size by size(I),
and we'll let time(I) denote the number of
operations executed by A on I. Then, the worstcase function for A is defined as follows:
WA(n)=max{time(I)|I is an input and size(I)=n}
14
Optimal in the worst case
An algorithm A is optimal in the worst case
for problem P, if for any algorithm B that
exits, or ever will exist, the following
relationship holds:
WA(n)WB(n) for all n>0
15
Steps to find an algorithm that is
optimal
(Find an algorithm) Find or design an
algorithm A to solve P. Then do an
analysis of A to find the worst-case
function WA.
(Find a lower bound) Find a function F
such that F(n)WB for all n>0 and for all
alogrithms B that solve P.
Compare F and WA. If F= WA, then A is
optimal in the worst case.
16
Steps to find an algorithm that is
optimal
Suppose we know that FWA. This means
that F(n)<WA(n) for some n. In this case
there are two possible courses of action to
consider:
Try to build a new algorithm C such that
WC(n)WA(n) for all n>0
Try to find a new function G such that F(n) G(n)
WB(n) for all n>0 and for all algorithms B that
solve P.
17
Matrix Multiplication
𝑒 𝑓
𝑎 𝑏
𝐴=
,𝐵=
𝑔 ℎ
𝑐 𝑑
The product 𝐴 𝐵 is the following 2 by 2
matrix:
𝑎𝑒 + 𝑏𝑔 𝑎𝑓 + 𝑏ℎ
𝐴𝐵 =
𝑐𝑒 + 𝑑𝑔 𝑐𝑓 + 𝑑ℎ
18
Matrix Multiplication
if two nn matrices are multiplied together,
𝑛3 multiplications and 𝑛2 (𝑛 − 1) additions
are needed. However, there are special
algorithm that can be reduced the number of
multiplication.
19
Matrix Multiplication
𝑐11
𝑐21
𝐶 = 𝐴𝐵
𝑐12 𝑎11 𝑎12 𝑏11 𝑏12
=
𝑐22 𝑎21 𝑎22 𝑏21 𝑏22
𝑄1 = 𝑎11 + 𝑎22 𝑏11 + 𝑏22
𝑄2 = 𝑎21 + 𝑎11 𝑏11
𝑄3 = 𝑎11 𝑏12 − 𝑏22
𝑄4 = 𝑎22 −𝑏11 + 𝑏21
𝑄5 = 𝑎11 + 𝑎12 𝑏22
𝑄6 = −𝑎11 + 𝑎21 𝑏11 + 𝑏12
𝑄7 = (𝑎12 − 𝑎22 )(𝑏21 + 𝑏22 )
20
Matrix Multiplication
Then the matrix product is given using the
remaining eight additions as
𝑐11 = 𝑄1 + 𝑄4 − 𝑄5 + 𝑄7
𝑐21 = 𝑄2 + 𝑄4
𝑐12 = 𝑄3 + 𝑄5
𝑐22 = 𝑄1 + 𝑄3 − 𝑄2 + 𝑄6
21
 In the last method, only 7 multiplications are
needed.
 Multiplication of larger-size matrices is broken
down into multiplying many 2 by 2 matrices. So
the number of multiplication operations becomes
less than n3.
 The known lower bound for the number of
multiplication operations needed to multiply two
n by n matrices is n2.
 Strassen showed how to multiply two matrices
with n2.81 multiplications. The number 2.81 is
related to log27.
22
Finding the minimum
 Problem: to find the minimum number in an
unsorted list of a numbers.
 We'll count the number of comparison
operations that an algorithm makes between
elements of the list.
 To find the minimum number in a list of n
numbers, the minimum number must be
compared with the other n-1 numbers.
Therefore, n-1 is a lower bound on the number
of comparisons needed to find the minimum
number in a list of n numbers.
23
Finding the minimum
The following algorithm is optimal because
the operation  is executed exactly n-1
times.
m:=a[1];
for i:=2 to n do
m:=if ma[i] then m else a[i]
od
24
Decision trees
A decision tree for an algorithm is a tree
whose nodes represent decision points in
the algorithm and whose leaves represent
possible outcomes.
Decision trees can be useful in trying to
construct an algorithm or trying to find
properties of a decision tree.
25
Decision trees
If an algorithm makes decisions based on
the comparison of two objects, then it can
be represented by a binary decision tree.
Each nonleaf node in the tree represents a
pair of objects to be compared by the
algorithm, and each branch from that
node represents a path taken by the
algorithm based on the comparison. Each
leaf can represent an outcome of the
algorithm.
26
Lower bounds for decision tree
algorithms
 Suppose that a problem has n possible
outcomes and it can be solved by a binary
decision tree algorithm. What is the best binary
decision tree algorithm? We may not know the
answer, but we can find a lower bound for the
depth of any binary decision tree to solve the
problem. Since the program has n possible
outcomes, it follows that any binary decision tree
algorithm to solve the problem must have at
least n leaves, one for each of the n possible
outcomes. Recall that the number of leaves in a
binary tree of depth d is at most 2d.
27
Lower bounds for decision tree
algorithms
So if d is the depth of a binary decision
tree to solve a problem with n possible
outcomes, then we must have n2d. We
can solve this inequality for d by taking
log2 of both sides to obtain log2n d. Since
d is a natural number, it follows that
log2nd
28
Ternary decision tree
We can do the same analysis for ternary
decision trees. The number of leaves in a
ternary tree of depth d is at most 3d. If d is
the depth of a ternary decision tree to
solve a problem with n possible outcomes,
then we must have n3d. Or:
log3nd
29
Binary Search
 Suppose we search a sorted list in a binary
fashion. That is, we check the middle element of
the list to see whether it's the key we are looking
for. If not, then we perform the same operation
on either the left half or the right half of the list,
depending on the value of the key. This
algorithm has a nice representation as a
decision tree. For example, suppose we have
the following sorted list of 15 numbers:
x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14,
x15,
30
Decision tree for binary search
x8
s
x4
s
x2
x1
s
x3
x5
x12
x6
x10
s
s
x7
x9
s
x11
x14
x13
s
x15
us u us u us u us u us u us u us u us u
31
Binary search
 Suppose we're given a number key K, and we
must find whether it is in the list. The decision
tree for a binary search of the list has the
number x8 at its root. This represents the
comparison of K with x8. If K=x8, then we are
successful in one comparison. If K<x8, then we
go to the left child of x8; otherwise we go to the
right child of x8. The result is a ternary decision
tree in which the leaves are labeled with either S,
for successful search, or U, for unsuccessful
search.
32
Binary search
 Since the depth of the tree is 4, it follows that
there will be four comparisons in the worst case
to find whether K is in the list. Is this an optimal
algorithm? To see that the answer is yes, we
can observe that there are 31 possible
outcomes for the given program: 15 leaves
labeled with S to represent successful searches;
and 16 leaves labeled with U to represent the
gaps where K<x1, xi<K<xi+1 for 1i<15, and
x15<K. Therefore, a worst-case lower bound for
the number of comparisons is log331=4.
Therefore the hyphen algorithm is optimal.
33
Examples
A solution to a problem has x possible
outcomes. An algorithm to solve the
problem has a binary decision tree of
depth 5.
Draw a picture of the decision tree for an
optimal algorithm to find the maximum
number in the list x1, x2, x3 and x4.
34
Finding a bad coin
Suppose we are asked to use a pan
balance to find the heavy coin among
eight coins with the assumption that they
all look alike and the other seven all have
the same weight. One way to proceed is to
always place coins in the two pans that
include the bad coin, so the pan will
always go down.
35
This gives a binary decision tree, where
each internal node of the tree represents
the pan balance. If the left side goes down,
then the heavy coin is on the left side of
the balance. Otherwise, the heavy coin is
on the right side of the balance. Each leaf
represents one coin that is the heavy coin.
Suppose we label the coins with the
numbers 1, 2,..., 8.
36
The decision tree for one algorithm is
shown in Figure 5.2, where the numbers
on either side of a nonleaf node represent
the coins on either side of the pan balance.
This algorithm finds the heavy coin in
three weighings. Can we do any better?
Look at the next example.
37
An Optimal Solution
We are asked to use a pan balance to find
the heavy coin among eight coins with the
assumption that they all look alike and the
other seven all have the same weight. In
this case we'll weigh coins with the
possibility that the two pans are balanced.
So a decision tree can have nodes with
three children.
38
We don't have to use all eight coins on the
first weighing. For example, the above
shows the decision tree for one algorithm.
Notice that there is no middle branch on
the middle subtree because, at this point,
one of the coins 7 or 8 must be the heavy
one. This algorithm finds the heavy coin in
two weighings.
39
This algorithm is an optimal pan-balance
algorithm for the problem, where we are
counting the number of weighings to find
the heavy coin. To see this, notice that any
one of the eight coins could be the heavy
one. Therefore, there must be at least
eight leaves on any algorithm's decision
tree.
40
But a binary tree of depth d can have 2d
possible leaves. So to get eight leaves, we
must have 2d ≥ 8. This implies that d ≥ 3.
But a ternary tree of depth d can have 3d
possible leaves. So to get eight leaves, we
must have 3d ≥ 8, or d ≥ 2. Therefore, 2 is
a lower bound for the number of weighings.
Since the algorithm solves the problem in
two weighings, it is optimal.
41
A Lower Bound Computation
Suppose we have a set of 13 coins in
which at most one coin is bad and a bad
coin may be heavier or lighter than the
other coins. The problem is to use a pan
balance to find the bad coin if it exists and
say whether it is heavy or light. We'll find a
lower bound on the heights of decision
trees for pan-balance algorithms to solve
the problem.
42
Any solution must tell whether a bad coin
is heavy or light. Thus there are 27
possible conditions: no bad coin and the
13 pairs of conditions (ith coin light, ith
coin heavy). Therefore, any decision tree
for the problem must have at least 27
leaves. So a ternary decision tree of depth
d must satisfy 3d ≥ 27, or d ≥ 3. This gives
us a lower bound of 3.
43
Now the big question: Is there an
algorithm to solve the problem, where the
decision tree of the algorithm has depth 3?
The answer is no. Just look at the cases of
different initial weighings, and note in each
case that the remaining possible
conditions cannot be distinguished with
just two more weighings. Thus any
decision tree for this problem must have
depth 4 or more.
44
5.2 Finding Closed Forms
A closed from is an expression that can be
computed by applying a fixed number of
familiar operations to the arguments. A
closed form can't have an ellipsis because
the number of operations to evaluate the
form would not be fixed. For example, the
expression n(n+1)/2 is a closed form, but
the expression 1+2+...+n is not a closed
form.
45
Closed Forms of Elementary Finite
Sums
𝑎1 , 𝑎2 ,... ,𝑎𝑛 form an AP series, then
𝑛(𝑎1 +𝑎𝑛 )
𝑎1 + 𝑎2 +... +𝑎𝑛 =
2
𝑎 + 𝑎𝑟 + 𝑎𝑟 2 + ⋯ + 𝑎𝑟 𝑛−1 =
𝑎(1−𝑟 𝑛 )
1−𝑟
if a,b,....,x form an AP with common
difference, then the number of terms in the
𝑥−𝑎
AP is:
+1
𝑑
46
Examples
Evaluate each of the followings:
1. 4+7+10+...40
2. 5+10+20+40+..+160
47
Solution
1.
13(40+4)
2
2.
5(26 −1)
2−1
48
Examples
Find a closed form for each of the
following sums.
1. 2+4+6+...+2n
2. 2+7+12+...+(5n+2)
3. 2+6+...+2(3n).
49
Solution
1. n(n+1)
2.
(5𝑛+4)(𝑛+1)
2
𝑛+1
3. 3
−1
50
Simple sort
a[i], i=1,...,n are n numbers.
We want to sort these numbers in
ascending order.
min(a,i,n) is the index of the minimum
number among the elements of a[i],..a[n].
exchange(a[i],a[j]) is the usual operation of
swapping elements and does not use any
comparison.
51
Simple sort
 The algorithm
for i:=1 to n-1 do
j:=min(a,i,n);
exchange(a[i],a[j])
od
 The algorithm makes n-1 comparison in the first
round, then n-2 comparison in the second
round,...
 So the total number of comparisons made is:
(n-1)+(n-2)+....1=n(n-1)/2
52
Simple sort
Exactly n(n-1)/2 comparisons are made for
all inputs. So every set of input
corresponds to the worst case.
53
Example
 For the following algorithm, answer each
question by giving a formula in terms of n:
for i:=1 to n do
for j:=1 to i do x:=x+f(x) od;
x:=x+g(x)
od
Find the number of times the assignment statement (:=)
is executed during the running of the program.
54
Solution
1
2
3
1+1 2+1+2 3+1+2+3
…
𝑛
𝑛 + 1 + 2+. . +𝑛
𝑛(𝑛 + 3)
2
55
Example
 For the following algorithm, answer each
question by giving a formula in terms of n:
i:=1;
while i<n+1 do
i:=i+2;
for j:=1 to i do S od
od
Find the number of times the statement S is executed
during the running of the program.
56
Solution
𝑛 1 2
3
4
5
𝑆 3 3 3+5 3+5 3+5+7
When n is odd, the answer is:
(𝑛+5)(𝑛+1)
3+5+7+...+(n+2)=
4
When n is even, the answer is:
𝑛(𝑛+4)
3+5+7+...+(n+1)=
4
57
Example
Find a closed form, in terms of n, for the
number of times S is executed in the
following algorithm:
for i:=1 to n do
for j:=i to n do
S
od
od
58
Solution
𝑛
𝑆
1
2
..
𝑛
1 2 + 1 .. 𝑛 + 𝑛 − 1 + ⋯+ 1
𝑛(𝑛 + 1)
2
59
Example
Find the exact number of times, in terms of
the natural number n, that S is executed in
the following algorithm:
i:=0;
while i<n do
S;
i:=i+2
od
60
Solution
𝑛
𝑆
1 2 3 4 …
1 1 2 2 …
𝑛
2
61