r/computerscience • • Oct 23 '21

What algorithms every one should know?

204 Upvotes

41 comments sorted by

167

u/Radiant64 Oct 23 '21

Some fun and/or useful ones off the top of my head:

Bubble sort! The traditional "bad algorithm".

Bresenham's line drawing algorithm.

Dijkstra's shunting-yard algorithm.

Mark-and-sweep.

The Mandelbrot fractal.

Binary search.

Recursive descent parsing.

Distance field raymarching.

39

u/ads_pam Oct 23 '21

Also take a look at the Window Sliding Technique and Kadane’s Algorithm.
These two have helped me solve some subarray problems MUCH faster than my brute force solutions to those type of problems. Also came up in an interview once.

11

u/SteeleDynamics Oct 24 '21

I've met Jay Kadane! He's a badass!

I asked him about the history of the maximum sub-array problem. I knew about Bentley presenting the problem and this is roughly his response:

JK: "You ever de-bone a trout?"

Me: "Nope"

JK: "Well you can either pick out the pin bones individually or you can remove the backbone and pin bones in one shot. It was like they were individually picking out the pin bones."

Very cool!

3

u/ads_pam Oct 24 '21

I’ll be honest, that’s such a wild way to go about describing the history of that algorithm, I did NOT see that coming! What an absolute legend!

5

u/[deleted] Oct 24 '21

Actually learned about line drawing algorithms in my graphics class this semester. Really interesting stuff.

7

u/loyaltyElite Oct 23 '21

I kinda love bubble sort being in this list.

0

u/[deleted] Oct 24 '21

[deleted]

1

u/loyaltyElite Oct 25 '21

I think it's just the natural sorting algorithm. Like as a child I would sort numbered blocks by picking up 2 and putting them in the right place and move to the next number

1

u/WinstonCaeser Oct 24 '21

shunting-yard makes parsing calculator or logical functions sooo much easier

0

u/[deleted] Oct 24 '21

[deleted]

2

u/Trantorianus Oct 24 '21

Most valuable is the INSIGHT, how simple algorithms can produce most complex results.

1

u/Radiant64 Oct 24 '21

Making cool images and animations.

24

u/Knight_Of_Orichalcum Oct 23 '21

I'd figure search and sort algorithms are a good start, but make sure to know about Big O notation along side it

1

u/Zazsona Oct 27 '21

Yeah, probably not much news to anyone here, but without knowledge of the Big O time complexity, if I had to pick between a 5 line Bubble Sort or multi-line Timsort... I'd probably go for the bubbles.

17

u/VintageData Oct 23 '21 edited Oct 23 '21

Binary search, radix and merge sort, breadth and depth first tree traversal, A*, Dijkstras algorithm, KMP and Boyer-Moore string search, and maybe counting sort for an example of a great hack that challenges what you thought you knew about sorting complexity.

Also for good measure it’s fun to take a deeper look at RSA, search indexing, neural nets (and gradient descent), and randomized algorithms.

Man I love algorithms and data structures. So much fun and still so much more to learn and explore.

7

u/Revolutionalredstone Oct 23 '21 edited Oct 23 '21

Branch and Bound techniques are widely applicable but much unused!

Techniques like A* are actually instances of a much more general set of algorithms loosely amenable to a search.

I find that some people solve almost everything with branch and bound while others (most people) rarely use them at-all.

Tasks like optimal voxel meshing or optimal triangle strip ordering are powerfully useful examples where branch and bound is king.

3

u/Sawertynn Oct 24 '21

Bogosort: considering various arrays, the optimistic case is the fastest of all other algorithms. So if you feel lucky, try it out!

5

u/AshingtonDC Oct 23 '21

Stalin sort

6

u/raedr7n Oct 24 '21

Remove the population until you're left with an empty (sorted) list?

9

u/AshingtonDC Oct 24 '21

remove everything out of order. the remaining items are sorted

0

u/[deleted] Oct 24 '21

[deleted]

3

u/Sawertynn Oct 24 '21

This is big O of what the leader wants it to be and nothing else!

2

u/Vakieh Oct 24 '21

I don't know that there are algorithms everyone should know, more that there are algorithms everyone doing certain things should know - and even there the sorts of things you need to 'know' in order to 'know' an algorithm are very different.

Sedgewick is the classic foundation. Knuth if you are doing real computer science rather than software development. But then there are a bunch of different ways to go from there - parallel computing algorithms, distributed computing algorithms, database specialised algorithms, data processing algorithms, various algorithms that prioritise certain things that are not cpu processing time (memory, reliability, security, network utilisation, power consumption).

Both Sedgewick and Knuth are a bit of a slog though. You could go with Algorithm Design or Algorithm Design and Application, for a different kind of slog.

The day they release a Head First Data Structures & Algorithms will be the day I agree to teach a data structures and algorithms class... until then those classes will always be a friggin nightmare.

1

u/Trantorianus Oct 24 '21

I always found Knuth absolutely unreadable.

1

u/dota2nub Oct 25 '21

Have you checked out "Grokking Algorithms"? It's not a head first and pretty limited in its content but it follows a similar idea.

2

u/fullstack_guy Oct 24 '21

You can iterate down a list and get the top X elements in O(N) complexity. I've been asked that on 3 different job interviews so far.

2

u/hawk-bull Oct 24 '21

you have piqued my curiosity. At first I thought it would be X linear selects but that would be O(XN). How do you do this?

3

u/Calvintherocket Oct 24 '21

I think quick select for the Xth largest and then scan through for elements bigger than that works.

1

u/hawk-bull Oct 24 '21

Right.. how did I not think of that hahaha

2

u/ShadySean Oct 24 '21

Bogo sort

1

u/mymar101 Oct 24 '21

Bubble tea. (Sic)

1

u/b1gm4c22 Oct 24 '21

Linear sum assignment

1

u/crazy00700yzarc Oct 24 '21

Definitely berlekamp massey /s

1

u/ThePeskyWabbit Oct 24 '21

bogo sort (aka monkey sort)

sleep sort

1

u/hawk-bull Oct 24 '21

I'm going to add BFS/DFS (personally prefer BFS cuz it's easier to implement without recursion), because I have had to use it in several places, both on online coding challenges as well as my own school project.

1

u/Competitive_Dog_6639 Oct 24 '21

Metropolis hastings if ya nasty

1

u/Galois-Group Oct 24 '21

Fast Fourier Transform

1

u/eliot3451 Oct 31 '21

Stack heap.

0

u/[deleted] Oct 23 '21

[deleted]

3

u/Pisano87 Oct 24 '21

Same found it super useful

2

u/DeltaPositionReady Oct 24 '21

My use case was where we wanted users to be able to search a list and return a close match accounting for spelling errors, without using a like or wildcard match.

The length of the distance was determined by the length of the search string to prevent enumerating the entire list.

1

u/Pisano87 Oct 27 '21

Literally did the same thing with a company that had two separate databases that needed to be joined on customer name. It was painful.