Algorithm
Jump to navigation
Jump to search
This page contains resources about Algorithms and Theory of Computation in general.
More specific information is included in each subfield.
Subfields and Concepts[edit]
See Category:Algorithms for some of its subfields.
Elementary Topics[edit]
(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[edit]
- 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[edit]
Video Lectures[edit]
Lecture Notes[edit]
- 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[edit]
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[edit]
- 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[edit]
Other Resources[edit]
- 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