CHAPTER 5: ALGORITHMS
DISCRETE MATHEMATICS 2
MAT202/ MAT2043
BY MADAM FATIMAH BIBI HAMZAH
CLO1: Use properties of relations, functions, graph theory and tree in solving mathematical
problems.
CLO3: Apply algorithms to a variety of related problems for effective planning.
5.1 BIN PACKING PROBLEM
BIN PACKING PROBLEM DEFINITION
❖ Given n items with sizes s1, s2, ..., sn
such that 0 ≤ si ≤ 1 for 1 ≤ i ≤ n, pack
them into the fewest number of unit
capacity bins.
❖ There is no known polynomial time
algorithm for its solution, and it is
conjectured that none exists.
BIN PACKING PROBLEM DEFINITION
Fitting things neatly & efficiently inside a larger container.
BIN PACKING BASICS
❖ The ‘bins’ are the containers that have a particular capacity.
✔ The goal is to pack the weights into smallest possible number of
bins.
✔ The bin-packing problem is concerned with the determination of
the minimum number of bins that are needed to pack a given set
of input data items.
✔ Applications: Operation research, Computer Science, Engineering…
BIN PACKING ALGORITHMS
❖ Four things you needs to know
✔ How to find the lower bound for the problem
✔ How to perform the first-fit algorithm
✔ How to perform the first-fit decreasing algorithm
✔ How to perform full-bin packing
Lower Bound
1.
Example 1:
Six (6) groups of people, of size 3, 1, 6, 4, 5 and 2
need to fit onto mini busses with capacity of 7, but
must stay together in their groups.
Find the lower bound of the mini buses required.
First-fit Algorithm
Take the item in the order given.
Place each item in the first available bin that can be take
it. Start from bin 1 each time.
Advantage: It is quick to do
Disadvantage: It is not likely to lead to a good solution.
Example 2:
Six (6) groups of people, of size 3, 1, 6, 4, 5 and 2
need to fit onto mini busses with capacity of 7, but
must stay together in their groups.
Use the first-fit bin-packing algorithm to find the
number of mini buses required and the waste
space.
Example 2:
Example 2:
Example 2:
Using the first-fit
bin-packing
algorithm:
4 mini busses
needed
7 spaces wasted
First-fit decreasing Algorithm
Reorder the items so that they are in descending(decreasing)
order.
Apply the first-fit algorithm to record the list.
Advantage: Usually got a fairly good solution.
Disadvantage: May not get an optimal solution.
Example 3:
Six (6) groups of people, of size 3, 1, 6, 4, 5 and 2
need to fit onto mini busses with capacity of 7, but
must stay together in their groups.
Apply the first-fit decreasing algorithm to find the
number of mini buses required to pack them
efficiently so that each group stays together.
Example 3:
Example 3:
Example 3:
Using the
first-fit
decreasing
algorithm:
3 mini
busses
needed
0 spaces
Full-bin Packing
Use observation to find combinations of items that will
fill a bin. Pack this item first.
Any remaining items are packed using first-fit algorithm.
Advantage: Usually get a good solution.
Disadvantage: It is difficult to do, especially when the
number of items are a lot.
Example 4:
Six (6) groups of people, of size 3, 1, 6, 4, 5 and 2
need to fit onto mini busses with capacity of 7, but
must stay together in their groups.
Apply the full-bin algorithm to find the number of
mini buses required to pack them efficiently so that
each group stays together.
Example 4:
Example 4:
Example 4:
Using the full-bin
packing:
3 mini busses
0 spaces
Example 5:
Exercise 2
Exercise 2
Exercise 2
Try it out!
Try it out!
Try it out!
Try it out!
Try it out!
Try it out!
Try it out!
Try it out!
Try it out!
Use the first-fit algorithm to pack the following
items into bins of size 20.(The numbers in brackets
are the size of the item). State the number of bins
used and the amount of wasted space.
A(8) B(7) C(14) D(9) E((6) F(9) G(5) H(15) I(6) J(7) K(8)
Try it out!
Apply first-fit decreasing algorithm to the given
data.
A(8) B(7) C(14) D(9) E((6) F(9) G(5) H(15) I(6) J(7) K(8)
Try it out!
Apply full-bin algorithm to the given data.
A(8) B(7) C(14) D(9) E((6) F(9) G(5) H(15) I(6) J(7) K(8)
5.2 HUFFMAN CODING
❖ Huffman coding (also
known as Huffman
Encoding) is an algorithm
for doing data compression,
and it forms the basic idea
behind file compression.
5.2 HUFFMAN CODING
5.2 HUFFMAN CODING
❖ Four things you needs to
know
✔ Fixed-length Encoding
✔ Variable-length Encoding
✔ Prefix code
✔ Huffman Codes
Fixed-length Encoding
In a fixed-length encoding scheme, each character is given a
binary code with the same number of bits.
Example:
Standard ASCII is a fixed length encoding scheme, where each
character is encoded with 7 bits.
This gives us 27 = 128 different codes for characters.
Fixed-length Encoding
Fixed-length Encoding
Example 6:
Example 7:
Let the word be ABRACADABRA
What is the most economical way to write this string in a
binary representation?
Each codeword uses the same number of bits.
Letters: A – 3 bits B - 3 bits C - 3 bits D – 3 bits R – 3 bits.
All together we have 11 letters, therefore we will have :
11x 3 = 33 bits
Can we do it better?
Can we do it better?
We can do better, provided:
✔ Some characters are more frequent than others.
✔ Characters may be different bit lengths, so that for example,
in the English alphabet letter a may use only one or two bits,
while letter y may use several.
✔ We have a unique way of decoding the bit stream.
Variable-length Encoding
The magic word : ABRACADABRA
Let A – 0 B - 100 C - 1010 D – 1011 R – 11
So ABRACADABRA - 01001101010010110100110
11 letters = 23 bits but fixed-length required 33 bits.
23 < 33, so we can improved about :
(33−23)/33 × 100% = 30.3%
Variable-length Encoding
How to ensure unique reconstruction?
• Let A 01 and B 0101. How to decode 010101?
✔ AB?
✔ BA?
✔ AAA?
Use prefix codes
Prefix Codes
Any prefix code can be represented by a full binary tree.
❖ Each leaf stores a symbol.
❖ Each vertex has two children(branches)
- left branch means 0 and right represent 1.
❖ Codeword is the path from the root to the leaf
interpreting suitably the left and right branches.
Prefix Codes
Prefix code: ABRACADABRA
A–0
B - 100
C - 1010
D – 1011
R – 11
Draw a binary tree of prefix code
Prefix Codes
Decoding is unique & simple!
Read the bit stream from left to
right and starting from the root.
Whenever a leaf is reached, write
down its symbol and return to the
root.
Huffman Codes
Huffman’s Idea
Example 8:
The frequencies of symbols are listed below:
A: 40 B: 20 C: 10 D: 10 R: 20
a. Draw a Huffman tree.
b. Write a binary code word of each character.
c. Find the variable-length of encoded symbols.
Example 8: Draw a Huffman tree
Example 8: Draw a Huffman tree
Example 8: Draw a Huffman tree
Example 8: Draw a Huffman tree
Example 8:
✔ b. Write a binary code word of each character.
A: 0 B: 100 C: 1010 D: 1011 R: 11
c. Find the variable-length of encoded symbols.
A: 40x1 B: 20x3 C: 10x4 D: 10x4 R: 20x2
= 40 + 60 + 40 + 40 + 40
= 220 bits
Example 9:
Given is the letters with the following frequencies.
Symbols a c f e i t o
Frequency 25 11 14 18 10 9 4
a. Draw a Huffman tree.
b. Write a binary code word of each character.
c. Encode the sequence “ coffee “.
d. Decode the bit string 0111011100.
e. Find the average length of encoded symbol.
Example 10:
How many bits may be required for encoding the message
‘mississippi’?.
Example 11:
Example 12: