Created by Trish Kelly
almost 8 years ago


Question  Answer 
Algorithm  Set of precise instructions which if followed will solve a problem 
Bubblesort algorithm  To sort a list compare adjacent members of the list, moving from left to right, and switch them if they are in the wrong order. Continue until pass produces no change in list. 
Quicksort alogorithm  Select middle as pivot. Write all numbers smaller than pivot on left, bigger on right. Take middle of each 2 lists as pivot and repeat until only one number left. 
Firstfit algorithm  Taking the boxes in the order listed, place the next box to be packed in the first available bin. Repeat. 
Firstfit decreasing algorithm  Order list so it is decreasing. Then do firstfit algorithm 
Binarysearch algorithm  Applied to search an ordered list. Compare required item with middle. If required is before then reject bottom half, if after reject top half. Repeat until required item is found or no items left to check. 
Graph G  Consists of a finite number of points (called vertices/nodes) connected by lines (edges/arcs) 
Path  Finite sequence of edges such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once 
Cycle (or circuit)  Closed path i.e the end vertex of the last edge is the start vertex of the first edge 
Hamiltonian cycle  Cycle that passes through every vertex of the graph once and only once and returns to its start vertex 
Eulerian cycle  Cycle that includes every edge of a graph exactly once 
Vertex set  Set of all vertices of a graph 
Edge set  Set of all edges of a graph 
Subgraph (of a graph)  Subset of the vertices together with a subset of edges 
Connected (vertices)  Two vertices are this if there is a path between them 
Connected (graph)  A graph is this if all pairs of its vertices are connected 
Simple graph  When there is no edge with the same vertex at each end i.e no loops, and not more than one edge connecting any pair of vertices 
Degree (or valency or order)  The degree of a vertex is the number of edges connected to it 
Directed edges/digraph  When the edges of a graph have a direction associated with them. 
Tree  Connected graph with no cycles 
Spanning tree  Of a graph G, is a subgraph that includes all the vertices of G and is also a tree 
Bipartite graph  Consists of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set 
Kr,s Graph  When in a graph there are r vertices in X and s vertices in Y and every vertex in X is joined to every vertex in Y. 
Minimum spanning tree/minimum connector  A spanning tree of a connected and undirected graph such that the total length of its edges is as small as possible 
Kruskal's algorithm  Builds a minimum spanning tree by adding one edge at a time to a subgraph. At each stage the edge of smallest weight is chosen provided that it does not create a cycle with edges already chosen. 
Prim's algorithm  Builds minimum spanning tree by adding on vertex at a time to a connected subgraph. The new vertex to be added is the one which is nearest to any vertex already in the subgraph 
Dijkstra's algorithm  Obtains the shortest route from the initial vertex to any other vertex in a network. At each stage a fresh vertex is assigned a final which gives the shorted distance from the initial vertex to that vertex 
Want to create your own Flashcards for free with GoConqr? Learn more.