Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

AS Further Mathematics > D1 > Flashcards

D1 Flashcards

0
Q

Bubble Sort

Purpose

A

Sorts a list into ascending or descending order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
1
Q

[n]

A

The integer value of

Round to the nearest whole number

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Bubble Sort

Algorithm

A
  1. Starting at the beginning of the list compare adjacent values
    - if they are in order leave them
    - if not swap them
  2. When you get to the end of the list repeat step one, each repetition of step one is called a pass
  3. When a pass has been completed without any swaps the list is in order
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Quick Sort

Purpose

A

Sorts a list into ascending or descending order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Quick Sort

Algorithm

A
  1. Select the middle value as a pivot by circling it
  2. Write out the items that are lower than the pivot in the order they appear in the list before the pivot
  3. Write down the pivot in a square as a fixed value
  4. Write down the remaining items that would come after the pivot in the order that they appear in the list
  5. Each side of the pivot(s) is now treated as a separate sub lists
  6. For each sub list repeat steps 1-5
  7. Stop when all items are fixed values, in a square
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Binary Search

Purpose

A

To find an item in an ordered list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Binary Search

Algorithm

A

T is the value you are looking for
m is the value from the list
n is the number of items left in the list

  1. m = [n+1 / 2]th value
  2. -if m=T item is found, end
    • if mT discard m and all items before it
  3. Repeat steps 1 to 2 until T is found or the list is exhausted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Bin Packing

Purpose

A

Fitting items into a space

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Bin Packing

First Fit Algorithm

A
  1. Take the items in the order given

2. Place each item in the first bin that it will fit in starting from bin 1 each time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Bin Packing

First Fit Decreasing Algorithm

A
  1. Reorder the items so that they are in descending order, biggest first
  2. Apply the first fit algorithm to the new list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Bin Packing

Full Bin Packing Algorithm

A
  1. Pack the first bins with any combinations of items that will completely fill a bin
  2. Pack any remaining items using the first fit algorithm (not decreasing) using the original order given
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Graph

Definition

A

A graph consists of vertices/nodes connected by edges/arcs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Simple Graph

Definition

A

Contains no loops

No more than one edge between each pair of vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Weighted Graph

Definition

A

A graph that has a number or distance associated with each edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Su graph

Definition

A

A part of a bigger graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Degree / Valency / Order

Definition

A

The degree/valency/order of a vertex is the number of edges incident to it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Connected

Definition

A

Two vertices are connected if there is a path between them

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Path

Definition

A

A finite sequence of edges such that the end vertex of one edge in the sequence is the start vertex if the next edge in the sequence
No vertex is repeated

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Walk

Definition

A

A path in which you are permitted to repeat vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Cycle / Circuit

Definition

A

A closed path, the end vertex of the last edge is the start vertex of the first edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Loop

Definition

A

An edge that starts and finishes at the same vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Digraph

Definition

A

A graph that has directions associated with its edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Tree

Definition

A

A connected graph with no cycles

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Spanning Tree

Definition

A

A spanning tree of a graph, G, is a su graph which includes all of the vertices in G and is also a tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Minimum Spanning Tree

Definition

A

The minimum spanning tree of a graph, G, is the spanning tree of smallest weight that includes all of the vertices in G

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Bipartite Graph

Definition

A

A graph which consists of two superset sets of vertices set X and set Y
Edges can only connect vertices between the two sets not within them

26
Q

Isomorphic Graphs

Definition

A

Two graphs are isomorphic if they show the same information but drawn differently

27
Q

Adjacency Matrix

Definition

A

A table that records the number of direct links between vertices

28
Q

Distance Matrix

Definition

A

A table that records the weights of the direct links between vertices

29
Q

Complete Graph

Definition

A

n vertices directly connected by an edge to every other vertex
Notation kn

30
Q

Complete Bipartite Graph

Definition

A

Every vertex in set x is connected by an edge to every vertex in set y
Notation kx,y where x is the number of vertices in set X and y is the number of vertices in set Y

31
Q

Kruskal’s Algorithm

Purpose

A

Finds the shortest/cheapest/fastest way of linking all the nodes into one system
Finds the minimum spanning tree of a graph
It considers edges

32
Q

Kruskal’s Algorithm

Algorithm

A
  1. Write out all the edges in ascending order of weight
  2. Select the arc of least weight to start the tree
  3. Consider the next arc of least weight
    • if it would form a cycle reject it
    • if not add it to the tree
  4. Repeat step 4 until the tree is complete
33
Q

Prim’s Algorithm

Purpose

A

Finds the shortest/cheapest/fastest way of linking all the modes into one system
Finds the minimum spanning tree if a graph
Considers vertices
Can be applied to a graph or a distance matrix

34
Q

Prim’s Algorithm - Graph

Algorithm

A
  1. Choose any edge to start the tree
  2. Select the edge of least weight that joins a vertex in the tree to one not in the tree
  3. Repeat step two until the tree is complete
35
Q

Prim’s Algorithm - Distance Matrix

Algorithm

A
  1. Choose any vertex to start the tree
  2. Delete the row in the matrix for the chosen vertex
  3. Number the column of the chosen vertex
  4. Circle the lowest undeleted entry in any of the numbered columns
  5. The ringed entry is the next vertex to be considered
  6. Repeat steps 2 to 5 until all rows are deleted
36
Q

Dijkstra’s Algorithm

Purpose

A

Finds the shortest, cheapest or fastest route between two vertices

37
Q

Dijkstra’s Algorithm

Algorithm

A
  1. Number the first vertex and enter working values for all vertices connected to it
  2. Number the next vertex of shortest distance come the start and enter a final value
  3. Use this final value to enter working values for all vertices connected to it
  4. Repeat steps 2 to 3 until you reach the end vertex
  5. The final value for the end vertex is the shortest distance to it from the start
  6. To find the route work backwards for the end vertex
38
Q

Traversable

Definition

A

A graph is traversable if it can be drawn I one go without removing the pen from the paper, starting and finishing in the same place

39
Q

Semi-Traversable

Definition

A

A graph is semi-traversable if it can be drawn in one go without revving the pen from the paper, starting and finishing at different vertices

40
Q

Eulerian

Definition

A

A graph is eulerian if all the valences are even

A eulerian graph is always traversable

41
Q

Semi-Eulerian

Definition

A

A graph is semi-eulerian if exactly two of its vertices have and odd valency and all of the others are even
A semi-eulerian graph is semi-traversable

42
Q

Route Inspection / Chinese Postman Algorithm

Purpose

A

Finds the weight of the shortest route which traverses every arc at least once and returns to the starting point

43
Q

Route Inspection / Chinese Postman Algorithm

Algorithm

A
  • If a graph is eulerian the shortest route that traverse each edge and returns to the starting point is equal to the weight of the network
  • If a graph is semi-eulerian, repeat the shortest route between the two odd vertices and add to the total weight of the network
  • if there are more than two odd vertices:
    1. Consider the possible pairings of the odd vertices
    2. Select the combination of pairings which gives the smallest total weight
    3. Add the weight to the total weight of the network
44
Q

Dummy Activity

Purpose

A

Shows reliance

There can never be more than one activity between a pair of events

45
Q

Critical Activity

Definition

A

Any activity on the critical path

Increasing the duration of a critical activity will increase the duration of the whole project

46
Q

Critical Path

Definition

A

A path from the source to the sink node only following critical activities

47
Q

Source Node

Definition

A

The first event in a project

48
Q

Sink Node

Definition

A

The final event in a project

49
Q

Early Event Time

Definition

A

The earliest time an event can start

The biggest value, working from the source to the sink node

50
Q

Late Event a Time

Definition

A

The latest an event can start without delaying the project

The smallest number working from the sink node to the source node

51
Q

Total Float

Definition

A

The total float of an activity is the amount of time that it can be delayed by without affecting the duration of the project

52
Q

Total Float

Formula

A

TotalFloat = LateEventTime - Duration - EarlyEventTime

53
Q

Minimum Number of Workers

Formula

A

TotalDurationOfAllActivities / DurationOfTheProject

54
Q

Objective Function

Definition

A

The aim of the problem

To maximise or minimise an algebraic expression

55
Q

Constraints

Definition

A

Things that will prevent you from having an infinite number of each variable
Each constraint can be written as an inequality

56
Q

Feasible Region

Definition

A

The region that contains all of the combinations of variables that are possible after applying the constraints

57
Q

Optimal Solution

Definition

A

The feasible solution that meets the objective function

58
Q

Solving a Linear Programming Problem

Steps

A
  1. Define the variables
  2. State the objective functions
  3. Write the constraints as inequalities
  4. Plot the inequalities on a graph and label the feasible region
  5. Find the optimal solution
59
Q

Finding the Optimal Solution

Objective Line Method

A
  1. Set the objective function equal to any number
  2. Plot this line on the graph
  3. Move the line across the graph keeping the gradient the same
  4. To maximise take the vertex of the feasible region that the line crosses last
    To minimise take the vertex of the feasible region that the line crosses first
  5. Out the coordinates into the objective function to find the maximum/minimum value
60
Q

Finding the Optimal Solution

Vertex Testing Method

A
  1. Consider each vertex of the feasible region
    2 substitute the coordinates of each vertex into the objective function
  2. Identify the vertex that gives the maximum/minimum value
61
Q

Plotting Inequalities

≤ and ≥

A

Use a solid line _____________

62
Q

Plotting Inequalities

< and >

A

Use a dashed line —————

AS Further Mathematics (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions