Greedy algorithms
G
r
e
e
d
y
a
l
g
o
r
i
t
h
m
s
David Kauchak
cs140
Spring 2024
A
d
m
i
n
i
s
t
r
a
t
i
v
e
Assignment 6
Grades
Dr. Dave’s grades
G
r
e
e
d
y
a
l
g
o
r
i
t
h
m
s
Algorithm that makes a local decision with the goal of
creating a globally optimal solution
Method for solving problems where optimal solutions can
be defined in terms of optimal solutions to sub-problems
G
r
e
e
d
y
Greedy
To solve the general problem:
Pick a locally optimal solution and repeat
H
o
r
n
f
o
r
m
u
l
a
A horn formula is a
set of implications and
negative clauses
:
H
o
r
n
f
o
r
m
u
l
a
A
h
o
r
n
f
o
r
m
u
l
a
i
s
a
s
e
t
o
f
i
m
p
l
i
c
a
t
i
o
n
s
a
n
d
n
e
g
a
t
i
v
e
c
l
a
u
s
e
s
:
LHS: positive literals anded
RHS: single positive literal
T
T
F
F
T
F
T
F
T
F
T
T
H
o
r
n
f
o
r
m
u
l
a
A
h
o
r
n
f
o
r
m
u
l
a
i
s
a
s
e
t
o
f
i
m
p
l
i
c
a
t
i
o
n
s
a
n
d
n
e
g
a
t
i
v
e
c
l
a
u
s
e
s
:
Negated literals ored
G
o
a
l
Given a horn formula, determine if the formula is
satisfiable, i.e. an assignment of true/false to the variables
that is consistent with all of the implications/causes
u x y z
0 1 1 0
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
?
w 0
x 0
y 0
z 0
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
?
w 0
x
1
y 0
z 0
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
?
w 0
x 1
y
1
z 0
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
?
w
1
x 1
y 1
z 0
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
?
w 1
x 1
y 1
z 0
not satisfiable
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
set all variables of
the implications of
the form
“
x
”
to
true
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
if the all variables of
the lhs of an
implication are true,
then set the rhs
variable to true
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
see if all of the
negative clauses are
satisfied
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
How is this a greedy algorithm?
A
g
r
e
e
d
y
s
o
l
u
t
i
o
n
How is this a greedy algorithm?
Make a greedy decision about
which variables to set and then
moves on
C
o
r
r
e
c
t
n
e
s
s
o
f
g
r
e
e
d
y
s
o
l
u
t
i
o
n
Two parts:
If our algorithm returns an assignment, is it a valid
assignment?
If our algorithm does not return an assignment,
does an assignment exist?
C
o
r
r
e
c
t
n
e
s
s
o
f
g
r
e
e
d
y
s
o
l
u
t
i
o
n
If our algorithm returns an assignment, is it a valid
assignment?
C
o
r
r
e
c
t
n
e
s
s
o
f
g
r
e
e
d
y
s
o
l
u
t
i
o
n
If our algorithm returns an assignment, is it a valid
assignment?
explicitly check all
negative clauses
C
o
r
r
e
c
t
n
e
s
s
o
f
g
r
e
e
d
y
s
o
l
u
t
i
o
n
If our algorithm returns an assignment, is it a valid
assignment?
don’
t stop until all
implications with all
lhs elements true
have rhs true
C
o
r
r
e
c
t
n
e
s
s
o
f
g
r
e
e
d
y
s
o
l
u
t
i
o
n
If our algorithm does not return an
assignment, does an assignment exist?
O
u
r
a
l
g
o
r
i
t
h
m
i
s
“
s
t
i
n
g
y
”
.
I
t
o
n
l
y
s
e
t
s
t
h
o
s
e
v
a
r
i
a
b
l
e
s
t
h
a
t
h
a
v
e
t
o
b
e
t
r
u
e
.
A
l
l
o
t
h
e
r
s
r
e
m
a
i
n
f
a
l
s
e
.
C
o
r
r
e
c
t
n
e
s
s
o
f
g
r
e
e
d
y
s
o
l
u
t
i
o
n
If our algorithm does not return an
assignment, does an assignment exist?
R
u
n
n
i
n
g
t
i
m
e
?
?
n = number of
variables
m = number of
formulas
R
u
n
n
i
n
g
t
i
m
e
?
O(nm)
n = number of
variables
m = number of
formulas
D
a
t
a
c
o
m
p
r
e
s
s
i
o
n
Given a file containing some data of a fixed alphabet
Σ
(e.g. A, B, C, D), we would like to pick a binary
character code that minimizes the number of bits
required to represent the data.
minimize the size of
the encoded file
C
o
m
p
r
e
s
s
i
o
n
a
l
g
o
r
i
t
h
m
s
http://en.wikipedia.org/wiki/Lossless_data_compression
S
i
m
p
l
i
f
y
i
n
g
a
s
s
u
m
p
t
i
o
n
:
f
r
e
q
u
e
n
c
y
o
n
l
y
Assume that we only have character
frequency information for a file
=
F
i
x
e
d
l
e
n
g
t
h
c
o
d
e
A =
B =
C =
D =
F
i
x
e
d
l
e
n
g
t
h
c
o
d
e
A = 00
B = 01
C = 10
D = 11
How many bits to
encode the file?
2 x 70 +
2 x 3 +
2 x 20 +
2 x 37 =
260 bits
F
i
x
e
d
l
e
n
g
t
h
c
o
d
e
A = 00
B = 01
C = 10
D = 11
Can we do better?
2 x 70 +
2 x 3 +
2 x 20 +
2 x 37 =
260 bits
V
a
r
i
a
b
l
e
l
e
n
g
t
h
c
o
d
e
What about:
A = 0
B = 01
C = 10
D = 1
1 x 70 +
2 x 3 +
2 x 20 +
1 x 37 =
153 bits
How many bits to
encode the file?
D
e
c
o
d
i
n
g
a
f
i
l
e
A = 0
B = 01
C = 10
D = 1
010100011010
What characters does this
sequence represent?
D
e
c
o
d
i
n
g
a
f
i
l
e
A = 0
B = 01
C = 10
D = 1
010100011010
What characters does this
sequence represent?
A
D
o
r
B
?
V
a
r
i
a
b
l
e
l
e
n
g
t
h
c
o
d
e
What about:
A = 0
B = 100
C = 101
D = 11
Is it decodeable?
V
a
r
i
a
b
l
e
l
e
n
g
t
h
c
o
d
e
What about:
A = 0
B = 100
C = 101
D = 11
How many bits to
encode the file?
1 x 70 +
3 x 3 +
3 x 20 +
2 x 37 =
213 bits
(18% reduction)
P
r
e
f
i
x
c
o
d
e
s
A
p
r
e
f
i
x
c
o
d
e
i
s
a
s
e
t
o
f
c
o
d
e
s
w
h
e
r
e
n
o
c
o
d
e
w
o
r
d
i
s
a
p
r
e
f
i
x
o
f
a
n
y
o
t
h
e
r
c
o
d
e
w
o
r
d
A = 0
B = 100
C = 101
D = 11
A = 0
B = 01
C = 10
D = 1
P
r
e
f
i
x
t
r
e
e
W
e
c
a
n
e
n
c
o
d
e
a
p
r
e
f
i
x
c
o
d
e
u
s
i
n
g
a
f
u
l
l
b
i
n
a
r
y
t
r
e
e
w
h
e
r
e
e
a
c
h
l
e
a
f
r
e
p
r
e
s
e
n
t
s
a
n
e
n
c
o
d
i
n
g
o
f
a
s
y
m
b
o
l
A = 0
B = 100
C = 101
D = 11
0
1
D
e
c
o
d
i
n
g
u
s
i
n
g
a
p
r
e
f
i
x
t
r
e
e
To decode, we traverse the graph until a leaf
node is reached and output the symbol
A = 0
B = 100
C = 101
D = 11
0
1
D
e
c
o
d
i
n
g
u
s
i
n
g
a
p
r
e
f
i
x
t
r
e
e
Traverse the graph until a leaf node is reached
and output the symbol
0
1
1000111010100
D
e
c
o
d
i
n
g
u
s
i
n
g
a
p
r
e
f
i
x
t
r
e
e
Traverse the graph until a leaf node is reached
and output the symbol
0
1
1000111010100
B
D
e
c
o
d
i
n
g
u
s
i
n
g
a
p
r
e
f
i
x
t
r
e
e
Traverse the graph until a leaf node is reached
and output the symbol
0
1
1000111010100
B
A
D
e
c
o
d
i
n
g
u
s
i
n
g
a
p
r
e
f
i
x
t
r
e
e
Traverse the graph until a leaf node is reached
and output the symbol
0
1
1000111010100
B A
D
D
e
c
o
d
i
n
g
u
s
i
n
g
a
p
r
e
f
i
x
t
r
e
e
Traverse the graph until a leaf node is reached
and output the symbol
0
1
1000111010100
B A D
C
D
e
c
o
d
i
n
g
u
s
i
n
g
a
p
r
e
f
i
x
t
r
e
e
Traverse the graph until a leaf node is reached
and output the symbol
0
1
1000111010100
B A D
C
A
D
e
c
o
d
i
n
g
u
s
i
n
g
a
p
r
e
f
i
x
t
r
e
e
Traverse the graph until a leaf node is reached
and output the symbol
0
1
1000111010100
B A D
C A
B
D
e
t
e
r
m
i
n
i
n
g
t
h
e
c
o
s
t
o
f
a
f
i
l
e
0
1
D
e
t
e
r
m
i
n
i
n
g
t
h
e
c
o
s
t
o
f
a
f
i
l
e
0
1
70
3
20
37
D
e
t
e
r
m
i
n
i
n
g
t
h
e
c
o
s
t
o
f
a
f
i
l
e
0
1
70
3
20
37
23
60
If we label the internal nodes with
the sum of the children…
D
e
t
e
r
m
i
n
i
n
g
t
h
e
c
o
s
t
o
f
a
f
i
l
e
0
1
70
3
20
37
23
60
Cost is equal to the sum of the
internal nodes (excluding the root)
and the leaf nodes
D
e
t
e
r
m
i
n
i
n
g
t
h
e
c
o
s
t
o
f
a
f
i
l
e
0
1
70
3
20
37
23
60
60 times we see a prefix that
starts with a 1
of those, 37 times we see an
additional 1
the remaining 23 times we see
an additional 0
70 times we see a 0 by itself
of these, 20 times we see a last 1
and 3 times a last 0
As we move down the tree, one bit
gets read for every nonroot node
A
g
r
e
e
d
y
a
l
g
o
r
i
t
h
m
?
Given file frequencies, can we come up with a prefix-
free encoding (i.e. build a prefix tree) that minimizes
the number of bits?
0
1
Where should the highest frequency items be?
A
g
r
e
e
d
y
a
l
g
o
r
i
t
h
m
?
Given file frequencies, can we come up with a prefix-
free encoding (i.e. build a prefix tree) that minimizes
the number of bits?
Heap
Heap
B
3
C
20
D
37
A
70
Heap
BC
23
D
37
A
70
3
20
23
merging with this
node will incur an
additional cost of 23
Heap
BCD
60
A
70
3
20
23
37
60
Heap
ABCD 130
3
20
23
37
60
70
3
20
23
37
60
70
What is the code
(assume left = 0)?
What is the code
(assume left = 0)?
3
20
23
37
60
70
A: 1
B: 000
C: 001
D: 01
P
r
o
v
i
n
g
c
o
r
r
e
c
t
n
e
s
s
The algorithm selects the symbols with the two
smallest frequencies first (call them f
1
and f
2
)
P
r
o
v
i
n
g
c
o
r
r
e
c
t
n
e
s
s
:
p
r
o
o
f
b
y
c
o
n
t
r
a
d
i
c
t
i
o
n
The algorithm selects the symbols with the two smallest
frequencies first (call them f
1
and f
2
)
Consider a tree that did not do this:
f
1
f
i
f
2
Is it optimal?
P
r
o
v
i
n
g
c
o
r
r
e
c
t
n
e
s
s
The algorithm selects the symbols with the two smallest
frequencies first (call them f
1
and f
2
)
Consider a tree that did not do this:
f
1
f
i
f
2
f
i
f
1
f
2
-
f
r
e
q
u
e
n
c
i
e
s
d
o
n
’
t
c
h
a
n
g
e
-
c
o
s
t
w
i
l
l
d
e
c
r
e
a
s
e
s
i
n
c
e
f
1
<
f
i
contradiction
f
1
f
i
f
2
d
1
d
2
f
i
f
1
f
2
d
1
d
2
R
u
n
t
i
m
e
?
1 call to MakeHeap
2(n-1) calls ExtractMin
n-1 calls Insert
O(n log n)
N
o
n
-
o
p
t
i
m
a
l
g
r
e
e
d
y
a
l
g
o
r
i
t
h
m
s
All the greedy algorithms we’
ve looked at so far
give the optimal answer
Some of the most common greedy algorithms
generate good, but non-optimal solutions
set cover
clustering
hill-climbing
relaxation
Handout
D
e
c
o
d
i
n
g
u
s
i
n
g
a
p
r
e
f
i
x
t
r
e
e
Traverse the graph until a leaf node is reached
and output the symbol
0
1
1000111010100
What is the tree?
What is the encoding?
How many bits to encode the file?
Heap
Greedy algorithms involve making locally optimal decisions to reach a globally optimal solution. Horn formulas consist of implications and negative clauses used to determine satisfiability in logical expressions. Explore the concepts and applications of these mathematical constructs in computer science and logical reasoning.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Greedy algorithms David Kauchak cs140 Spring 2024
Administrative Assignment 6 Grades Dr. Dave s grades
Greedy algorithms Algorithm that makes a local decision with the goal of creating a globally optimal solution Method for solving problems where optimal solutions can be defined in terms of optimal solutions to sub-problems
Greedy Greedy To solve the general problem: Pick a locally optimal solution and repeat
Horn formula A horn formula is a set of implications and negative clauses: x u z x y x y z
Horn formula A horn formula is a set of implications and negative clauses: x u z x y x y z ? ? ? ? LHS: positive literals anded RHS: single positive literal T T F F T F T T T F T F
Horn formula A horn formula is a set of implications and negative clauses: x u z x y x y z Negated literals ored
Goal Given a horn formula, determine if the formula is satisfiable, i.e. an assignment of true/false to the variables that is consistent with all of the implications/causes x u z x y x y z u x y z 0 1 1 0
A greedy solution? y x x w y z x x x z y w w w x y w 0 x 0 y 0 z 0
A greedy solution? y x x w y z x x x z y w w w x y w 0 x 1 y 0 z 0
A greedy solution? y x x w y z x x x z y w w w x y w 0 x 1 y 1 z 0
A greedy solution? y x x w y z x x x z y w w w x y w 1 x 1 y 1 z 0
A greedy solution? y x x w y z x x x z y w w w x y w 1 not satisfiable x 1 y 1 z 0
A greedy solution set all variables of the implications of the form x to true
A greedy solution if the all variables of the lhs of an implication are true, then set the rhs variable to true
A greedy solution see if all of the negative clauses are satisfied
A greedy solution How is this a greedy algorithm?
A greedy solution How is this a greedy algorithm? Make a greedy decision about which variables to set and then moves on
Correctness of greedy solution Two parts: If our algorithm returns an assignment, is it a valid assignment? If our algorithm does not return an assignment, does an assignment exist?
Correctness of greedy solution If our algorithm returns an assignment, is it a valid assignment?
Correctness of greedy solution If our algorithm returns an assignment, is it a valid assignment? explicitly check all negative clauses
Correctness of greedy solution If our algorithm returns an assignment, is it a valid assignment? don t stop until all implications with all lhs elements true have rhs true
Correctness of greedy solution If our algorithm does not return an assignment, does an assignment exist? Our algorithm is stingy . It only sets those variables that have to be true. All others remain false.
Correctness of greedy solution If our algorithm does not return an assignment, does an assignment exist?
Running time? ? n = number of variables m = number of formulas
Running time? O(nm) n = number of variables m = number of formulas
Data compression Given a file containing some data of a fixed alphabet (e.g. A, B, C, D), we would like to pick a binary character code that minimizes the number of bits required to represent the data. minimize the size of the encoded file A C A D A A D B 0010100100100
Compression algorithms http://en.wikipedia.org/wiki/Lossless_data_compression
Simplifying assumption: frequency only Assume that we only have character frequency information for a file Symbol Frequency A B C D A C A D A A D B = 70 3 20 37
Fixed length code Use ???2 bits for each character A = B = C = D =
Fixed length code Use ???2 bits for each character Symbol Frequency A B C D 2 x 70 + 2 x 3 + 2 x 20 + 2 x 37 = A = 00 B = 01 C = 10 D = 11 70 3 20 37 260 bits How many bits to encode the file?
Fixed length code Use ???2 bits for each character Symbol Frequency A B C D 2 x 70 + 2 x 3 + 2 x 20 + 2 x 37 = A = 00 B = 01 C = 10 D = 11 70 3 20 37 260 bits Can we do better?
Variable length code What about: Symbol Frequency A B C D 1 x 70 + 2 x 3 + 2 x 20 + 1 x 37 = A = 0 B = 01 C = 10 D = 1 70 3 20 37 153 bits How many bits to encode the file?
Decoding a file 010100011010 A = 0 B = 01 C = 10 D = 1 What characters does this sequence represent?
Decoding a file 010100011010 A = 0 B = 01 C = 10 D = 1 A D or B? What characters does this sequence represent?
Variable length code What about: Symbol Frequency A B C D A = 0 B = 100 C = 101 D = 11 70 3 20 37 Is it decodeable?
Variable length code What about: Symbol Frequency A B C D 1 x 70 + 3 x 3 + 3 x 20 + 2 x 37 = A = 0 B = 100 C = 101 D = 11 70 3 20 37 213 bits (18% reduction) How many bits to encode the file?
Prefix codes A prefix code is a set of codes where no codeword is a prefix of any other codeword A = 0 B = 01 C = 10 D = 1 A = 0 B = 100 C = 101 D = 11
Prefix tree We can encode a prefix code using a full binary tree where each leaf represents an encoding of a symbol 1 0 A A = 0 B = 100 C = 101 D = 11 D B C
Decoding using a prefix tree To decode, we traverse the graph until a leaf node is reached and output the symbol 1 0 A A = 0 B = 100 C = 101 D = 11 D B C
Decoding using a prefix tree Traverse the graph until a leaf node is reached and output the symbol 1 0 1000111010100 A D B C
Decoding using a prefix tree Traverse the graph until a leaf node is reached and output the symbol 1 0 1000111010100 B A D B C
Decoding using a prefix tree Traverse the graph until a leaf node is reached and output the symbol 1 0 1000111010100 B A A D B C
Decoding using a prefix tree Traverse the graph until a leaf node is reached and output the symbol 1 0 1000111010100 B A D A D B C
Decoding using a prefix tree Traverse the graph until a leaf node is reached and output the symbol 1 0 1000111010100 B A D C A D B C
Decoding using a prefix tree Traverse the graph until a leaf node is reached and output the symbol 1 0 1000111010100 B A D C A A D B C
Decoding using a prefix tree Traverse the graph until a leaf node is reached and output the symbol 1 0 1000111010100 B A D C A B A D B C
Determining the cost of a file Symbol Frequency A B C D 1 0 70 3 20 37 A D B C
Determining the cost of a file Symbol Frequency A B C D 1 0 70 3 20 37 A 70 D 37 = n = B C cost ( ) depth( ) T f i i 1 i 3 20
