CSE 421 Section 3

Greedy Algorithms

How to Approach Writing an Algorithm

Writing an Algorithm

• Throughout this course, you will learn how to write several different kinds of algorithms. �(Ex: graph modeling, greedy algorithms, more kinds to come)�
• It can be difficult to understand what a problem actually needs you to do, which makes picking what kind of algorithm might solve the problem challenging as well!�
• Today, we will work through a problem using an algorithm-writing strategy that you can apply to all the problems throughout this course and beyond

The Strategy

1. Read and Understand the Problem
2. Generate Examples
3. Come Up with a Baseline
4. Brainstorm and Analyze Possible Algorithms
5. Write an Algorithm
6. Show Your Algorithm is Correct
7. Optimize and Analyze the Run Time

1. Read and Understand the Problem

No really, we mean it!

• You can’t solve a problem if you don’t know what you’re supposed to do! �
• Remember that problems are written in mathematical English, which is likely to be much more dense than, say, a paragraph from a novel. You’ll have to read more slowly (this advice still applies for our ridiculous word problems). �
• As you’re reading, underline anything you don’t understand. �
• Rereading the problem a few times can often help (it’s easier to understand details once you have the big picture in your brain).

Ask Yourself some Questions:

• Are there any technical terms in the problem you don’t understand? �
• What is the input type? (Array? Graph? Integer? Something else?) �
• What is your return type? (Integer? List?) �
• Are there any words that look like normal words, but are secretly technical terms (like “subsequence” or “list”)? These words sometimes subtly add restrictions to the problem and can be easily missed.

Problem 1 – Line Covering

Problem 1.1 – Line Covering

• Are there any technical terms in the problem you don’t understand? ��
• What is the input type? (Array? Graph? Integer? Something else?) ��
• What is your return type? (Integer? List?) ��
• Are there any words that look like normal words, but are secretly technical terms (like “subsequence” or “list”)? These words sometimes subtly add restrictions to the problem and can be easily missed.

Work reading through this problem with the people around you and answering the four questions, and then we’ll go over it together!

Problem 1.1 – Line Covering

• Are there any technical terms in the problem you don’t understand? ��
• What is the input type? (Array? Graph? Integer? Something else?) ��
• What is your return type? (Integer? List?) ��
• Are there any words that look like normal words, but are secretly technical terms (like “subsequence” or “list”)? These words sometimes subtly add restrictions to the problem and can be easily missed.

Problem 1.1 – Line Covering

• Are there any technical terms in the problem you don’t understand? ��
• What is the input type? (Array? Graph? Integer? Something else?) ��
• What is your return type? (Integer? List?) ��
• Are there any words that look like normal words, but are secretly technical terms (like “subsequence” or “list”)? These words sometimes subtly add restrictions to the problem and can be easily missed.

“cover” means “place a truck at most 3 miles from”

Problem 1.1 – Line Covering

• Are there any technical terms in the problem you don’t understand? ��
• What is the input type? (Array? Graph? Integer? Something else?) ��
• What is your return type? (Integer? List?) ��
• Are there any words that look like normal words, but are secretly technical terms (like “subsequence” or “list”)? These words sometimes subtly add restrictions to the problem and can be easily missed.

“cover” means “place a truck at most 3 miles from”

A list of integers

Problem 1.1 – Line Covering

• Are there any technical terms in the problem you don’t understand? ��
• What is the input type? (Array? Graph? Integer? Something else?) ��
• What is your return type? (Integer? List?) ��
• Are there any words that look like normal words, but are secretly technical terms (like “subsequence” or “list”)? These words sometimes subtly add restrictions to the problem and can be easily missed.

“cover” means “place a truck at most 3 miles from”

A list of integers

A list of integers

Problem 1.1 – Line Covering

• Are there any technical terms in the problem you don’t understand? ��
• What is the input type? (Array? Graph? Integer? Something else?) ��
• What is your return type? (Integer? List?) ��
• Are there any words that look like normal words, but are secretly technical terms (like “subsequence” or “list”)? These words sometimes subtly add restrictions to the problem and can be easily missed.

“cover” means “place a truck at most 3 miles from”

A list of integers

A list of integers

list

2. Generate Examples

Examples Help us Understand!

• You should generate two or three sample instances and the correct associated outputs. �
• If you’re working with others, these instances help make sure you’ve all interpreted the problem the same way.

​

• Your second goal is to get better intuition on the problem. You’ll have to find the right answer to these instances. In doing so you might notice some patterns that will help you later�
• Note: You should not think of these examples as debugging examples – null or the empty list is not a good example for this step. You can worry about edge cases at the end, once you have the main algorithm idea. You should be focused on the “normal” (not edge) case.

Problem 1.2 – Line Covering

Generate two examples with their associated outputs. Put some effort into these! The more different from each other they are, the more likely you are to catch mistakes later.

Work through reading this problem with the people around you and answering the four questions, and then we’ll go over it together!

Problem 1.2 – Line Covering

Generate two examples with their associated outputs. Put some effort into these! The more different from each other they are, the more likely you are to catch mistakes later.

Problem 1.2 – Line Covering

Generate two examples with their associated outputs. Put some effort into these! The more different from each other they are, the more likely you are to catch mistakes later.

3. Come Up with a Baseline

Inefficient but Effective First Attempt

• In a time-constrained setting (like a technical interview or an exam) you often want a “baseline” algorithm.

​

• This should be an algorithm that you can implement and will give you the right answer, even if it might be slow.

​

• We’re going to skip this step today, but you’ll see it in future examples and in lectures.

4. Brainstorm and Analyze �Possible Algorithms

Think about Algorithm Possibilities

• It sometimes helps to ask, “what kind of algorithm could I design?” �(This week the answer is going to be “a greedy algorithm” because we’re learning about greedy algorithms)

​

• By the end of the quarter, you’ll have a list of possible techniques.

​

• Questions to help you pick:
• Does this problem remind me of any algorithms from class? What technique did we use there?
• Do I see a modeling opportunity (say a graph we could run an algorithm on, or a stable matching instance we could write)?
• Is there a way to improve the baseline algorithm (if you have one) to something faster?

Remember: Your First Guess Might Not Be Right!

• You may want to try multiple different algorithm paradigms if you’re not sure what might work best / be fastest

​

• Even if you’re pretty sure of the algorithm type you want to use, it helps to brainstorm multiple different possibilities

​

• Then, we can test these possibilities, using the examples we came up with in part 2, to see which choice gives the correct output

Problem 1.4 – Line Covering

For this problem today, you should use a greedy algorithm.

​

Come up with at least two greedy ideas (which may or may not work). Run each of your ideas through the examples you generated in part 2.

Think of some greedy ideas with the people around you, and then we’ll go over it together!

Problem 1.4 – Line Covering

Come up with at least two greedy ideas (which may or may not work). Run each of your ideas through the examples you generated in part 2.

Problem 1.4 – Line Covering

Come up with at least two greedy ideas (which may or may not work). Run each of your ideas through the examples you generated in part 2.

Try your Algorithm Ideas on your Examples

• Now that you have some (hopefully) good ideas, you want to test them out on actual example inputs and see if you get the expected output

​

• Generate a few more instances and narrow down to just one possibility:
• If you eliminate all of your ideas, go back to the last step and generate a new rule
• If you can’t eliminate down to one choice after multiple examples, try specifically to create an instance where they should behave differently
• If you still can’t make them behave differently, just pick one to try

​

• This will help you determine which algorithm to pursue!

Problem 1.4 – Line Covering

Come up with at least two greedy ideas (which may or may not work). Run each of your ideas through the examples you generated in part 2.

5. Write an Algorithm

Write That Pseudocode!

• Now that you’ve determined which of your ideas is (probably) correct, you need to formalize your algorithm

​

• Some tips:
• You should first see if you can describe it in English! This is much easier to parse for a human.
• You don’t need to be very specific about data structures.
• Pseudocode can help be unambiguous in some cases (so use it sometimes), but as a rule of thumb: if you are using many symbols to say something simple, then probably pseudocode is not the way to go.

Problem 1.5 – Line Covering

function Placements(A[1..n])

uncoveredIndex ← 1

sites ← empty list

while uncoveredIndex ≤ n do

newSite ← A[uncoveredIndex] + 3

append newSite to sites.

while uncoveredIndex ≤ n and |A[uncoveredIndex] − newSite| ≤ 3 do

uncoveredIndex++

return sites

6. Show Your Algorithm is Correct

Writing the Algo isn’t Enough… �We Need to Prove that it Works!

• In general, you’ll be often writing some kind of induction proof, or proving some implications to show that your algorithm is correct

​

• For greedy algorithms specifically, we have three common proof strategies:
• greedy stays ahead
• exchange arguments
• structural arguments

Problem 1.6 – Line Covering

Write a proof of correctness.

Try to use one of those greedy proof techniques with the people around you, and then we’ll go over it together!

Problem 1.6 – Line Covering

Problem 1.6 – Line Covering

7. Optimize and Analyze the Run Time

Just Like Back in 332…

• Make your algorithm as efficient as possible.

​

• Flesh out any pseudocode you’ve written with enough detail to analyze the running time (do you need particular data structures?).

​

• Write and justify the big-O running time.
• Can you make your code more efficient?
• Can you give a reason why you shouldn’t expect the code to be any faster?

Problem 1.7 – Line Covering

Write the big-O of your code and justify the running time with a few sentences.

Problem 1.7 – Line Covering

Write the big-O of your code and justify the running time with a few sentences.

That’s All, Folks!

Thanks for coming to section this week!

Any questions?

​