D1 Definitions


Definitions for Decision 1 Edexcel Maths
Trish Kelly
Flashcards by Trish Kelly, updated more than 1 year ago
Trish Kelly
Created by Trish Kelly almost 8 years ago

Resource summary

Question Answer
Algorithm Set of precise instructions which if followed will solve a problem
Bubble-sort 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.
Quick-sort 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.
First-fit algorithm Taking the boxes in the order listed, place the next box to be packed in the first available bin. Repeat.
First-fit decreasing algorithm Order list so it is decreasing. Then do first-fit algorithm
Binary-search 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
Show full summary Hide full summary


All AS Maths Equations/Calculations and Questions
Core 2 AS level maths formulae OCR
AS level Maths Equations to Remember
Gurdev Manchanda
Ordinary Differential Equations
Elliot O'Leary
Maths C4 Trig formulae (OCR MEI)
Zacchaeus Snape
Elliot O'Leary
Elliot O'Leary
Using GoConqr to study Maths
Sarah Egan
The Weimar Republic, 1919-1929
A Level Chemistry Unit 1 - Organic Chemistry