Computer Science Algorithms Everyone Should Know

algorithms.md

Source: http://www.reddit.com/r/compsci/comments/1kcal2/algorithims_everyone_should_know/cbnhcbz

Here's a random selection, approximately ordered from most basic to more advanced. I may add more later...

Edit: this is definitely not meant to be an exhaustive list, it's just a random selection of things I use a lot/think are cool.

Numerical:

• Euclid's algorithms
• Gaussian elimination
• Fourier-Motzkin elimination
• Fast Fourier Transform

Data structures:

• Binary trees
• Hash tables
• Binary decision diagrams
• Disjoint sets
• Trie
• Priority queue

Sorting & searching arrays:

• Bubblesort
• Quicksort
• Heapsort -- mostly useful because building a heap is a really handy way of making a priority queue
• Binary search

Tree search:

• Breadth first search
• Depth first search

Graphs:

• Dijkstra's algorithm
• Prim's algorithm
• Ford-Fulkerson
• A*

Automata and parsing:

• Finite automata
• Thompson's construction for creating a nondeterministic finite automaton from a regular expression
• The powerset construction for determinising a finite automaton
• Pushdown automata and context-free languages
• Recursive descent parsing for LL(k) languages LR parsing for LR(k) languages

Numerical optimization:

• Simplex
• Hill climbing algorithms
• Newton's method

Combinatorial optimization:

• The Hungarian algorithm for solving the assignment problem
• Boolean satisfiability -- an NP-complete problem
• DPLL -- used to solve SAT
• QBF -- a PSPACE complete problem

Graphics:

• Rasterisation
• Ray tracing

Compilers:

• Hindley-Milner type inference
• Register colouring

Machine learning:

• Back propagation for neural networks
• Expectation maximization algorithm
• Naive Bayes
• Support vector machines
• Random forests

Cryptography:

• Diffie-Hellman key exchange
• DES
• Block cipher modes of operation -- most important is CBC imho
• RSA

Miscellaneous:

• Graham scan for finding convex hulls
• Quine-McCluskey algorithm for logic minimization