Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
Algos
OCR-MEI algorithms
| Term | Definition |
|---|---|
| Node/Vertex | A point on the graph which can be connected |
| Arc/Edge | The line which joins two nodes. An arc must have a vertex at each end. |
| Graph | A collection of nodes joined by edges |
| Loop | An edge which has the same vertex at both ends |
| Order (of an arc) | Number of edges incident on an arc. (Loops count twice) |
| Connected | Every vertex is joined by a path to every other vertex |
| Simple | No loops and now repeated edges (UV and UV or UU) |
| Tree | A simply connected graph with the minimum number of arcs |
| Complete graph (not explicitly on spec) | A simply connected graph with the maximum number of edges. I.e. all pairs of arcs have an edge. |
| Bipartite | When the vertices partition into two sets and there are no edges connecting arcs within the SAME set. |
| Complete Bipartite graph | A simply connected bipartite graph with the max edges while still being bipartite. |
| Digraph | A graph with directed arcs. |
| Network | A weighted graph |
| Weight | A numerical value assigned to an edge. |
| Kruskal's | Continuously select the arc with the smallest weight which doesn't form a cycle until n-1 selected. |
| Prim's | Choose any node and add it to T. Choose the arc of minimum weight from T to non-T and add the node it connects. Continue until all nodes are in T. |
| Tabular Prims | Select a node from the columns. Cross out its row. Number 1. Select the lowest weighted arc from a numbered column not crossed out. Number the associated column and cross out its row. |
| Dijkstra's | Starting node is order 1 label 0. Fill in all adjoining nodes with path total path length on that route. Select the node with currently shortest length, next order. Repeat. |
| Critical Path analysis | Activities with times and predecessors. Times go on arcs, Vertices represent points in time. Immediate predecessors go into a vertex which the next activity comes out of. Single start and end node. |
| Dummy activity | Activity with weight of 0, represented by a dashed line. Needed to maintain the simple nature of the graph, and sometimes when an activity is a predecessor for 2. |
| Minimum project completion time | The longest length direct path from the start to the finish. Any activity along this path is critical. There maybe be multiple equal critical paths. Otherwise, activities have floats. |
| How to identify minimum project completion time. | Forward pass. Two boxes at each node. Label start 0. At each node, write on the earliest start time. This is the greatest time of the sum of the incoming node+arc pairs. Complete for every node. Cannot fill in without all predecessors. |
| Identifying critical path | Backward pass. Similar, from end backwards. When the forward and backward labels are equal, the node is on the critical path, and is a critical event. |
| Float + types+formula | Float - the time by which an activity can be delayed without effect minimum completion time. Independent and interfering. For activity IJ (latest time at J - earliest time at I - duration) |
| Independent def and formula | The float unique to an activity, not affecting the float of any other activities. (Earliest time at J - latest time at I - duration) or 0 if negative. |
| Interfering float def and formula | Float that has an impact on the float of other activities. Total float- independent float. |
| Representing critical path analysis | Cascade chart. Horizontal time scale, activities on Y. Bottom row is critical activities, non-critical placed at earliest possible start time. |
| Resource histogram | Shows how many workers are needed at each time. Sometimes activities require != 1 worker. |
| Scheduling | Moving activities so they are not necessarily at the earliest start time to manage worker numbers. No algo for this just intuit. |
| Transmission system (Flows) | Network flow from Source, S, to sink, T. Arcs have weights which represent capacity. Draw in one Supersource or Supersink if necessary. Arcs have inflows and outflows. |
| Cut | A cut partitions nodes into two distinct sets, one containing the source and the other the sink (wet and dry). A cut has capacity. This is the sum of capacities of of arcs from the wet to dry side ignoring the rest. |
| Cut - related theorem. | Maximum flow/ minimum cut theorem. The maximum flow is equal to the minimum cut capacity. If you can find a flow equal to a cut, this cut is a bottleneck and this must be the maximum flow. |
| How to find maximum flow. | Choose any viable path. Add the maximum flow of that path to the flow. Cross out any saturated pipes (Where flow=capacity) Repeat until no more viable paths. Total inflow to sink or outflow from source is max flow. Look for cut with this capacity |
| Exception to this | Sometimes you have to run a flow backwards through an otherwise saturated arc, effectively with a -1 flow through it to increase total flow |
| Optimal solution for an LP | Will always be at or include a vertex. Think of the profit equation as a line which is translated upwards, its maximum may be parallel to a constraint, or its max will be at a vertex. |
| Basic | A feasible solution includes 2 non-basic variables which are equal to 0. Other variables are basic and non-0. |
| Choosing simplex pivot | First column - Choose the most negative value in the P row. For the row, do the ratio check: RHS/pivot is minimised and entry is positive. |
| Multiple optimal solutions | Degenerate. There will be a non-basic column which has a 0 in the objective row. This can be iterated on to give another solution. |
| Minimising (2 Options) | You can maximise the negative of the objective function.. Or, same method but with the most positive value in the objective function. (same ratio test) |
| When there is an equality in simplex | Either use substitution to rewrite other equations, or write it as <= and >=. |
| Critical event correction | A critical event is an arc which joins two nodes where start time=end time and the difference in time of the two nodes is equal to the weight of the arc |
Created by:
pemmb