程序代写代做代考 information theory algorithm decision tree PowerPoint Presentation

PowerPoint Presentation

Lower Bounds
& Models of Computation
Jeff Edmonds
York University

COSC 3101
Lecture 8
Thinking about Algorithms Abstractly

1

Lower Bounds for Sorting using Information Theory

2

The Time Complexity of a Problem P
Merge, Quick, and Heap Sort can sort N numbers
using O(N log N) comparisons between the values.
Theorem: No algorithm can sort faster.
The Time Complexity of a Problem P:
The minimum time needed
by an algorithm to solve it.

3

The Time Complexity of a Problem P
The minimum time needed by an algorithm to solve it.

Problem P is computable in time Tupper(n)
if there is an algorithm A which
outputs the correct answer
in this much time
Eg: Sorting computable in Tupper(n) = O(n2) time.
$ A, ” I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
Upper Bound:

4

Understand Quantifiers!!!
One girl
Could be a separate girl for each boy.
Sam Mary
Bob Beth
John Marilin Monro
Fred Ann

Sam Mary
Bob Beth
John Marilin Monro
Fred Ann

Algorithm
Input
$ A, ” I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)

5

The Time Complexity of a Problem P
The minimum time needed by an algorithm to solve it.
$ A, ” I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
” I, $ A, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
What does this say?
True for any problem P and time Tupper.
Given fixed I. Its output is P(I).
Let AP(I) be the algorithm that outputs the string P(I).

6

The Time Complexity of a Problem P
The minimum time needed by an algorithm to solve it.

Time Tlower(n) is a lower bound for problem p
if no algorithm solve the problem faster.
There may be algorithms that give the correct answer
or run quickly on some inputs instance.
Lower Bound:

7

The Time Complexity of a Problem P
The minimum time needed by an algorithm to solve it.
Lower Bound:
Time Tlower(n) is a lower bound for problem p
if no algorithm solve the problem faster.
Eg: No algorithm can sort N values
in Tlower = sqrt(N) time.
But for every algorithm, there is at least one instance I for which either the algorithm gives the wrong answer or it runs in too much time.
” A, $ I, A(I) = P(I) or Time(A,I) ³ Tlower(|I|)

8

Understand Quantifiers!!!
One girl
Could be a separate girl for each boy.
Sam Mary
Bob Beth
John Marilin Monro
Fred Ann

Sam Mary
Bob Beth
John Marilin Monro
Fred Ann

Algorithm
Input
” A, $ I, A(I) = P(I) or Time(A,I) ³ Tlower(|I|)

9

$ A, ” I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
” A, $ I, A(I) ≠ P(I) or Time(A,I) ³ Tlower(|I|)
Lower Bound:
Upper Bound:
The Time Complexity of a Problem P
The minimum time needed by an algorithm to solve it.
“There is” and “there isn’t a faster algorithm”
are almost negations of each other.

10

$ A, ” I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
Upper Bound:
Prover-Adversary Game

I have an algorithm A that I claim works and is fast.
I win if A on input I gives
the correct output
in the allotted time.
Oh yeah, I have an input I for which it does not.
What we have been doing all along.

11

Lower Bound:
Prover-Adversary Game

I win if A on input I gives
the wrong output or
runs slow.
” A, $ I, [ A(I) = P(I) or Time(A,I) ³ Tlower(|I|)]

Proof by contradiction.
I have an algorithm A that I claim works and is fast.
Oh yeah, I have an input I for which it does not .

12

Lower Bound:
Prover-Adversary Game

” A, $ I, [ A(I) = P(I) or Time(A,I) ³ Tlower(|I|)]

I have an algorithm A that I claim works and is fast.
Lower bounds are very hard to prove, because I must consider every algorithm
no matter how strange.

13

The Yes/No Questions Game

I choose a number Î[1..N].
I ask you yes/no questions.
Time is the number of questions
asked in the worst case.
I answer.
I determine the number.

14

The Yes/No Questions Game
Upper Bound

6

Great!

15

The Yes/No Questions Game
Upper Bound
Time

N leaves
= # of questions
= height
= log2(N)

16

The Yes/No Questions Game
Lower Bound?
Time

N leaves
Is there a faster
algorithm?

Is the third bit 1?
If different
questions?

= # of questions
= height
= log2(N)

17

The Yes/No Questions Game
Lower Bound?

N leaves
Is there a faster
algorithm?

If it has a different
structure?

Best case
Worst case
Time
= # of questions
= height
= log2(N)

18

The Yes/No Questions Game
Lower Bound
Theorem: For every question strategy A,
with the worst case object I to ask about,
log2 N questions need to be asked
to determine one of N objects.
” A, $ I, A(I) = P(I) or Time(A,I) ³ log2 N

Proof: Prover/Adversary Game

19

Lower Bound Proof
Oh yeah, I have an input I for which it does not.

I have an algorithm A that
I claim works and is fast.
Two cases:
# output leaves < N # output leaves ³ N 20 I have an algorithm A that I claim works and is fast. Man your algorithm does not have N output leaves. I win if A on input I gives the wrong output or requires log N questions. Lower Bound Proof: case 1 I give a input I = 4 with missing output. 21 Good now your algorithm has all N outputs as leaves. It must have height ³ log N. I win if A on input I gives the wrong output or requires log N questions. I have an algorithm A that I claim works and is fast. I give a input I = 5 at a deep leaf. Lower Bound Proof: case 2 22 The Yes/No Questions Game Lower Bound Theorem: For every question strategy A, with the worst case object I to ask about, log2 N questions need to be asked to determine one of N objects. " A, $ I, A(I) = P(I) or Time(A,I) ³ log2 N Proof: Prover/Adversary Game End of Proof. 23 Communication Complexity Or a obj Îa set of N objs. Time is the number of bits sent in the worst case. I send you a stream of bits. I determine the object. I choose a number Î[1..N]. 24 Communication Complexity Upper Bound 6 Great! 25 Communication Complexity Lower Bound Theorem: For every communication strategy A, with the worst case object I to communicate, log2 N bits need to transmitted to communicate one of N objects. " A, $ I, A(I) = P(I) or Time(A,I) ³ log2 N 26 The Sorting Game I choose a permutation of {1,2,3,…,N}. I ask you yes/no questions. Time is the number of questions asked in the worst case. I answer. I determine the permuation. 27 Sorting Upper Bound b,c,a Great! 28 Time N! leaves = # of questions = height = log2(N!) Sorting Upper Bound 29 N! = 1 × 2 × 3 × … × N/2 × … × N N factors each at most N. N/2 factors each at least N/2. £ NN N/2 £ N/2 Bounding log(N!) N/2 log(N/2) £ log(N!) £ N log(N) = Q(N log(N)). 30 Time N! leaves = # of questions = height = log2(N!) = Q(N log(N)). Is there a faster algorithm? Is the third bit of c 1? If different questions? Sorting Lower Bound 31 class InsertionSortAlgorithm { for (int i = 1; i < a.length; i++) { int j = i; while ((j > 0) && (a[j-1] > a[i])) {
a[j] = a[j-1];
j–; }
a[j] = B; }}
Is there a faster algorithm?
If different model of computation?
Sorting
Lower Bound

32

Sorting
Lower Bound
Theorem: For every sorting algorithm A,
with the worst case input instance I,
Q(N log2 N) comparisons (or other bit operations)
need to be executed to sort N objects.
” A, $ I, A(I) = P(I) or Time(A,I) ³ N log2 N

Proof: Prover/Adversary Game

33

Lower Bound Proof
Oh yeah, I will find an input I
for which it does not.

I have an algorithm A that I claim works and is fast.

class InsertionSortAlgorithm {
for (int i = 1; i < a.length; i++) { int j = i; while ((j > 0) && (a[j-1] > a[i])) {
a[j] = a[j-1];
j–; }
a[j] = B; }}

34

Lower Bound Proof
I have an algorithm A that I claim works and is fast.

class InsertionSortAlgorithm {
for (int i = 1; i < a.length; i++) { int j = i; while ((j > 0) && (a[j-1] > a[i])) {
a[j] = a[j-1];
j–; }
a[j] = B; }}
But first let me translate your algorithm into a decision tree.

35

I choose a permutation of {1,2,3,…,N}.

I answer.
I determine the permuation.

class InsertionSortAlgorithm {
for (int i = 1; i < a.length; i++) { int j = i; while ((j > 0) && (a[j-1] > a[i])) {
a[j] = a[j-1];
j–; }
a[j] = B; }}
I ask you this yes/no question.
I run my algorithm until
I need to know something about the input permutation.

Lower Bound Proof

36

class InsertionSortAlgorithm {
for (int i = 1; i < a.length; i++) { int j = i; while ((j > 0) && (a[j-1] > a[i])) {
a[j] = a[j-1];
j–; }
a[j] = B; }}

Lower Bound Proof

37

Lower Bound Proof
Oh yeah, I have an input I for which it does not.

I have an algorithm A that
I claim works and is fast.
Two cases:
# output leaves < N! # output leaves ³ N! 38 I have an algorithm A that I claim works and is fast. Man your algorithm does not have N! output leaves. I win if A on input I gives the wrong output or requires log N questions. Lower Bound Proof: case 1 I give a input I =
with missing output.

39

Good now your algorithm
has all N! outputs as leaves.

It must have height ³ log N!.

I win if A on input I gives
the wrong output or
requires log N! questions.
I have an algorithm A that I claim works and is fast.

Lower Bound Proof: case 2

I give a input I = at a deep leaf.

= Q(N log(N)).

40

Sorting
Lower Bound
Theorem: For every sorting algorithm A,
on the worst case input instance I,
Q(N log2 N) comparisons (or other bit operations)
need to be executed to sort N objects.
” A, $ I, A(I) = P(I) or Time(A,I) ³ N log2 N

Proof: Prover/Adversary Game
End of Proof.

41

End

42

$

g
b
loves
b
g
,
,
(
,
)


$
b
g
loves
b
g
,
,
(
,
)

/docProps/thumbnail.jpeg