CSE 421 Section 7
What Tool?
How to Determine Which Algo Paradigm to Try
What Tool?
In the real world…
When you come across a problem you’d like to solve (perhaps on an interview or on the final exam), you generally won’t be told what kind of algorithm to write. You COULD just randomly start trying stuff, but that’s going to be pretty inefficient, and you may waste a lot of time pursuing algorithmic paradigms that just won’t work for the given problem.
Ideally, you want to be able to figure out what kind of algorithm to write in only a few tries. So how do you figure out what technique to use?
The Strategy
Step 1: Read the Problem Carefully
If these questions look familiar, they should!
If you can’t answer these, there’s no way to figure out what technique to use—you don’t even know what problem you’re solving!
Step 2: Generate Example Inputs/Outputs
Spend a few minutes producing some examples. This will help make sure that you have a clear understanding of the problem. Like usual, it’s helpful to think about a few different “typical” cases here, don’t worry too much about edge cases yet.
Plus, you might stumble upon which technique to use here; for example, if you try to visualize an example input, and you start drawing a graph.
Step 3: Ask Some Questions
At this point, you should ask “is this really a graph modeling problem?” Some signs to look for:
Step 3: Ask Some Questions
If it doesn’t feel like graph modeling, the next step to ask is probably “could I solve this problem recursively?” Try asking all of these:
These might start leading you to either a divide and conquer (with the first bullet) or dynamic programming solution. In all cases, be sure you can see “how the recursion is helping”.
Step 3: Ask Some Questions
Finally:
Then maybe it’s time for a greedy algorithm. But really, it’s time for you to generate like 3 more examples and try them against your proposed algorithm. It’s not fun to write a bunch of code only to realize it doesn’t work! And greedy algorithms very often fail. Do some more checks before you jump into code writing.
Step 4: Still Stuck?
So, none of the earlier steps worked…
Take a deep breath, it’s going to be ok.
Step 4.1: Get a Baseline Algorithm
Figure out what “brute force” or any other baseline would be, and jot it down quickly on paper. And when you’re scared, look to your baseline like that hang-in-there-cat motivational poster. Worst-case, you’re going to use that one. And if you figured out that one, you could probably find another one.
Hang in there.
Step 4.2: Write a Few More Examples
And solve them. How are you, as a person, solving them? You’re doing some process. See if you can reflect on it and realize what it looks like. That might inspire you toward an algorithm.
Step 4.3: Ask Yourself Some More Questions
2. Try it Yourself
Problem 2 – Try it Yourself!
For each of these problems, get far enough through these steps that you’re able to guess what technique you might want to use. Then write down a sentence or two about what in the problem lead you toward that technique.
Work through the parts of this problem with the people around you, and then we’ll go over it together!
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Graph. The list prerequisites contains pairs of courses that can be represented as edges and the course numbers can represent vertices in a graph.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Dynamic Programming. Different combination of coins must be tested to find the minimum number to use. By using a coin, the total amount of money is reduced which becomes the next sub-problem.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Greedy/Dynamic Programming. The goal is to maximize the output, so dynamic programming can be used to memoize the smaller sub-problems for buying/selling on certain days. An indicator to try a greedy algorithm is that you can only hold one share at any time, so there might be a way to decide which share to hold and when to sell it
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Divide and Conquer. We can split this into smaller sub-problems and we know that each linked list is sorted which is an indicator for divide and conquer algorithms.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Dynamic Programming. One key phrase is ”number of possible combinations”, so there must be a way to find the number of combinations for a sub-problem (a smaller target integer) which can be memoized using dynamic programming.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Graph. Some key words here are ”n cities” and “connected directly/indirectly” which represents a graph where cities are the vertices and whether they are connected or not as the edges.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Greedy/Dynamic Programming. A greedy algorithm can be used to always keep track of the furthest location you can jump to given which locations you’ve already been and similarly, with dynamic programming, it can be done by memoizing the furthest location for each location.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Divide and Conquer. Some keywords here are “search” and “ascending order”, so we know each column and row are sorted which can be split into smaller matrices that are sorted as well to find a value.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Greedy. The goal is to maximize the height and width, so walls that are further away and taller should be prioritized.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Divide and Conquer. Since we want to find the number of smaller elements to the right of an element in an unsorted array, there must be some sorting that occurs, so a modified divide and conquer sorting algorithm can be used.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Dynamic Programming. The indicator here is that we want to try out different permutations of removing boxes to maximize the output. After removing boxes, the problem becomes smaller, so dynamic programming should be used to memoize the solutions to smaller sub-problems.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Graph. There is a dependency on being able to visit a room since you must have found a key in the previous room to unlock it and the goal is to visit all rooms. Because of this, the problem can be represented as a graph with the goal as traversing through all nodes of the graph.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Graph. The key takeaway here is that the list times is a list of weighted edges since for every element, it provides the source, destination and the weight. Another element in this question is that it wants to find the minimum time it takes for all n locations to receive a signal which alludes to some sort of graph traversal.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Greedy: Less trivial greedy idea: for each candidate, we treat him/her as the one who has the minimum efficiency in a team. Then, we select the rest of the team members based on this condition.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Dynamic programming. Since different merging orders could lead to the same subproblem, using a memo structure could reduce the amount of calculation needed.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Graph: Cities are the nodes and highways are undirected edges.
Problem 2 – Try it Yourself!
Problem 2 – Try it Yourself!
Greedy: we greedily concatenate source and check if we have target as a subsequence of the concatenated string or not.
That’s All, Folks!
Thanks for coming to section this week!
Any questions?