FANDOM


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

More specific information is included in each subfield.

Subfields and ConceptsEdit

See Category:Algorithms for some of its subfields.

Elementary topicsEdit

(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 Edit

  • Quantum Algorithms
  • Game Theory Algorithms
  • Optimization Algorithms
  • 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
    • 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 CoursesEdit

Video LecturesEdit

Lecture NotesEdit

BooksEdit

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.

SoftwareEdit

See alsoEdit

Other ResourcesEdit