Glossary
For the exact definitions of the terms and for examples, please see the material linked by the terms.
A | B | C | D | E | F | G | H | I | K | L | M | N | O | P | Q | R | S | T | U | V
- adjacency list
fi: vieruslista
A data structure for representing graphs. In it, each vertex is associated with a list of its neighbours.
- adjacency matrix
fi: vierusmatriisi
A data structure for representing graphs. In it, the adjacency information between vertices is represented with a matrix.
- array
fi: taulukko
An elementary data structure. A fixed-size sequence of elements stored in consecutive memory locations.
External links: Wikipedia
- articulation point
See: cut vertex
- AVL tree
fi: AVL-puu
A special, balanced class of binary search trees. The balancing condition requires that the heights of the left and right subtrees of a node differ by at most one. The name AVL comes from the inventors of the data structure, Georgy Adelson-Velsky and Evgenii Landis.
- backtracking search
fi: peräytyvä hakeminen
An search procedure that tries to build a solution by recursively expanding a partial solution condidates to larger ones. Backtracks to the previous partial solution candidate if none of the expansions resulted in a solution.
- Bellman-Ford algorithm
fi: Bellman-Fordin algoritmi
An algorithm for computing single source shortest paths in edge-weighted directed graphs. It can handle negative edge weights and detect whether the graph contains a negative weight cycle.
- BFS
See: breadth-first search
- binary heap
fi: binäärinen keko
A binary tree data structure with some additional properties, used to implement priority queues and heapsort.
- binary search tree
fi: binäärihakupuu
Binary tree data structure in which each node is associated with an element. Additionally it holds that the elements in the left subtree of a node are less than or equal to the element of the node, and those in the right subtree are greater than or equal to that of the node.
- binary tree
fi: binääripuu
A rooted tree in which each node may only have a left child node and a right child node, both of which may be missing.
- bit array
See: bit set
- bit set
fi: bittivektori
A set data structure for elements that are, or can be easily mapped to, small integers.
- bit vector
See: bit set
- breadth-first search
fi: leveyshaku
An algorithm for traversing graphs.
- chaining
fi: ketjutus
A hash table collision resolution method using lists.
- closed hashing
See: open addressing
- clustering
fi: kasautuminen
A phenomenon occurring in hash tables using open addressing and (linear or quadratic) probing as the collision resolution method.
- collision
fi: yhteentörmäys
The event of two elements hashing to the same index in a hash table.
- connected component
fi: yhtenäinen komponentti
A maximal set of vertices in an undirected graph such that from each vertex in the set, there is a path to all other vertices in the set.
External links: Wikipedia
- counting sort
fi: laskentajärjestäminen
A sorting algorithm for sequences whose elements are small integers or can be seen as such.
- cryptographic hash function
fi: kryptografinen hajautusfunktio
A hash function that has some special properties, making it suitable for cryptographic applications.
External links: Wikipedia
- cut vertex
fi: leikkaussolmu
A vertex in an undirected graph whose removal increases the number of connected components.
- cycle
fi: sykli
A path in a graph which starts and ends in the same vertex.
- DAG
- depth-first forest
fi: syvyyshakumetsä
The subgraph consisting of the depth-first trees formed by running depth-first search multiple times so that all the vertices are visited.
- depth-first search
fi: syvyyshaku
An algorithm for traversing graphs.
- depth-first tree
fi: syvyyshakupuu
The tree subgraph consisting of the edges traversed by depth-first search from a single source vertex.
- deque
See: double-ended queue
- DFS
See: depth-first search
- digraph
See: directed graph
- Dijkstra’s algorithm
fi: Dijkstran algoritmi
A greedy algorithm for computing single source shortest paths in edge-weighted directed graphs (negative edge weights are not allowed).
- direct-access table
fi: suorahakutaulu
A map data structure for keys that are, or can be easily mapped to, small integers.
- directed acyclic graph
fi: suunnattu syklitön verkko
A directed graph that does not contain cycles.
External links: Wikipedia
- directed graph
fi: suunnattu verkko
A graph in which the edges are directed, meaning that each edge has a source and a target vertex.
- divide and conquer
fi: hajota ja hallitse
An algorithm design paradigm.
External links: Wikipedia
- double hashing
fi: kaksoishajautus
A method for producing hash table probe sequences in open addressing.
- double-ended queue
fi: pakka
A collection data structure. Similar to queue but also allows one to insert elements in the beginning and remove elements from the end.
- dynamic array
See: resizable array
- dynamic programming
fi: dynaaminen ohjelmointi
An algorithm design technique.
External links: Wikipedia
- exhaustive search
fi: kattava hakeminen
A search algorithm that goes through all feasible solution candidates in some way, and is able to provide a solution or to report that none exists.
- Fibonacci numbers
fi: Fibonaccin luvut
The sequence \(0,1,1,2,3,5,8,...\) of integers defined recursively by \(F_0 = 0\), \(F_1 = 1\), and \(F_n = F_{n-1}+F_{n-2}\) for \(n \ge 2\).
External links: Wikipedia
- forest
fi: metsä
A set of disjoint trees.
- generic programming
See: generics
- generics
fi: geneerinen ohjelmointi
- GPU
- graph
fi: verkko
A mathematical structure, or a data structure, consisting of vertices”vertex and edges between them.
External links: Wikipedia
- graphics processing unit
fi: grafiikkasuoritin
A processor type originally designed for performing computations specific to computer graphics. Nowadays used also for many other computing purposes.
External links: Wikipedia
- greedy algorithm
fi: ahne algoritmi
An algorithm that makes a locally optimal choise at each step. May not produce a globally optimum solution at the end.
External links: Wikipedia
- hash code
See: hash value
- hash function
fi: hajautusfunktio
A function that computes the hash value of the given input.
External links: Wikipedia
- hash table
fi: hajautustaulu
A data structure for implementing sets and maps by using a hash function.
External links: Wikipedia
- hash value
fi: hajautusarvo
The value produced by a hash function.
External links: Wikipedia
- heapsort
fi: kekojärjestäminen
A sorting algorithm that works by first building a heap of the elements, and then removing the elements from it in sorted order.
- in place sorting algorithm
fi: paikallaan järjestäminen
A sorting algorithm that stores only a constant amount of array elements outside the array at any given moment. Different variants of the definition are possible, please see the text.
- in-degree
fi: tuloaste
The number of edges coming in a vertex in a directed graph.
- independent set
fi: riippumaton joukko
A set of vertices in a graph so that there are no edges between any of them.
- independent uniform permutation hashing
fi: riippumaton tasainen permutaatiohajautus
A property in open addressing hashing: the probe sequence of each key is equally likely to be any of the \(m!\) possible probe sequences.
- inorder traversal
fi: läpikäynti sisäjärjestyksessä
A method for visiting all the nodes in a rooted tree, especially for binary trees. The current node is visited after the left child node has been recursively traversed, before the right child subtree is traversed.
- insertion sort
fi: lisäysjärjestäminen
A sorting algorithm.
External links: Wikipedia
- invariant
fi: invariantti
A property of a mathematical object that remains unchanged when the object is changed.
External links: Wikipedia
- Kosaraju’s algorithm
fi: Kosarajun algoritmi
A linear time algorithm for computing the strongly connected components of a directed graph.
External links: Wikipedia
- Kruskal’s algorithm
fi: Kruskalin algoritmi
A greedy algorithm for computing minimum spanning trees.
- level order traversal
fi: läpikäynti tasojärjestyksessä
A method for visiting all the nodes in a rooted tree. The nodes are visited level-wise, first the root, then the children of the root, then the children of the children of the root, and so on.
- lexicographical order
fi: sanakirjajärjestys
- linear probing
fi: lineaarinen kokeilu
A method for producing hash table probe sequences in open addressing.
- linked list
fi: linkitetty lista
A collection data structure. Each element is stored in a node, and each node has a reference to a successor node (“null” at the end of the list).
External links: Wikipedia
- load factor
fi: täyttösuhde, sv: belastningsfaktor
In resizable arrays, the ratio \(\frac{s}{c}\) between the number \(s\) of elements stored and the capacity \(c\) of the underlying array. In «hash tables”hash table|, the ratio \(\frac{n}{m}\), where \(n\) is the number of elements stored in a hash table and \(m\) is the number of entries in the hash table array.
- longest common subsequence
fi: pisin yhteinen osamerkkijono
Given two sequences, a common subsequence of largest length, where a subsequence is common for the sequences if its elements appear in the same order in both sequences.
External links: Wikipedia
In dynamic programming, the act of saving subproblem solutions, and then using the saved solutions instead of recomputing them if they are needed again in the future.
- merge operation
fi: lomitusoperaatio
The operation that merges two sorted sub-arrays into the sorted sub-array containing the elements of both sub-arrays.
- message digest
See: hash value
- node
See: vertex
NP
The family of decision problems that can be solved in polynomial time with a non-deterministic Turing machine.
- open addressing
fi: avoin osoittaminen
A hash table collision resolution method using probing.
- open hashing
See: chaining
- optimization problem
fi: optimointiongelma
A problem in which one is interested in finding a best possible solution.
- ordered map
fi: järjestetty kuvaus
A map data structure which maintains the order of the keys in the map, allowing efficient search for the smallest, largest, successor and predecessor keys.
- ordered set
fi: järjestetty joukko
A set data structure which maintains the order of the elements in the set, allowing efficient search for the smallest, largest, successor and predecessor elements.
- ordered tree
fi: järjestetty puu
A rooted tree in which the children of a node are ordered so that one of them is the first one, then the second one and so on.
- out-degree
fi: lähtöaste
The number of edges leaving a vertex in a directed graph.
- partitioning algorithm
fi: ositusalgoritmi
In quicksort, an algorithm that divides a sub-array in three parts with respect to the given pivot element.
- path
fi: polku
A sequence of vertices in a graph such that each pair of consecutive vertices in it is connected by an edge.
- path compression
fi: polkujen tiivistäminen
A method to obtain shallower representative trees in the union-find disjoint sets data structure.
- pivot element
fi: jakoalkio
In quicksort, the element with respect to which the partitioning algorithm partitions the current sub-array.
- postfix notation
- postorder traversal
fi: läpikäynti jälkijärjestyksessä
A method for visiting all the nodes in a rooted tree. The current node is visited after all the child subtrees are be recursively traversed.
- preorder traversal
fi: läpikäynti esijärjestyksessä
A method for visiting all the nodes in a rooted tree. The current node is visited before the child subtrees are traversed recursively.
- Prim’s algorithm
fi: Primin algoritmi
A greedy algorithm for computing minimum spanning trees.
- priority queue
fi: prioriteettijono
A collection data type that associates a priority to the elements and allows efficiently finding and removing the element with the largest priority.
- probe sequence
fi: kokeilujono
The order in which hash table indices are inspected in open addressing.
- pruning technique
fi: karsintamenetelmä
A technique that can detect that the current partial solution candidate cannot be extended a full solution in backtracking search.
- pseudocode
fi: pseudokoodi
An approach for describing algorithms in a human readable, informal way.
External links: Wikipedia
- quadratic probing
fi: neliöllinen kokeilu
A method for producing hash table probe sequences in open addressing.
- queue
fi: jono
A collection data structure. Allows one to “enqueue” (insert) elements at the end, and “dequeue” (remove) elements from the beginning of the queue. Similar to stack but with “first in, first out” semantics.
- radix sort
fi: kantalukujärjestäminen
A sorting algorithm for sequences whose elements are sequences of small integers (or can be seen as such).
- red-black tree
fi: punamusta puu
A special, balanced class of binary search trees. The nodes are colored either red or black so that a special balancing condition holds.
- rehashing
fi: uudelleen hajautus
The act of inserting keys in a hable into another hash table of different size.
- representative element
fi: edustaja-alkio
An element that represents a larger set of elements, especially in the union-find disjoint sets data structure.
- resizable array
fi: muuttuvamittainen taulukko
A collection data type that allows constant time random access, and adding and removing elements at the end in amortized constant time.
External links: Wikipedia
- reverse Polish notation
fi: käänteinen puolalainen notaatio
A mathematical notation in which operators follow their operands. For instance, the infix expression \(1 + (2 * 3)\) is written as “\(1\) \(2\) \(3\) \(*\) \(+\)”.
External links: Wikipedia
- rooted tree
fi: juurellinen puu
A tree in which one of the nodes is the root of the tree.
- rotation
fi: kierto
A local structural modification in binary search trees that preserves the binary search tree property.
- SCC
- selection sort
fi: valintajärjestäminen
A sorting algorithm.
External links: Wikipedia
- separate chaining
See: chaining
- simple uniform hashing
fi: yksinkertainen tasaisen hajautuksen oletus
A property in hashing: each key is equally likely to hash to a hash value independently of the other keys.
- spanning tree
fi: virittävä puu
A subgraph that is a tree and contains all the vertices of the graph.
External links: Wikipedia
- stable sorting algorithm
fi: vakaa järjestämisalgoritmi
A sorting algorithm that does not change the relative order of equal elements.
- stack
fi: pino
A collection data structure. Allows one to “push” (insert) and “pop” (remove) elements at the top of the stack. Similar to queue but with “last in, first out” semantics.
External links: Wikipedia
- strongly connected component
fi: vahvasti yhtenäinen komponentti
A maximal set of vertices in a directed graph such that from each vertex in the set, there is a path to all other vertices in the set.
External links: Wikipedia
- subgraph
fi: aliverkko
A graph \(G=(v',E')\) is a subgraph of the graph \(G = (V,E)\) if \(V' \subseteq V\) and \(E' \subseteq E\).
- template metaprogramming
See: generics
- templates
See: generics
- timestamp
fi: aikaleima
Information identifying the occurrence time of an event (either absolutely or relative to other events).
A special element inserted in a hash table in open addressing to mark a removed element.
- topological ordering
See: topological sort
- topological sort
fi: topologinen järjestys
A linear ordering of the vertices of a directed acyclic graph so that, for each edge, the source vertex is before the target vertex.
External links: Wikipedia
- tree
fi: puu
A mathematical structure, or a data structure, consisting of nodes and edges between them. An undirected graph that is connected and acyclic.
- truth assignment
fi: totuusjakelu
A function from the set of variables of a propositional formula to the Boolean values “false” and “true”.
- union-find
fi: yhdistä ja etsi
- vertex
fi: solmu
An element in graphs, possibly connected to others with edges between them. The term “node” is perhaps more commonly used on trees (undirected acyclic graphs).
- vertex attribute
fi: solmuattribuutti