Algorithm
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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
(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
- Radix sort
- Simple sorts
- Search Algorithms
- Breadth First Search (BFS)
- 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)
- Evolutionary Computation
- 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
Advanced Topics
- 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)
Online Courses
Video Lectures
Lecture Notes
- Algorithms by Piotr Idyk
- Algorithms by Jeff Erickson
- Design and Analysis of Algorithms by Dana Moshkovitz and Bruce Tidor
- Automata, Computability and Complexity by Scott Aaronson
- Introduction to Theory of Computation by Anil Maheshwari and Michiel Smid
- Introduction to Theory of Computing by Nicholas Harvey
Books
See also Further Reading.
- 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.
- Savage, J. E. (1998). Models of Computation. Addison-Wesley. (link)
- Lewis, H. R., & Papadimitriou, C. H. (1997). Elements of the Theory of Computation. 2nd Ed. Prentice Hall.
- Davis, M., Sigal, R., & Weyuker, E. J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science. 2nd Ed. Morgan Kaufmann.
Software
- C++ Algorithms, Problems & Programming Examples
- Searching and Sorting Algorithms via C#
- C-Sharp-Algorithms - Github
- pygorithm - Python (Github)
- TheAlgorithms - C++, Python, Java, C#, C, Scala, Go, Javascript, Ruby (Github)
- EZ Collections, EZ Life - Java
- CompetitiveProgramming - C++ (Github)
- OpenFst - C++, Shell
See also
Other Resources
- Theoretical Computer Science - Google Scholar Metrics (Top Publications)
- - Algorithmic Information Theory - Scholarpedia
- List of Algorithms (Scriptol) - A complete list of all major algorithms (300) in any domain
- List of algorithms - Wikipedia
- Top 10 Algorithms and Data Structures for Competitive Programming - Geeks for Geeks
- Theory Of Computation and Automata Tutorials - Geeks for Geeks
- Dynamic Programming Problems - InterviewBit
- Dynamic Programming - Geeks for Geeks
- Traveling Salesman Problem (TSP) Implementation
- Awesome Competitive Programming
- HackerRank - Algorithms challenges
- HackerEarth