Thread by @svpino

One of the most useful things you can learn:

Greedy algorithms, how they work, and how to solve problems using them.

Here is why they are fundamental: ↓

Greedy algorithms:

• Pretty intuitive to understand
• Easy to come up with them
• A great way to solve many problems

Optimization is the root of all evil. Many times, a greedy solution is all you need to solve a problem.

At each step, a greedy algorithm always makes the best optimal choice.

(Unfortunately, this approach is not always guaranteed to converge to the optimal solution. More about this later.)

Here is an example problem where you could use a greedy algorithm:

"Given a list of tasks and the time it takes to complete them, calculate the maximum number of tasks you can do in a day."

Here is how you could solve it:

1. Sort the list in increasing order.
2. Consecutively select a task until you can't fit another one in a day.

Greedy algorithms don't always find the optimal solution.

An example: Find the cheapest route between two cities on a map.

Always taking the cheapest next step from where you're at will not get you the optimal route.

There are problems for which greedy algorithms are perfect.

A couple of successful applications:

1. Dijkstra’s algorithm: Find the shortest path between two nodes in a weighted graph.

2. Huffman encoding: A method to compress data.

As a software engineer, understanding how to build greedy solutions is a critical skill.

I usually always start with a greedy solution as a baseline. I can always optimize further when necessary.