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
Decision Year 1
AS Further Maths- Edexcel
| Question | Answer |
|---|---|
| What is an algorithm? | Finite sequence of step-by-step instructions carried out to solve a problem |
| What columns should you use for a trace table? | Step no. - Variables - Print |
| What does a round box mean in a flow chart? | Start/End |
| What does a box mean in a flow chart? | Instruction |
| What does a diamond mean in a flow chart? | Decision |
| How do you carry out a bubble sort? | Compare adjacent items. If they are in order, leave them. If they are not in order, swap them. The list is in order when a pass is completed without any swaps. |
| What do you need to remember at the end of a bubble sort? | Write the order once more- to show no change |
| How do you carry out a quick sort? | Select a central piot and split the items into two sub-lists. One sub-list contains items less than the pivot, the other, greater. You then keep selecting pivots until all items are in order. |
| What are the 3 bin packing algorithms? | first-fit, first-fit decreasing, full-bin |
| How do you calculate the lower bound of a bin-pack? | Sum the data and divide by how much can fit in one bin. Always round UP |
| How do you carry out a first-fit bin pack? | Place them in bins in the order they are given as. If an item goes over the max storage, move it to the next bin |
| How do you carry out a first-fit decreasing bin pack? | Re-write the list in decreasing order. Then place them in bins in order. If an item goes over the max storage, move it to the next bin |
| How do you carry out a full-bin pack? | Combined items so that they max out bins. Remaining items- use first-fit. |
| What is the order of the bubble and quick sort? | n² |
| How do you work out estimated times using the order of an algorithm? | (new amount of data / old amount of data)^(order index) x (time for old amount) |
| What is a node/ vertex? | Point on a graph |
| What is an edge/ arc? | Line segment of a graph |
| What is a vertex set? | List of vertices |
| What is an edge set? | List of edges |
| What is a subgraph? | A part of an original graph |
| What is the degree/ valency on a vertex? | Number of incident edges |
| What is a walk? | Route through the graph along edges from one vertex to the next |
| What is a path? | Walk where no vertex is visited more than once |
| What is a trail? | Walk in which no edge is visited more than once |
| What is a cycle? | A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once |
| What is a Hamiltonian cycle? | A cycle that includes every vertex |
| What is a connected graph? | A graph where all nodes are attached by arcs |
| What is a loop? | An edge which starts and finishes at the same vertex |
| What is a simple graph? | No loops and at most one edge connecting two vertices |
| What is a directed graph? | Graph where edges have a direction |
| What is the sum of the degrees? | 2 x no. edges |
| What is a tree? | A connected graph with no cycles |
| What is a spanning tree? | Subgraph which includes all the vertices and is a tree |
| What is a complete graph? | Every vertex is directly connected to all other vertices |
| What is an isomorphic graph? | Graphs which display the same information, just are drawn differently |
| What is an adjacency matrix? | Describes the number of arcs connecting each pair of vertices. (Vertices written along the side and top) |
| What is a distance matrix? | Matrix which describes the weight of each arc (Vertices written along the side and top) |
| What are the two algorithms used to calculate minimum spanning trees? | Kruskals and Prims |
| What is Kruskal's algorithm? | Sort all arcs into ascending order of weight. Select smallest to start the tree. Consider the next in the list, add it if it doesn't form a cycle. Repeat until all nodes are connected |
| What is Prim's algorithm (on a graph) ? | Choose any vertex. Select the smallest arc it is incident to, add it to the tree. Keep selecting the smallest possible arc (assuming it doesn't form a cycle). |
| What is Prim's algorithm (on a distance matrix) ? | Choose any vertex. Delete the row. Number the column of the vertex. Put a ring around the lowest undeleted entry. Delete the row. Number the column of the vertex ............ |
| What is Dijkstra's algorithm used for? | Finding the shortest path from S to T through a network |
| What is Dijkstra's algorithm? | Label the start S with the final label 0. Record a working value at every node that S connects to. (Replace working value if a smaller one is found). Select the smallest working value, this is now the final value. Work out all the working values... |
| How do you work out the shortest path after completing Dijkstra's algorithm? | Work backwards, arc is part of it if the working value-weight = working value of previous node |
| What is an eulerian graph? | A connected graph where all vertices have even valency |
| What is a semi-eulerian graph? | A connected graph where only two vertices have odd valency |
| What is the shortest route of an eulerian graph? | The total weight of the graph |
| What is the shortest route of an semi-eulerian graph? | The total weight of the graph + shortest path between odd vertices |
| What is the route inspection algorithm? | 1 identify odd vertices 2 consider all pairing 3 select smalled weight pairing 4 add a repeat of that pairing |
| What three things do you need to give to formulate a linear programming problem? | 1) Decision variable (x,y,z) 2) The objective, maximise/ minimise 3) The constraints (all inequalities) |
| What constraints won't be given in the question? | Greater-than or equal to zero constraints |
| What is the name for the region which satisfies the constraints? | Feasible region |
| How do you optimise an equation using the graphical method? | Align a ruler with the objective line and move it along the graph, the last point it touches = max, first = min |
| How do you optimise an equation using the vertex method? | Work out the co-ordinates of every vertex and plug those values into the objective. |
| What is the difference when a linear programming question asks for an integer solution? | Consider the integer points surrounding the optimal vertex. |
| What is a precedence table? | Table which shows which activities must be completed for others to start |
| What do arcs represent on a network (critical path analysis) ? | Activites |
| What do vertices represent on a network (critical path analysis) ? | Completion of those activities (events) |
| What are the names for the first and last nodes (critical path analysis) ? | Source and sink node |
| What is a dummy activity? | Shows dependecies between activites (no time or cost) |
| How many activities go between 2 event? | 1 only |
| How do you work out early event times? | Forward pass. (top box) Greatest value of all (total ) values entering the box |
| How do you work out late event times? | Backward pass. (bottom box) Smallest value of all (total) values leaving the box |
| How can you tell in an activity is critical? | The events on either side have equal late and early times and the largest event time - smallest = weight of activity arc |
| What is a critical path? | Path from source to sink containing only critical activities |
| How do you calculate total float? | latest finish time - duration - earliest start time |
| What is the float of a critical activity? | 0 |
| What is a Gantt (cascade) chart? | Graph which displays each activities earliest start time, earliest finish time and float |
Created by:
XanderMoore
Popular Math sets