# Algorithm

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 ones)

• Brute-force Algorithms (i.e. exhaustive search)
• Divide and Conquer Algorithms
• Branch-and-bound 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
• Hashing Algorithms
• Randomized Algorithms
• Number Theory and Cryptography Algorithms
• Chinese Remainder Theorem
• Optimization Algorithms
• Shortest Path Problem
• Dijkstra's Algorithm
• Bellman–Ford Algorithm
• A* search Algorithm
• Floyd–Warshall Algorithm
• Johnson's Algorithm
• Viterbi Algorithm
• Algorithms on Strings

• 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
• NP-Completeness and Approximation Algorithms
• External Memory Algorithms
• Logic
• Semantics (of Programming Languages)
• Computational Complexity Theory
• Space Complexity
• Time Complexity
• Intractability
• Computability Theory / Recursion Theory
• Church-Turing Thesis
• Decidability
• Reducibility
• Halting Problem
• 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

## Books

• Davis, M., Sigal, R., & Weyuker, E. J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science. 2nd Ed. Morgan Kaufmann.
• Lewis, H. R., & Papadimitriou, C. H. (1997). Elements of the Theory of Computation. 2nd Ed. Prentice Hall.
• Skiena, S. S., & Revilla, M. A. (2003). Programming Challenges: The Programming Contest Training Manual. Springer Science & Business Media.
• Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation. 3rd Ed. Pearson.
• Cormen, T. H. (2009). Introduction to Algorithms. 3rd Ed. MIT Press.
• Fernandez, M. (2009). Models of Computation: An Introduction to Computability Theory. Springer.
• Sedgewick, R. (2011). Algorithms. 4th Ed. Pearson Education.
• Knuth, D. E. (2011). The Art of Computer Programming, Volumes 1-4A. Addison-Wesley Professional.
• Sipser, M. (2012). Introduction to the Theory of Computation. 3rd Ed. Cengage Learning.
• Linz, P. (2016). An Introduction to Formal Languages and Automata. 6th Ed. Jones & Bartlett Publishers.