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
Let’s 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
