Algorithm is a procedure accepting arguments of any data type that satisfies certain properties (invariant, concept). Data structure, or abstract data type, is an invariant-defined set of data types which is studied for the analysis of algorithms. The design, implementation and use of general algorithms is called generic programming.

In computational complexity theory, oracle is a black box that is able to produce a solution for any instance of a given computational problem. In optimization, first-order oracle is an oracle that provides first-order information of the objective, i.e. function value and (sub-)gradient, at a given point: $x \mapsto (f(x), f'(x))$.


Algorithm analysis

Sorting algorithms

Graph algorithms

Data structure

  1. Set: a collection of unique values.
  2. List (linked list): every element has a key and a reference, with linear structure and insertion or removal from anywhere during iteration.
    • Stack (FILO): a container with insert/push and delete/pop operation at one end (top).
    • Queue (FIFO, buffer): a container with insert/enqueue at one end (back) and delete/dequeue at another (front).
  3. Tree (hierarchy): every element/node has one parent except the root, and may have one value/key.
    • Heap (priority queue): The key of a parent node is always no greater/less than those of its children.
  4. Graph: mapping within a set which can represent connection, directed link, and weight.
  5. Associative array (map, dictionary): a collection of key-value pairs, where keys are unique.
    • hash table: a hash function separates each key into a separate bucket of an array.
    • search tree: ordered, optimized for search.
  6. Multimap: a collection of keys potentially associted with multiple values.


🏷 Category=Computation