# 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