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

(It includes topics of International Olympiad in Informatics and some others)

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

Advanced Topics

• Quantum Algorithms
• Game Theory Algorithms
• Optimization Algorithms
  • Evolutionary Computation
    • 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
  • Digital Image 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
• 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

Online Courses

Video Lectures

• Introduction to Algorithms by Erik Devaine and Srinivas Devadas

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

Books

See also Further Reading.

• 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.

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)

See also

• International Olympiad in Informatics

Other Resources

• Theoretical Computer Science - Google Scholar Metrics (Top Publications)
• - Algorithmic Information Theory - Scholarpedia
• Top 10 Algorithms and Data Structures for Competitive Programming - Geeks for Geeks
• Theory Of Computation and Automata Tutorials - Geeks for Geeks
• Dynamic Programming - Geeks for Geeks
• Traveling Salesman Problem (TSP) Implementation
• Awesome Competitive Programming
• HackerRank - Algorithms challenges
• HackerEarth