Difference between revisions of "Algorithm"

From Ioannis Kourouklides
Jump to navigation Jump to search
(Subfields and Concepts)
(Books)
 
(31 intermediate revisions by the same user not shown)
Line 6: Line 6:
 
''See [http://kourouklides.wikia.com/wiki/Category:Algorithms Category:Algorithms] for some of its subfields.''
 
''See [http://kourouklides.wikia.com/wiki/Category:Algorithms Category:Algorithms] for some of its subfields.''
  
=== Elementary topics===
+
=== Elementary Topics===
''(It includes most topics covered in the syllabus of [[International Olympiad in Informatics]] and some related ones)''
+
''(It includes most topics covered in the syllabus of [[International Olympiad in Informatics]] and some related topics)''
* Divide and Conquer Algorithm
+
* Brute-force Algorithms (i.e. exhaustive search)
 +
* Divide and Conquer Algorithms
 +
* Branch-and-bound Algorithms
 +
* Branch-and-cut Algorithms
 
* Sorting Algorithms
 
* Sorting Algorithms
 
** Simple sorts
 
** Simple sorts
Line 28: Line 31:
 
** Breadth First Search (BFS)
 
** Breadth First Search (BFS)
 
** Depth First Search (DFS)
 
** Depth First Search (DFS)
*[[Graph Theory|Graph]] and Tree Algorithms
+
* [[Graph Theory|Graph and Tree]] Algorithms
 
** Minimum Spanning Tree
 
** Minimum Spanning Tree
* Hashing Algorithms
+
** Alpha–Beta Pruning (using Minimax Algorithm)
* Randomized Algorithms
+
* [[Game Theory|Game Theory Algorithms]]
* [[Cryptography |Number Theory and Cryptography Algorithms]]
+
** Minimax Algorithm
** Chinese Remainder Theorem
+
** Combinatorial Game Theory
* [[Optimization |Optimization Algorithms]]
 
** [[Evolutionary Computation]]
 
*** Genetic Algorithms
 
** Greedy Algorithms
 
** Dynamic Programming / Optimal [[Control Theory|Control]]
 
** Linear Programming
 
** Travelling Salesman Problem (TSP)
 
 
* Shortest Path Problem
 
* Shortest Path Problem
 
** Dijkstra's Algorithm
 
** Dijkstra's Algorithm
Line 48: Line 44:
 
** Johnson's Algorithm
 
** Johnson's Algorithm
 
** Viterbi Algorithm
 
** Viterbi Algorithm
 +
* [[Optimization |Optimization Algorithms]]
 +
** [[Evolutionary Computation]]
 +
*** Genetic Algorithms
 +
** Greedy Algorithms
 +
** Dynamic Programming
 +
** Linear Programming
 +
** Travelling Salesman Problem (TSP)
 +
* [[Cryptography |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
 
* Algorithms on Strings
  
 
=== Advanced Topics ===
 
=== Advanced Topics ===
 +
* [[Cryptography |Cryptography Algorithms]]
 +
** Asymmetric (public key) Encryption
 +
** Symmetric (secret key) Encryption
 +
** Cryptographic Hash Functions
 
* [[Quantum Computation|Quantum Algorithms]]
 
* [[Quantum Computation|Quantum Algorithms]]
* [[Game Theory|Game Theory Algorithms]]
 
 
* [[Machine Learning|Machine Learning Algorithms]]
 
* [[Machine Learning|Machine Learning Algorithms]]
 
* [[Statistical Learning Theory|Learning Theory]]
 
* [[Statistical Learning Theory|Learning Theory]]
Line 69: Line 85:
 
** Epicurus' Principle of Multiple Explanations
 
** Epicurus' Principle of Multiple Explanations
 
** Occam's Razor
 
** Occam's Razor
** Bayes rule
+
** Bayes' rule
 +
** Universality probability
 +
** Universal Turning Machine
 +
** Minimum Description Length (MDL) principle
 +
** Minimum Message Length (MML)
 +
** Algorithmic Statistics
 
* NP-Completeness and Approximation Algorithms
 
* NP-Completeness and Approximation Algorithms
 
* External Memory Algorithms
 
* External Memory Algorithms
*[[Logic]]
+
* [[Logic]]
 
* Semantics (of Programming Languages)
 
* Semantics (of Programming Languages)
 
* Computational Complexity Theory
 
* Computational Complexity Theory
Line 78: Line 99:
 
** Time Complexity
 
** Time Complexity
 
** Intractability
 
** Intractability
 +
** Analysis of Algorithms
 +
** No Free Lunch Theorem
 
* Computability Theory / Recursion Theory
 
* Computability Theory / Recursion Theory
 
** Church-Turing Thesis
 
** Church-Turing Thesis
 
** Decidability
 
** Decidability
 
** Reducibility
 
** Reducibility
 +
** Halting Problem
 +
** Turing Complete / Computationally Universal
 +
** Universal Turing Machine
 
* Models of Computation
 
* Models of Computation
 
** Sequential Models (e.g. Turing Machine)
 
** Sequential Models (e.g. Turing Machine)
Line 97: Line 123:
 
** Type-3 / Regular
 
** Type-3 / Regular
 
* Formal Language Theory
 
* Formal Language Theory
 +
** Backus–Naur Form / Backus Normal Form (BNF)
  
 
==Online Courses==
 
==Online Courses==
Line 108: Line 135:
 
* [https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/index.htm Automata, Computability and Complexity by Scott Aaronson]
 
* [https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/index.htm Automata, Computability and Complexity by Scott Aaronson]
 
* [http://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf Introduction to Theory of Computation by Anil Maheshwari and Michiel Smid]
 
* [http://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf Introduction to Theory of Computation by Anil Maheshwari and Michiel Smid]
 +
* [https://www.cs.ubc.ca/~nickhar/F18-421/ Introduction to Theory of Computing by Nicholas Harvey]
  
 
==Books==
 
==Books==
 
''See also [https://en.wikipedia.org/wiki/Theory_of_computation#Further_reading Further Reading].''
 
''See also [https://en.wikipedia.org/wiki/Theory_of_computation#Further_reading Further Reading].''
 +
 +
* Barak, B. (TBA). Introduction to Theoretical Computer Science. [https://introtcs.org/ (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.[http://thuvien.thanglong.edu.vn:8081/dspace/bitstream/DHTL_123456789/4013/1/cs504-2.pdf (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. ([http://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation.pdf 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.
 
*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. ([http://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation.pdf 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==
 
==Software==
Line 131: Line 162:
 
* [http://codeforces.com/blog/entry/14328 EZ Collections, EZ Life] - Java
 
* [http://codeforces.com/blog/entry/14328 EZ Collections, EZ Life] - Java
 
* [https://github.com/SuprDewd/CompetitiveProgramming CompetitiveProgramming] - C++ (Github)
 
* [https://github.com/SuprDewd/CompetitiveProgramming CompetitiveProgramming] - C++ (Github)
 +
* [http://www.openfst.org/twiki/bin/view/FST/WebHome OpenFst] - C++, Shell
  
 
==See also==
 
==See also==
Line 138: Line 170:
 
* [https://scholar.google.com/citations?view_op=top_venues&hl=en&vq=eng_theoreticalcomputerscience Theoretical Computer Science] - Google Scholar Metrics (Top Publications)
 
* [https://scholar.google.com/citations?view_op=top_venues&hl=en&vq=eng_theoreticalcomputerscience Theoretical Computer Science] - Google Scholar Metrics (Top Publications)
 
* [http://www.scholarpedia.org/article/Algorithmic_information_theory - Algorithmic Information Theory] - Scholarpedia
 
* [http://www.scholarpedia.org/article/Algorithmic_information_theory - Algorithmic Information Theory] - Scholarpedia
 +
* [https://www.scriptol.com/programming/list-algorithms.php List of Algorithms (Scriptol)] - A complete list of all major algorithms (300) in any domain
 +
* [[wikipedia:List_of_algorithms|List of algorithms]] - Wikipedia
 
* [http://www.geeksforgeeks.org/top-algorithms-and-data-structures-for-competitive-programming/ Top 10 Algorithms and Data Structures for Competitive Programming] - Geeks for Geeks
 
* [http://www.geeksforgeeks.org/top-algorithms-and-data-structures-for-competitive-programming/ Top 10 Algorithms and Data Structures for Competitive Programming] - Geeks for Geeks
 
* [https://www.geeksforgeeks.org/theory-of-computation-automata-tutorials/ Theory Of Computation and Automata Tutorials] - Geeks for Geeks
 
* [https://www.geeksforgeeks.org/theory-of-computation-automata-tutorials/ Theory Of Computation and Automata Tutorials] - Geeks for Geeks

Latest revision as of 03:16, 1 January 2019

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.

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

See also[edit]

Other Resources[edit]