CSE 421 Section 2

Graph algorithms

Administrivia

Announcements & Reminders

• HW1
• Due today (you can use at most 3 of your 6 24h tokens on it).
• HW2
• Due Thursday Oct 9 @ 11:59pm

​

The “extremal principle”

Problem 2 - Write it Better: extremal principle

Starting point:

Problem 2 - Write it Better: extremal principle

Starting point:

​

We will construct a simple path in 𝐺 (i.e. a path with no repeated vertices) as follows:

Problem 2 - Write it Better: extremal principle

Starting point:

​

We will construct a simple path in 𝐺 (i.e. a path with no repeated vertices) as follows:

​

Now finish the proof with the people around you, and we’ll go over it together.

Problem 2 - Write it Better: extremal principle

Problem 2 - Write it Better: extremal principle

It’s common in proofs by contradiction to have cases like we’ve seen here; “Option A: we’re done with our proof! Option B: do something else.” Here, though, that “do something else” has us basically where we started (a new end-vertex on our path where we’ve used one edge), and it’s tempting to say “repeat indefinitely, eventually you hit the other case.” That’s mathematically correct! But not particularly elegant. And you have to write down enough steps that your reader knows what the pattern is, which could be a lot. � �The more elegant version is to use the “extremal principle”. Instead of slowly building an object (here, the path), just start with the most extreme version of the object at the beginning (usually the biggest one or the first one). Starting with the right object lets us eliminate Option A and jump right to Option B.�

Problem 2 - Write it Better: extremal principle

NEW, EXTREME Starting point: what kind of path should we consider?

Problem 2 - Write it Better: extremal principle

Problem 2 - Write it Better: extremal principle

Problem 2 - Write it Better: extremal principle

Graph Modeling

Modeling a Problem

• In order to write an algorithm for a word problem, first we need to translate that word problem into a form that we can interact with more easily.

​

• Often, that means figuring out how to encode it into data structures and identifying what type of algorithm might work for solving it�
• A common form this will take is graph modeling, turning the problem into a graph. This will let us use graph algorithms to help us find our solution.

​

​

Graph Modeling Steps

1. Ask "what are my fundamental objects?" (These are usually your vertices)
2. Ask "how are they related to each other?" (These are usually your edges)
• Be sure you can answer these questions:
• Are the edges directed or undirected?
• Are the edges weighted? If so, what are the weights? Are negative edges possible?
• The prior two usually warrant explicit discussion in a solution. You should also be able to answer, "are there self-loops and multi-edges", though often it doesn't need explicit mention in the solution.
3. Ask "What am I looking for, is it encoded in the graph?" Are you looking for a path in the graph? A short(-est) one or long(-est) one or any one? Or maybe an MST or something else?
4. Ask "How do I find the object from 3?" If you know how, great! Choose an algorithm you know. If not, can you design an algorithm?
5. If stuck on step 4, you might need to go back to step 1! Sometimes a different graph representation leads to better results, and you'll only realize it around step 3 or 4.

​

Writing Algorithms Using Existing Algorithms

• Often, a problem can be solved by using an existing algorithm in one of two ways:�
• Reduction / Calling the existing algorithm (like a library function) with some additional work before and/or after the call

​

• Modifying the existing algorithm slightly�
• Both are valid approaches, and which one you choose depends on the problem�
• Whenever possible, it’s a good idea to use ideas that you know work! You don’t need to start from scratch to reinvent the wheel

​

​

Problem 4 – Graph Modeling

In this problem we’re going to solve a classic riddle.

​

1. First, you should solve the classic riddle yourself to get a feel for the problem. 2 You are on the beach with a jug that holds exactly 5 gallons, a jug that holds exactly 3 gallons, and a large bucket. Your goal is to put exactly 4 gallons of water into the bucket. Unfortunately, the jugs are not graduated (e.g., you can’t just fill the larger jug 4/5 full). What you can do are the following operations. � • Completely fill any of your jugs. � • Pour from one of your containers into another until the first container is empty or the second is full. � • Pour out all the remaining water in a container. �How do you get 4 gallons of water into the bucket?

Work on this problem with the people around you, and then we’ll go over it together!

Problem 4 – Graph Modeling

1. How do you get 4 gallons of water into the bucket?

Problem 4 – Graph Modeling

1. How do you get 4 gallons of water into the bucket?

Fill the 5 gallon jug, pour into the 3 gallon jug until it is full (the jugs now contain 2 and 3 gallons respectively). Pour from the larger jug into the large bucket (it now has 2 gallons). Empty the 3 gallon jug, and repeat all these steps to get the desired 4 gallons. ��

Problem 4 – Graph Modeling

1. How do you get 4 gallons of water into the bucket?

Fill the 5 gallon jug, pour into the 3 gallon jug until it is full (the jugs now contain 2 and 3 gallons respectively). Pour from the larger jug into the large bucket (it now has 2 gallons). Empty the 3 gallon jug, and repeat all these steps to get the desired 4 gallons. ��Alternatively, Fill the 3 gallon jug, pour into the 5 gallon jug. Fill the 3 gallon jug again, pour until the 5 gallon jug is full (they now contain 5 gallons and 1 gallon respectively) . Pour the 1 gallon from the 3 gallon jug into the bucket. Refill the 3 gallon jug and pour into the bucket to bring the total to 4 gallons. ��There may be other solutions.

Problem 4 – Graph Modeling

Problem 4 – Graph Modeling

Intuition:

The “state” of the puzzle can be represented as the number of gallons in each of the jugs and the bucket.

​

We encode the rules of the puzzle such that each possible step is an edge.

Problem 4 – Graph Modeling

Intuition:

The “state” of the puzzle can be represented as the number of gallons in each of the jugs and the bucket.

​

We encode the rules of the puzzle such that each possible step is an edge.

Work on this problem with the people around you. First see if you can model it as a graph, and then think about how you could use that graph in an algorithm. Then we’ll go over it together!

Problem 4 – Graph Modeling

What are my fundamental objects?:

​

How are they related to each other?:

​

What am I looking for, is it encoded in the graph?:

​

How do I find the object from 3:

Problem 4 – Graph Modeling

What are my fundamental objects?: How much water is in each jug and how much is in the final bucket. We need a vertex for each possible state the jugs and bucket can be in.

​

How are they related to each other?:

​

What am I looking for, is it encoded in the graph?:

​

How do I find the object from 3:

Problem 4 – Graph Modeling

What are my fundamental objects?: How much water is in each jug and how much is in the final bucket. We need a vertex for each possible state the jugs and bucket can be in.

​

How are they related to each other?: We can fill a jug, empty a jug, or pour one jug into another or the bucket. So, we need edges that connect the different states for each of these valid operations.

​

What am I looking for, is it encoded in the graph?:

​

How do I find the object from 3:

Problem 4 – Graph Modeling

Problem 4 – Graph Modeling

Problem 4 – Graph Modeling

Problem 4 – Graph Modeling

Problem 4 – Graph Modeling

Problem 4 – Graph Modeling

Problem 4 – Graph Modeling

Problem 4 – Graph Modeling

Problem 4 – Graph Modeling

Correctness

​

​

Problem 4 – Graph Modeling

Problem 4 – Graph Modeling

Running Time

​

​

Problem 4 – Graph Modeling

Big-O

Big-O Review

Big-O Tips for Comparing

Problem 1 – Big-O-No

Work on this problem with the people around you, and then we’ll go over it together!

Problem 1 – Big-O-No

Problem 1 – Big-O-No

Problem 1 – Big-O-No

Problem 1 – Big-O-No

Problem 1 – Big-O-No

Problem 1 – Big-O-No

Problem 1 – Big-O-No

Problem 1 – Big-O-No

Problem 1 – Big-O-No

Problem 1 – Big-O-No

That’s All, Folks!

Thanks for coming to section this week!

Any questions?

​