[SOLVED] CS algorithm Greedy algorithms

Greedy algorithms

Find the best solution to a local problem and (hope) it solves the global problem
Greedy algorithms

Greedy algorithms find the global maximum when:
1. optimal substructure optimal
solution to a subproblem is a
optimal solution to global problem 2. greedy choices are optimal
solutions to subproblems
Greedy algorithm

A list of tasks with start/finish times Want to finish most number of tasks How to find?
Activity selection

Optimal substructure:
Finding the largest number of tasks
that finish before time t can be combined with the largest number of tasks that start after time t
Activity selection

Greedy choice:
The task that finishes first is in a
optimal solution
Proof:
Suppose we have optimal solution
A. If quickest finishing task in A, done. Otherwise we can swap it in.
Activity selection

Greedy: select earliest finish time
Activity selection

A list of items with their values, but your knapsack has a weight limit
Goal: put as much value as you can in your knapsack
Knapsack problem

What is greedy choice?
Knapsack problem

What is greedy choice?
A: pick the item with highest value to weight ratio (value/weight) (only optimal if fractions allowed)
Knapsack problem

If you have to choose full items,
the constraint of the fixed backpack size is infeasible for greedy solutions
Knapsack problem

Who has used a zip/7z/rar/tar.gz?
Compression looks at the specific files you want to compress and comes up with a more efficient binary representation
Huffman code

How many letters in alphabet?
How many binary digits do we need?
If we are given a specific set of letters, we can have variable length representations and save space: aaabaaabaa : a=0,b=1->0001000100 or :aaab=1,a=0 -> 1100
Huffman code

Huffman code uses variable size letter representation compress binary representation on a specific file
letter: abcde count: 157 6 6 5
What is greedy choice?
Huffman code

We want longer representations for less frequently used letters
Greedy choice: Find least frequently used letters (or group of letters)
and assign them an extra 1/0
Repeat until all letters unique encode
Huffman code

1. Merge least frequently used nodes into a single node (usage is sum)
2. Repeat until
all nodes on a tree
Huffman code

1. Merge least frequently used nodes into a single node (usage is sum)
2. Repeat until
all nodes on a tree
You try!
Huffman code

1. Merge least frequently used nodes into a single node (usage is sum)
2. Repeat until
all nodes on a tree
Huffman code

Huffman coding length = 15 * 1 + 3 * 24 = 87
Original coding length = 15 * 3 + 3 * 24 = 117
25 percent compression
Huffman code

Greedy algorithms are closely related to dynamic programming
Greedy solutions depend on an optimal subproblem structure
Subproblem structure = recursion, which can be expensive
Dynamic programming

Dynamic programming is turning a recursion into a more efficient iteration
Consider Fibonacci numbers
Dynamic programming

Using recursion leads to repeated calculation: f(n) = f(n-1) + f(n-2)
Instead we can compute from the bottom up:
L=0, C = 1
for 1 to n
N = C+L, L=C, C=N
Dynamic programming

Consider this problem: you start on the left (any row up/down)
You can only go right, up-right (diagonal) or down-right
Want to reach right with minimizing sum of cells passed through
Dynamic programming

Lets look at the Quasar minigame in Mass Effect:
Pay $200 to play and start at 0 points Can choose to add 1-8 or 4-7 points Can stop at these (points, pay out): (15, $50), (16, $100), (17, $200), (18, $250), (19, $300), (20, $400)
Dynamic programming