Further Decision - Key Terms Flashcards
Algorithm (C1)
Finite sequence of step-by-step instructions carried out to solve a problem.
Trace Table (C1)
Used to record values of each variable as the algorithm
Instruction| n | A | B | C | Print
Step
Flow Chart Symbols (C1)
Stretched Circle - Start/End
Rectangle - Instruction
Rhombus - Decision (question)
Full-bin packing (C1)
Select ANY items to fill bins as much as possible.
Lower bound (C1)
Sum of values / bin size
Allows you to determine what the minimum no. of bins needed and thus whether your answer is optimal.
Optimal Solution (C1)
Solution that cannot be improved upon.
(e.g. Bin Packing = Smallest no. of bins)
Order (C1)
‘A function of its size.’ If order = f(n), then increasing size of the problem from n to m will increase the run time by a factor of f(m)/f(n).
Identifies how changes in the size of a problem affects the approximate run time of the algorithm.
Linear = n (e.g. Bubble sort
Quadratic = n^2 = Quadratic)
Cubic = n^3
Order (continued) (C1)
Increasing size of problem by factor k means:
- Linear alg. = k times longer
- Quadratic alg. = k^2 times longer
- Cubic alg. = k^3 times longer
Graph (C2)
Vertices/nodes connected by edges/arcs.
Weighted Graph (C2)
(Network)
Each edge has a ‘weight’ - number associated with it.
Vertex (C2)
(a.k.a node)
A point on a graph connected by edges.
Vertex/Edge Set (C2)
List of vertices/edges.
Edge (C2)
(a.k.a arc)
A line segment connecting vertices.
Subgraph (C2)
A graph of which the vertices belong to another bigger graph.
Degree (C2)
(Valency/Order)
The number of edges connecting to a vertex.
Walk (C2)
A route through a graph along edges going from one vertex to the next.
Path (C2)
A WALK in which no vertex is visited more than once.
Trail (C2)
A WALK in which no edge is visited more than once.
Cycle (C2)
A PATH in which the end vertex is the same as the start vertex.
Hamiltonian Cycle (C2)
A CYCLE including every vertex within it.
Eulerian Circuit (C2)
A TRAIL which traverses every arc and starts and ends at the same vertex.
Connected Graph (C2)
All vertices are connected to at least one other vertex.
Loop (C2)
An edge/arc that starts and finishes at the same vertex.
Simple Graph (C2)
A GRAPH with no loops & at most one edge is connecting to any pair of vertices.
Directed Edges (C2)
Edges which have a specific direction associated.
Directed Graph (C2)
(disgraph)
Graph with directed edges.
Undirected Graph (C2)
Edges have no direction.
Sum of degrees of vertices = 2 x no. of edges
Thus the number of odd vertices must be even or 0.
(a.k.a Euler’s handshaking lemma)
Tree (C2)
A connected graph with no cycles.
Spanning Tree (C2)
A subgraph which includes all vertices of the original graph and is a tree.
Complete Graph (C2)
A graph in which every vertex is directly connected by a single edge to each of the other vertices.
Isomorphic Graphs (C2)
Graphs which show the same information but are drawn differently.
Adjacency Matrix (C2)
Each entry describes the number of arcs joining the corresponding vertices.
(Symmetrical two-way table)
Distance Matrix (C2)
The matrix associated with a weighted graph and so the entries represent the weight of each arc, not the no. of arcs.
Planarity Graph (C2)
A graph that can be drawn in a plane such that, when drawn, no two edges meet except at a vertex.
Minimum Spanning Tree (C3)
A spanning tree such that the total length of its arcs is as small as possible.
Eulerian Graph (C4)
Network containing a trail including every edge that starts and ends at the same vertex. The trail is called a Eulerian Circuit.
Semi-Eulerian Graph (C4)
Network containing a trail including every edge but starts and finishes at different vertices.
[Any connected graph with exactly 2 odd vertices is Semi-Eulerian]
Tour (C5)
Walk which visits every vertex and returns to its starting vertex.
(May visit vertices more than once, thus is different to a Hamiltonian cycle)
Table of least distances (C5)
Distance matrix which shows the shortest path between any 2 points in a network.
(two-way table)
Residual Minimum Spanning Tree (C5)
MST for the resulting network after removing a vertex.
Decision Variables (C6)
Numbers of each of the things that can be varied. (e.g. 12x)
Objective (C6)
Aim of the linear programming problem.
Constraints (C6)
Features of a problem that prevent infinite numbers of each of the variables - these form inequalities.
Feasible Solution (C6)
Values for decision variables that satisfy the constraints.
Feasible Region (C6)
Region which contains all feasible solutions.
Optimal solution (C6)
Feasible solution which meets the objective. (May be >1 OS)
Slack variables (C7)
Represents the difference between the actual quantity and the maximum possible value.
→ Takes up ‘spare’ in function
→ Used to turn ≤ inequalities into equations
Artificial Variable (C7)
Used to ensure each constraint with a surplus variable contains a basic variable.
[Type of Surplus variable]
Surplus Variable (C7)
→ Take up ‘excess’ in function
→ Used to turn ≥ inequalities
into equations
Precedence/Dependence Table (C8)
Shows which activities must be completed before others are started.
‘Activity On Arc’ Network (C8)
Arc represent activities & nodes represent events (completion of activities)
Types of Node (C8)
Source = First
Sink = Final
Dummy Activity (C8)
Has no time or cost.
Aims to show dependencies between activities to avoid 2 arcs starting and ending at the same node.
ARC GOES FIRST, THEN DUMMY.
Event Times (C8)
Early = Earliest time of arrival at event, allowing for completion of all preceding activities.
Late = Latest time event can be left without extending time needed for project.
Critical Activity (C8)
Any increase in its duration results in a corresponding increase in duration of entire project.
Not every activity connect 2 critical events is a critical activity.
Critical Path (C8)
Longest path from source node to sink node contained in network which entirely follows critical activities.
Event times: Early = Late
THERE CAN BE > 1 CP.
Total Float (C8)
Amount of time that an activity’s start may be delayed without affecting the duration of the project.
TF = Latest finish time - duration - earliest start time
TF of a critical activity = 0
