Grokking Algorithms

EXERCISE
7.1
In each of these graphs, what is the weight of the shortest path from 
start to finish?

---

140
Chapter 7
 
 
I
 
 
Dijkstra’s algorithm
Recap
• Breadth-first search is used to calculate the shortest path for
an unweighted graph.
• Dijkstra’s algorithm is used to calculate the shortest path for
a weighted graph.
• Dijkstra’s algorithm works when all the weights are positive.
• If you have negative weights, use the Bellman-Ford algorithm.

---

141
greedy 
algorithms
In this chapter
• You 
learn how to tackle the impossible:
problems that have no fast algorithmic solution 
(NP-complete problems).
• You learn how to identify such problems when you 
see them, so you don’t waste time trying to find a 
fast algorithm for them.
• You learn about approximation algorithms, which 
you can use to find an approximate solution to an 
NP-complete problem quickly.
• You learn about the greedy strategy, a very simple 
problem-solving strategy.
8

---

142
Chapter 8
 
 
I
 
 
Greedy algorithms
The classroom scheduling problem
Suppose you have a classroom and want to hold as many classes 
here as possible. You get a list of classes.
You can’t hold
 all
of these classes in there, because some of them 
overlap.
You want to hold as many classes as possible in this classroom. How 
do you pick what set of classes to hold, so that you get the biggest set of 
classes possible?
Sounds like a hard problem, right? Actually, the algorithm is so easy, it 
might surprise you. Here’s how it works:
1. Pick the class that ends the soonest. This is the first class you’ll hold 
in this classroom.
2. Now, you have to pick a class that starts after the first class.
Again, pick the class that ends the soonest. This is the second
class you’ll hold.

---

143
The classroom scheduling problem
Keep doing this, and you’ll end up with the answer! Let’s try it out. Art 
ends the soonest, at 10:00 a.m., so that’s one of the classes you pick.
Now you need the next class that starts after 10:00 a.m. and ends
the soonest.
English is out because it conflicts with Art, but Math works.
Finally, CS conflicts with Math, but Music works.
So these are the three classes you’ll hold in this classroom.

---

144