# Algorithm

This page contains resources about Algorithms  and Theory of Computation in general.

More specific information is included in each subfield.

## Subfields and Concepts

See Category:Algorithms for some of its subfields.

### Elementary topics

(Topics covered in International Olympiad in Informatics)

• Divide and Conquer Algorithm
• 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
• Breadth First Search (BFS)
• Depth First Search (DFS)
• Graph Algorithms
• Minimum Spanning Tree
• Hashing Algorithms
• Randomized Algorithms
• Number Theory and Cryptography Algorithms
• Chinese Remainder Theorem

• Quantum Algorithms
• Game Theory Algorithms
• Optimization Algorithms
• Genetic Algorithms
• Greedy Algorithms
• Dynamic Programming / Optimal Control
• Linear Programming
• Travelling Salesman Problem (TSP)
• Shortest Path Problem
• Dijkstra's Algorithm
• Bellman–Ford Algorithm
• A* search Algorithm
• Floyd–Warshall Algorithm
• Johnson's Algorithm
• Viterbi Algorithm
• Machine Learning Algorithms
• Learning Theory
• Computational Learning Theory
• Statistical Learning Theory
• Algorithmic Learning Theory
• Data Compression Algorithms
• Algorithms on Strings
• Digital Signal Processing Algorithms
• Algorithmic Information Theory
• Algorithmic Complexity (by Kolmogorov)
• Algorithmic Probability (by Solomonoff)
• Universal Search (by Levin)
• Algorithmic Randomness (by Martin-Loef)
• 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
• 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.
• Savage, J. E. (1998). Models of Computation. Addison-Wesley. (link)
• 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.