Algorithm

From Ioannis Kourouklides
Revision as of 15:59, 28 April 2018 by Kourouklides (talk | contribs) (Advanced Topics)
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

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 ones)

  • Brute-force Algorithms (i.e. exhaustive search)
  • Divide and Conquer Algorithms
  • Branch-and-bound 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
  • 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
  • Hashing Algorithms
  • Randomized Algorithms
  • Number Theory and Cryptography Algorithms
    • Chinese Remainder Theorem
  • Optimization Algorithms
  • Shortest Path Problem
    • Dijkstra's Algorithm
    • Bellman–Ford Algorithm
    • A* search Algorithm
    • Floyd–Warshall Algorithm
    • Johnson's Algorithm
    • Viterbi Algorithm
  • Algorithms on Strings

Advanced Topics

  • 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
  • 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
    • Halting Problem
  • 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

Lecture Notes

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

See also

Other Resources