Computer Science

Computer science formalizes algorithms, programming-language structures, data abstractions, and correctness properties.

Data structures is the largest field, with over a quarter of the articles. It develops each structure with its invariants and the cost of its operations: search trees from binary search trees to AVL, red–black and B-trees, heaps, hash tables, tries and union-find. Graph algorithms come with their correctness and cost, from shortest paths by Dijkstra's algorithm, Bellman–Ford and Floyd–Warshall to spanning trees, flows and matchings by the algorithms of Kruskal, Prim, Edmonds–Karp and Gale–Shapley.

Process calculi, the second largest field, is mostly session types for the π-calculus, with subject reduction and progress for typed processes. Type systems and lambda calculi has Hindley–Milner type inference, where Algorithm W is sound and complete and finds principal types, relational parametricity for System F and System Fω, and strong normalization of the calculus of constructions. Programming-language semantics gives the IMP language operational and denotational semantics and a correct compiler to a stack machine.

Machine learning covers probabilistic graphical models such as Bayesian networks and hidden Markov models, Bayesian inference, supervised learning, and online learning and boosting, with Novikoff's perceptron mistake bound and the Freund–Schapire bound on the training error of AdaBoost.

• Data structures
• Graph algorithms
• Sorting and searching
• Dynamic programming
• Greedy algorithms and matroids
• Approximation algorithms
• Online algorithms
• Randomized algorithms and probabilistic analysis
• Parallel algorithms
• Algebraic and numerical algorithms
• Computational geometry
• String algorithms
• Heuristic search and planning
• Cryptography
• Databases
• Quantum algorithms
• Process calculi and behavioural equivalence
• Concurrent systems and protocols
• Programming language semantics
• Type systems and lambda calculi
• Program logics and verification
• Machine learning

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.