Chapitre 3: Greedy algorithms

Interval scheduling problem
18:54

Problem (Interval scheduling problem)

Job $j$ starts at $s_{j}$ and finishes at $f_{j}$
Two jobs are compatible if they don't overlap
Goal: find maximum subset of mutually compatible jobs

Question

What kind of heuristics would you consider to select your maximum subset?

What is wrong with earliest start time, shortest interval or fewest conflicts?

Dynamic programming solution
18:54

Consider $S_{ij}$ the set of activities that start after activity $a_{i}$ finishes and before $a_{j}$ starts, and write $c [i, j]$ the size of an optimal solution on $S_{ij}$ .

If $a_{k}$ is part of the optimal solution, then

c [i, j] = c [i, k] + 1 + c [k, j] .

We brute-force the choice of

a_{k}

to obtain:

c [i, j] = {0 max {c [i, k] + c [k, j] + 1 : a_{k} \in S_{ij}} if S_{ij} = \emptyset otherwise

Exercise

Implement a top-down memoized version of the problem. What is its running time?

DP solution
18:54

Greedy template
18:54

Greedy template

Consider jobs in some order
Select first job
Remove incompatible jobs
Repeat steps 2 and 3 while still possible

Question

How would you order the activities?

Optimality of greedy algorithm
18:54

Proposition

The greedy algorithm that considers jobs in increasing order of finish time is optimal.

Phrased in terms of the DP, we could say

Proposition

The optimal solution of $S_{ij}$ could always be assumed to contain the activity in $S_{ij}$ with earliest finish time.

Greedy implementation
18:54

Exercise

Implement a greedy version of the interval scheduling problem

Exercises
18:54

Exercise (Interval partitioning)

Lectures have start and finish times
Goal: find smallest number of classrooms to schedule all lectures.

Implement a solution, prove it's optimal and find its running time.

Programming exercises
18:54

Exercise

Given an array of nonnegative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

Exercise

What if we want to know the minimum number of jumps required to reach the last index?

Exercise: Lemonade change
18:54

Exercise

At a lemon stand, each lemonade costs 5 euros. Each customer will buy one lemonade and pay with either a 5, 10, or 20 euro bill. You must determine whether it is possible to provide the correct change to each customer, knowing that you don't have any change at first.

Lossless text compression
18:54

Question

Given a text that uses 32 symbols (26 letters, space, punctuation), how can we encode this text in bits?

Question

How can we use the relative frequencies of the letters to reduce our encoding? How do we know when the next symbol begins?

Prefix code
18:54

A prefix code does not have ambiguities.

Definition (Prefix code)

A prefix code for a set $S$ is a function

c : S \to {0, 1}

such that

c (x)

is never a prefix of

y

x, y \in S

are distinct.

Codes: binary tree representation
18:54

Example

Draw the tree associated with

c (a) = 11, c (e) = 01, c (k) = 001, c (l) = 10, c (u) = 000

Question

When is a binary tree a representation of a prefix code?

Exercise

What is the meaning of 111010001111101000

Optimality
18:54

Definition (Average bits per letter)

ABL (c) = x \in S \sum f_{x} ∣ c (x) ∣

In a binary tree, the formula becomes

ABL (T) = x \in S \sum f_{x} depth_{T} (x)

Problem

Given an alphabet $S$ , find a prefix code that minimizes the ABL.

Towards Huffman encoding
18:54

Key observations

Lowest frequency letters should be at the lowest level in the tree of an optimal prefix code.
For $n > 1$ , the lowest level always contains at least two leaves.
The order in which items appear in a level does not matter

Huffman encoding by hand
18:54

Example

Encode the string "pepper" using Huffman encoding

Huffman: pseudo-code
18:54

Huffman(S) {
  if |S|=2 {
    return tree with root and 2 leaves
  } else {
    let y and z be lowest-frequency letters in S
    S’ = S
    remove y and z from S’
    insert new letter ω in S’ with fω=fy+fz
    T’ = Huffman(S’)
    T = add two children y and z to leaf ω from T’
    return T
  }
}

Question

What's the time complexity?

Huffman: correctness
18:54

Proposition

Let T' be the tree obtained by removing two sibling leaves $x, y$ , and relabelling the parent $ω$ with frequency $f_{x} + f (y)$ .

ABL (T^{'}) = ABL (T) - f_{ω}

Proposition

Huffman code for S achives the minimum ABL of any prefix code

Priority queue
18:54

We need a priority queue model so we can associate shorter encodings with the most frequent letters. The following method should be implemented and run "fast".

insert(S, x)
max(S)
extract_max(S)
increase_key(S, x, k)

Data structure: Heaps
18:54

Definition (Heap)

A heap is an array visualized as a nearly complete binary trees.

Example

Represent the following array as a heap

0	1	2	3	4	5	6	7	8	9
23	12	34	4	5	10	7	8	29	1

Question

Given a node $i$ , what are the indices of its children? What about the index of the parent?

Max and min-heaps
18:54

Definition (Max/min-heaps)

A max (resp. min) heap is a heap that has the additional property that a parent is always greater (resp. less) than or equal to its children.

A min heap is ideal to find the two least frequent letters!

Min-Heaps in Python's standard library
18:54

Question

How are these methods implemented to keep the heap invariant? Why do we sift down instead of up?

Huffman encoding: implementation
18:54

Exercise

Implement Huffman's encoding. How many bits do you save on Shakespeare's 18th sonnet?

Huffman code: exercises
18:54

Interval scheduling problem18:54

Problem (Interval scheduling problem)

Question

Dynamic programming solution18:54

Exercise

DP solution18:54

Greedy template18:54

Greedy template

Question

Optimality of greedy algorithm18:54

Proposition

Proposition

Greedy implementation18:54

Exercise

Exercises18:54

Exercise (Interval partitioning)

Programming exercises18:54

Exercise

Exercise

Exercise: Lemonade change18:54

Exercise

Lossless text compression18:54

Question

Question

Prefix code18:54

Definition (Prefix code)

Codes: binary tree representation18:54

Example

Question

Exercise

Optimality18:54

Definition (Average bits per letter)

Problem

Towards Huffman encoding18:54

Key observations

Huffman encoding by hand18:54

Example

Huffman: pseudo-code18:54

Question

Huffman: correctness18:54

Proposition

Proposition

Priority queue18:54

Data structure: Heaps18:54

Definition (Heap)

Example

Question

Max and min-heaps18:54

Definition (Max/min-heaps)

Min-Heaps in Python's standard library18:54

Question

Huffman encoding: implementation18:54

Huffman encoding: implementation18:54

Exercise

Huffman code: exercises18:54

Huffman code: exercises18:54

Exercices: homework18:54

Interval scheduling problem
18:54

Dynamic programming solution
18:54

DP solution
18:54

Greedy template
18:54

Optimality of greedy algorithm
18:54

Greedy implementation
18:54

Exercises
18:54

Programming exercises
18:54

Exercise: Lemonade change
18:54

Lossless text compression
18:54

Prefix code
18:54

Codes: binary tree representation
18:54

Optimality
18:54

Towards Huffman encoding
18:54

Huffman encoding by hand
18:54

Huffman: pseudo-code
18:54

Huffman: correctness
18:54

Priority queue
18:54

Data structure: Heaps
18:54

Max and min-heaps
18:54

Min-Heaps in Python's standard library
18:54

Huffman encoding: implementation
18:54

Huffman encoding: implementation
18:54

Huffman code: exercises
18:54

Huffman code: exercises
18:54

Exercices: homework
18:54