# Greedy Algorithms #

Idea:

- Make choices one-at-a-time
- Never look back
- Hope for the best

However: does not work everywhere.

## When to use greedy algorithms? #

Problem should exhibit optimal substructure:

- Optimal solutions to a problem are made up from optimal solutions of subproblems
- Each problem depends on only one subproblem

## Common strategy for proving correctness #

- Make a series of choices
- Suppose we’re on track to make optimal solution T*

- Show that at each step, choices won’t rule out a globally optimal solution
- Suppose that T* disagrees with the next greedy choice

- Manipulate T* in order to make a solution T that’s not worse but agrees with the next greedy choice
- Swap choice
*k*instead of choice*j*

- Swap choice
- After having made all choices, we haven’t ruled out an optimal solution, so the solution we found is optimal

This can be turned into an inductive proof.

## Wrong greedy: unbounded knapsack #

Idea: select items with best value/weight ratio

- This works if you can fill the entire knapsack capacity
- However, if there is space left over, then we have a suboptimal solution

## Correct greedy: activity selection #

### Problem statement #

Input:

- Activities a1…an
- Start times s1…sn
- Finish times f1…fn

Output:

- Maximize the number of activities to do in a given day

### Greedy algorithm #

- Pick activity you can add with the smallest finish time
- Repeat

What makes it greedy?

- At each step in the algorithm, make a choice:
- Can increase activity set by one
- Leaving room for future choices
- Do this and hope for the best

- Hope that at the end of the day, this is a globally optimal solution

### Correctness #

- When we make a choice, we don’t rule out an optimal solution (i.e., there exists some optimal solution that contains that choice)
- Suppose we have already chosen ai and there is still an optimal T* that extends our choices
- Now consider the next choice ak
- If ak in T*, we are done
- If ak not in T*:
- Let aj be the activity in T* with smallest finish time after ai
- Consider schedule T swapping aj for ak
- T is still allowed, since ak has smaller ending time than aj, so does not conflict with anything
- T still optimal, since it has the same numer of activities as T*

- The above is the inductive step of the proof of correctness.