6298832
Description
Flashcards by Trish Kelly, updated more than 1 year ago
|
Created by Trish Kelly
over 7 years ago
|
|
| 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 |
Want to create your own Flashcards for free with GoConqr? Learn more.