# Algorithm

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

More specific information is included in each subfield.

## Subfields and Concepts

See Category:Algorithms for some of its subfields.

### Elementary Topics

(It includes most topics covered in the syllabus of International Olympiad in Informatics and some related topics)

• Brute-force Algorithms (i.e. exhaustive search)
• Divide and Conquer Algorithms
• Branch-and-bound Algorithms
• Branch-and-cut Algorithms
• Sorting Algorithms
• Simple sorts
• Insertion sort
• Selection sort
• Efficient sorts
• Merge sort
• Heapsort
• Quicksort
• Bubble sort and variants
• Bubble sort
• Shellsort
• Comb sort
• Distribution sort
• Counting sort
• Bucket sort
• Search Algorithms
• Depth First Search (DFS)
• Graph and Tree Algorithms
• Minimum Spanning Tree
• Alpha–Beta Pruning (using Minimax Algorithm)
• Game Theory Algorithms
• Minimax Algorithm
• Combinatorial Game Theory
• Shortest Path Problem
• Dijkstra's Algorithm
• Bellman–Ford Algorithm
• A* search Algorithm
• Floyd–Warshall Algorithm
• Johnson's Algorithm
• Viterbi Algorithm
• Optimization Algorithms
• Evolutionary Computation
• Genetic Algorithms
• Greedy Algorithms
• Dynamic Programming
• Linear Programming
• Travelling Salesman Problem (TSP)
• Number Theory Algorithms
• Euclidean Algorithm
• Extended Euclidean Algorithm
• Integer Factorization
• Prime Factorization
• Primality Tests
• Chinese Remainder Theorem
• Hashing Algorithms
• Randomized Algorithms
• Geometry Algorithms
• Algorithms on Strings

• Cryptography Algorithms
• Asymmetric (public key) Encryption
• Symmetric (secret key) Encryption
• Cryptographic Hash Functions
• Quantum Algorithms
• Machine Learning Algorithms
• Learning Theory
• Computational Learning Theory
• Statistical Learning Theory
• Algorithmic Learning Theory
• Data Compression Algorithms
• Digital Signal Processing Algorithms
• Algorithmic Information Theory
• Kolmogorov Complexity / Algorithmic Complexity
• Algorithmic Probability / Solomonoff Probability
• Universal Search (by Levin)
• Algorithmic Randomness (by Martin-Lof)
• Solomonoff's Theory of Inductive Inference
• Epicurus' Principle of Multiple Explanations
• Occam's Razor
• Bayes' rule
• Universality probability
• Universal Turning Machine
• Minimum Description Length (MDL) principle
• Minimum Message Length (MML)
• Algorithmic Statistics
• NP-Completeness and Approximation Algorithms
• External Memory Algorithms
• Logic
• Semantics (of Programming Languages)
• Computational Complexity Theory
• Space Complexity
• Time Complexity
• Intractability
• Analysis of Algorithms
• No Free Lunch Theorem
• Computability Theory / Recursion Theory
• Church-Turing Thesis
• Decidability
• Reducibility
• Halting Problem
• Turing Complete / Computationally Universal
• Universal Turing Machine
• Models of Computation
• Sequential Models (e.g. Turing Machine)
• Functional Models (e.g. Cellular Automata)
• Concurrent Models (e.g. Petri Nets)
• Automata Theory
• Turing Machine
• Linear Bounded Automaton (LBA)
• Finite State Machine (FSM) / Finite State Automaton (FSA)
• Pushdown Automaton (PDA)
• (Formal) Grammars
• Type-0 / Recursively enumerable
• Type-1 / Context-sensitive
• Type-2 / Context-free
• Type-3 / Regular
• Formal Language Theory
• Backus–Naur Form / Backus Normal Form (BNF)

## Books

• Barak, B. (TBA). Introduction to Theoretical Computer Science. (draft)
• Linz, P. (2016). An Introduction to Formal Languages and Automata. 6th Ed. Jones & Bartlett Publishers.
• Sipser, M. (2012). Introduction to the Theory of Computation. 3rd Ed. Cengage Learning.
• Sedgewick, R. (2011). Algorithms. 4th Ed. Pearson Education.
• Knuth, D. E. (2011). The Art of Computer Programming, Volumes 1-4A. Addison-Wesley Professional.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. 3rd Ed. MIT Press.
• Fernandez, M. (2009). Models of Computation: An Introduction to Computability Theory. Springer.
• Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.(link)
• Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. 3rd Ed. Pearson.
• Skiena, S. S., & Revilla, M. A. (2003). Programming Challenges: The Programming Contest Training Manual. Springer Science & Business Media.