Ioannis Kourouklides
Don't have an account?
Register
Register
in: Algorithms, Informatics Competitions, Artificial Intelligence

Changes: Algorithm

Back to page
Edit
Tags: Visual edit apiedit
mNo edit summary
Tag: Visual edit
(38 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
This page contains resources about [https://en.wikipedia.org/wiki/Algorithm Algorithms] in general.
 +
This page contains resources about [https://en.wikipedia.org/wiki/Algorithm Algorithms]  and [https://en.wikipedia.org/wiki/Theory_of_computation Theory of Computation] in general.
   
 
More specific information is included in each subfield.
  
More specific information is included in each subfield.
Line 5: Line 5:
 
==Subfields and Concepts==
  
==Subfields and Concepts==
 
''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===
  +
''(It includes topics of [[International Olympiad in Informatics]] and some others)''
  ⚫
* Divide and Conquer Algorithm
 
* Sorting 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
  
* Search Algorithms
  +
** Breadth First Search (BFS)
⚫
* Graph Algorithms
  
  +
** Depth First Search (DFS)
  +
*[[Graph Theory|Graph]] and Tree Algorithms
  +
** Minimum Spanning Tree
  ⚫
* Hashing Algorithms
  ⚫
* Randomized Algorithms
  +
* [[Cryptography |Number Theory and Cryptography Algorithms]]
  +
** Chinese Remainder Theorem
  +
  +
=== Advanced Topics ===
  +
* [[Quantum Computation|Quantum Algorithms]]
  +
* [[Game Theory|Game Theory Algorithms]]
 
* [[Optimization |Optimization Algorithms]]
  
* [[Optimization |Optimization Algorithms]]
  +
** [[Evolutionary Computation]]
  ⚫
*** Genetic Algorithms
  +
** Greedy Algorithms
  +
** Dynamic Programming / Optimal [[Control Theory|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|Machine Learning Algorithms]]
  
* [[Machine Learning|Machine Learning Algorithms]]
  +
* [[Statistical Learning Theory|Learning Theory]]
⚫
* Compression Algorithms
  
  +
** Computational Learning Theory
−
* Regular Expressions
  
  +
** Statistical Learning Theory
  +
** Algorithmic Learning Theory
  +
* [[Information Theory|Data Compression Algorithms]]
 
* Algorithms on Strings
  
* Algorithms on Strings
 
* [[Digital Signal Processing|Digital Signal Processing Algorithms]]
  
* [[Digital Signal Processing|Digital Signal Processing Algorithms]]
  +
** [[Digital Image Processing|Digital Image Processing Algorithms]]
−
** Fast Fourier Transform
  
  +
* Algorithmic [[Information Theory]]
−
** Discrete Hilbert Transform
  
  +
** Kolmogorov Complexity / Algorithmic Complexity
−
** Spectral Peak Location Algorithm
  
  +
** Algorithmic Probability / Solomonoff Probability
−
** Frequency Demodulation Algorithm
  
  +
** Universal Search (by Levin)
⚫
** Stable Goertzel Algorithm
  
  +
** Algorithmic Randomness (by Martin-Lof)
−  
  +
** Solomonoff's Theory of Inductive Inference
−
* NP-Completeness
  
  +
** 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==
  
==Online Courses==
 
===Video Lectures===
  
===Video Lectures===
  +
* [https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/ Introduction to Algorithms by Erik Devaine and Srinivas Devadas]
−
*
 
   
 
===Lecture Notes===
  
===Lecture Notes===
  +
* [http://www.cs.duke.edu/courses/fall10/cps130/lectures.html Algorithms by Piotr Idyk]
−
*
 
  +
* [http://jeffe.cs.illinois.edu/teaching/algorithms/ Algorithms by Jeff Erickson]
  +
* [https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2012/index.htm Design and Analysis of Algorithms by Dana Moshkovitz and Bruce Tidor]
  +
* [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]
   
 
==Books==
  
==Books==
  +
''See also [https://en.wikipedia.org/wiki/Theory_of_computation#Further_reading 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. ([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.
 
*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.
 
*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==
  +
* [http://www.sanfoundry.com/1000-cpp-algorithms-problems-programming-examples/ C++ Algorithms, Problems & Programming Examples]
−
*
  
  +
* [https://www.codeproject.com/Articles/177363/Searching-and-Sorting-Algorithms-via-C Searching and Sorting Algorithms via C#]
  +
* [https://github.com/aalhour/C-Sharp-Algorithms C-Sharp-Algorithms] - Github
  +
* [https://github.com/OmkarPathak/pygorithm pygorithm] - Python (Github)
  +
* [https://github.com/TheAlgorithms TheAlgorithms] - C++, Python, Java, C#, C, Scala, Go, Javascript, Ruby (Github)
  +
* [http://codeforces.com/blog/entry/14328 EZ Collections, EZ Life] - Java
  +
* [https://github.com/SuprDewd/CompetitiveProgramming CompetitiveProgramming] - C++ (Github)
   
 
==See also==
  
==See also==
  +
*[[International Olympiad in Informatics]]
⚫
*[[Logic]]
  
−
*
  
   
 
==Other Resources==
  
==Other Resources==
  +
* [https://scholar.google.com/citations?view_op=top_venues&hl=en&vq=eng_theoreticalcomputerscience Theoretical Computer Science] - Google Scholar Metrics (Top Publications)
⚫
* [[Category:Algorithms]]
  
  +
* [http://www.scholarpedia.org/article/Algorithmic_information_theory - Algorithmic Information Theory] - Scholarpedia
  +
* [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/dynamic-programming/ Dynamic Programming] - Geeks for Geeks
  +
* [https://www.geeksforgeeks.org/traveling-salesman-problem-tsp-implementation/ Traveling Salesman Problem (TSP) Implementation]
  +
* [https://github.com/lnishan/awesome-competitive-programming Awesome Competitive Programming]
  +
* [https://www.hackerrank.com/domains/algorithms/ HackerRank - Algorithms challenges]
  +
* [https://www.hackerearth.com HackerEarth]
  +
  +
[[Category:Algorithms]]
  +
[[Category:Informatics Competitions]]
  +
[[Category:Artificial Intelligence]]

Revision as of 14:54, 28 April 2018

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

Community content is available under CC-BY-SA unless otherwise noted.