r/computerscience • u/Fast-Nail-7442 • Oct 23 '21
What algorithms every one should know?
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.
14
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
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
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
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
2
1
1
1
1
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
1
1
0
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.
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.