﻿ Algorithms and Data Structures Glossary (Starting with "G")
 Home Free Glossaries Free Dictionaries Post Your Translation Job! Free Articles Jobs for Translators

#### Algorithms and Data Structures Glossary(Starting with "G")

By www.nist.gov,
Gaithersburg, Maryland, U.S.A.

paul . black [at] nist . gov

Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously

 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

### G

Galil-Giancarlo
Galil-Seiferas
gamma function
GBD-tree
GCD: see greatest common divisor
geometric optimization problem
global optimum
gnome sort
graph
graph coloring
graph concentration
graph drawing
graph isomorphism
graph partition
Gray code
greatest common divisor
greedy algorithm
greedy heuristic
grid drawing
grid file
Grover's algorithm

#### gamma function

(definition)

Definition: The gamma function of n, written Γ(n), is ∫ 0 e-xxn-1dx. Recursively Γ(n+1) = nΓ(n). For non-negative integers Γ(n+1) = n!.

Note: The gamma function is defined for all numbers whereas factorial is (strictly) only defined for non-negative integers.

Author: PEB

MathWorld's gamma function

#### GBD-tree

(data structure)

Definition: A generalized BD-tree, hence the name, which stores spatially extended objects as a hierarchy of minimum bounding boxes. It is a balanced multiway tree which serves as a spatial access method.

Generalization (I am a kind of ...)
spatial access method.

Note: After [GG98, page 211].

Author: PEB

Yutaka Ohsawa and Masao Sakauchi, A New Tree Type Data Structure with Homogeneous Nodes Suitable for a Very Large Spatial Database, Proc. Sixth International Conference on Data Engineering, February 5-9, 1990, Los Angeles, California, USA, pages 296-303.

#### geometric optimization problem

(definition)

Definition: An optimization problem induced by a collection of geometric objects.

Note: Since the variables and constraints come from physical situations, faster algorithms can often be developed. Adapted from [AS98, page 413].

Author: PEB

#### global optimum

(definition)

Definition: The best possible solution to a problem.

Note: Some search methods may get trapped in a local optimum and miss the global optimum.

Author: PEB

#### gnome sort

(algorithm)

Definition: Put items in order by comparing the current item with the previous item. If they are in order, move to the next item (or stop if the end is reached). If they are out of order, swap them and move to the previous item. If there is no previous item, move to the next item.

Generalization (I am a kind of ...)
stable sort, in-place sort.

Note: Complexity is O(n2) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning.

This can be seen as an insertion sort that only keeps track of the current item. After having moved an item backward into place, it "walks" forward, checking the order of items as it goes, until it reaches the next item is out of place, which is beyond where progress left off.

This can be seen as a bidirectional bubble sort that intelligently reverses direction, instead of making complete passes.

Dick Grune, the inventor, calls this "the simplest sort algorithm."

Author: PEB

#### graph

(data structure)

Definition: A set of items connected by edges. Each item is called a vertex or node. Formally, a graph is a set of vertices and a binary relation between vertices, adjacency.

Formal Definition: A graph G can be defined as a pair (V,E), where V is a set of vertices, and E is a set of edges between the vertices E ⊆ {(u,v) | u, v ∈ V}. If the graph is undirected, the adjacency relation defined by the edges is symmetric, or E ⊆ {{u,v} | u, v ∈ V} (sets of vertices rather than ordered pairs). If the graph does not allow self-loops, adjacency is irreflexive.

Specialization (... is a kind of me.)
directed graph, undirected graph, acyclic graph, directed acyclic graph, planar graph, biconnected graph, connected graph, complete graph, dense graph, sparse graph, hypergraph, multigraph, labeled graph, weighted graph, tree.

Aggregate child (... is a part of or used in me.)

Note: Graphs are so general that many other data structures, such as trees, are just special kinds of graphs.

A graph is like a road map. Cities are vertices. Roads from city to city are edges. (How about junctions or branches in a road? You could consider junctions to be vertices, too. If you don't want to count them as vertices, a road may connect more than two cities. So strictly speaking you have hyperedges in a hypergraph. If you want to allow more than one road between each pair of cities, you have a multigraph, instead. It all depends on how you want to define it.)

Another way to think of a graph is as a bunch of dots connected by lines. Because mathematicians stopped talking to regular people long ago, the dots in a graph are called vertices, and the lines that connect the dots are called edges. The important things are edges and the vertices: the dots and the connections between them. The actual position of a given dot or the length or straightness of a given line isn't at issue. Thus the dots can be anywhere, and the lines that join them are infinitely stretchy. Moreover, a mathematical graph is not a comparison chart, nor a diagram with an x- and y-axis, nor a squiggly line on a stock report. A graph is simply dots and lines between them---pardon me, vertices and edges.
Michael Bolton <mb@michaelbolton.net> 22 February 2000

Authors: PEB,PJT

Journal of Combinatorics dynamic surveys DS8 and DS9 are a bibliography and glossary of graphs. Deepayan Chakrabarti and Christos Faloutsos, Graph Mining: Laws, Generators, and Algorithms, ACM Computing Surveys, Vol. 38, March 2006, Article 2.
A great list of graph generators and their strengths and weaknesses.

#### graph coloring

(definition)

Definition: See vertex coloring, edge coloring, or k-coloring.

Author: PEB

#### graph concentration

(definition)

Definition: Contracting a graph by removing a subset of the vertices.

Note: From Algorithms and Theory of Computation Handbook, page 47-39, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### graph drawing

(classic problem)

Definition: The problem of representing a graph in a plane "neatly," for instance with a minimum number of edge crossings.

Author: PEB

#### graph isomorphism

(classic problem)

Definition: Determine if two graphs are isomorphic.

Author: PEB

#### graph partition

(classic problem)

Definition:Partition the vertices while keeping the cost of spanning edges low.

Aggregate child (... is a part of or used in me.)
graph.

Author: PEB

#### Gray code

(definition)

Definition: An ordering of 2n binary numbers such that only one bit changes from one entry to the next. Gray codes for 4 or more bits are not unique, even allowing for permutation or inversion of bits.

Aggregate parent (I am a part of or used in ...)
Karnaugh map.

Note: Gray codes are particularly useful in mechanical encoders since a slight change in position only affects one bit. Using a typical binary code, up to n bits could change, and slight misalignments between reading elements could cause wildly incorrect readings.

An n-bit Gray code corresponds to a Hamiltonian cycle on an n-dimensional hypercube.

A Gray code was used in a telegraph demonstrated by French engineer Émile Baudot in 1878. Frank Gray, a Bell Labs researcher, patented a method using the codes in 1953.

See the links for polynomial-time algorithms to convert between binary numbers and certain Gray codes.

Author: PEB

Image of a Gray code rotary railroad control.

Frank Gray, Pulse Code Communication, U.S. Patent 2,632,058, filed 13 November 1947, issued 17 March 1953.

#### greatest common divisor

(algorithm)

Definition: (1) The greatest integer which is a divisor of given positive integers. For instance, GCD(30, 42) = 6. (2) An algorithm to find the same.

Also known as GCD, highest common factor.

Note: After [CLR90, page 804].

Author: PEB

#### greedy algorithm

(algorithmic technique)

Definition: An algorithm that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems.

Specialization (... is a kind of me.)
Dijkstra's algorithm, Huffman coding, Kruskal's algorithm, optimal merge, Prim-Jarnik algorithm.

Note:Prim-Jarnik algorithm and Kruskal's algorithm are greedy algorithms that find the globally optimal solution, a minimum spanning tree. In contrast, any known greedy algorithm to find a Hamiltonian cycle might not find the shortest path, that is, a solution to the traveling salesman problem.

If there is no greedy algorithm that always finds the optimal solution for a problem, one may have to search (exponentially) many possible solutions to find the optimum. Greedy algorithms are usually quicker, since they don't consider the details of possible alternatives.

Author: PEB

#### greedy heuristic

(algorithmic technique)

Definition: Solve an optimization problem by finding locally optimal solutions.

Note: From Algorithms and Theory of Computation Handbook, page 1-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### grid drawing

(definition)

Definition: A graph drawing in which each vertex is represented by a point with integer coordinates.

Note: From Algorithms and Theory of Computation Handbook, page 9-23, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

#### grid file

(data structure)

Definition: A point access method which splits space into a nonperiodic grid. Each spatial dimension is divided by a linear hash. Small sets of points are referred to by one or more cells of the grid.

Note: After [GG98].

Author: PEB

 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

Published - April 2009

Find free glossaries at TranslationDirectory.com

Find free dictionaries at TranslationDirectory.com

Translation agencies are welcome to register here - Free!

Freelance translators are welcome to register here - Free!

Submit your glossary or dictionary for publishing at TranslationDirectory.com