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

ruthmoog - Aug 29 '23 - - Dev Community

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:

Breadth-first search

Path found with Dijkstra's algorithm:

Djikstra'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

  1. Use Breadth-first search for the cheapest path in an unweighted graph, and Dijkstra's algorithm for the cheapest path in a weighted graph

  2. If you have negative weights use Bellman-Ford algorithm and not Dijkstra's algorithm

  3. Sets have some cool behaviours

    • Intersection (select items in BOTH sets)
    • Union (select all items)
    • Difference (select items NOT in both sets)
  4. 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
  5. 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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .