Book Club: Grokking Algorithms. 5: Dijkstra's algorithm, greedy algorithms

#books #algorithms #bookclub

Grokking Algorithms An illustrated guide for programmers and other curious people, by Aditya Y. Bhargava

Chapter 7: Dijkstra's algorithm

Chapter 8: Greedy algorithms

If you read any of these chapters, please go ahead and discuss what you thought in the comments!

📝 you can read my notes below.

📆 The next post will be on chapters 9 - 10. I'll aim for September 2023.
If you're on Storygraph and want to join me, say hi and I'll start a Buddy Read.

Dijkstra's algorithm

key topics in this chapter: weighted graphs, unweighted graphs, Dijstra's algorithm, cycles, positive and negative weighting ...

The shortest path from A to B is not always the fastest path. Dijkstra's algo finds the fastest path, by assigning weight to the edges

Cycles

A cycle means you can loop back to the same node.

Following the cycle never gives you the shortest path.
An undirected graph is a cycle
Dijkstra's algorithm only works on
- graphs with no cycles
- graphs with a positive weight cycle (if the weight of a cycle is negative when looking for the shortest path, you'll be stuck in an infinite loop calculating around the ever decrementing cycle)

Path found with Breadth-first search:

Path found with Dijkstra's algorithm:

Greedy algorithms

Key topics covered Impossible problems, NP-complete problems, approximation algorithms, greedy strategy, sets, union, difference, intersection, fractorial function...

This chapter covers a few scenarios where writing accurate algorithms is difficult. I found this the hardest to get my head around, because the example algorithms are not smart my mind was automatically trying to optimise the behaviour without realising it.

Think I might need to revisit this chapter!

The classroom scheduling problem: Find the most classes that can be held in the classroom by selecting whichever class ends first, then repeat starting after the previous classes end.

The knapsack problem: If you use the process above to steal expensive items that weigh a lot for your knapsack, it won't give you the optimal solution ... but you'll get pretty close, and sometimes that's good enough.

The set-covering problem: Make a power set (calculate everything), then choose the best answer. It takes a long time to do this... O(2^{^n})

number of factorial routes — copyright Manning Publications, drawn by adit.io

The travelling salesperson: Find the most efficient route between x calling points. The number of possible routes becomes very big, very fast (fractorial function)

NP-completeness

To figure if a problem is NP-complete, look for...

Algorithm runs quickly with a few items but slowly with a lot of items
"All combinations of x" usually suggests NP-completeness, combinations can't be broken into smaller solvable sub-problems
Involves a set and is hard to solve
You can restate the problem as the set-covering problem or the travelling salesperson problem

Key Takeaways

Use Breadth-first search for the cheapest path in an unweighted graph, and Dijkstra's algorithm for the cheapest path in a weighted graph
If you have negative weights use Bellman-Ford algorithm and not Dijkstra's algorithm
Sets have some cool behaviours
- Intersection (select items in BOTH sets)
- Union (select all items)
- Difference (select items NOT in both sets)
NP-complete problems are when you calculate all scenarios to figure out the shortest/smallest one
- e.g. the travelling salesperson, set-coverage problem
- they have no known fast solution at scale
- it's best to use an approximation algorithm instead
Greedy algorithms hope to end up with a global optimum, but optimising locally
- they're easy to write and fast to run so they make good approximation algorithms
- Greedy algorithms: at each step, pick the optimal move