Algorithm

From Ioannis Kourouklides
Jump to: navigation, 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
  • 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)
  • 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]

Books[edit]

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.
  • Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.
  • 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[edit]

See also[edit]

Other Resources[edit]