Brainscape's Knowledge GenomeTM

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


See full index

Further Maths > D1 > Flashcards

D1 Flashcards

1
Q

What is a bubble sort?

A

Comparing adjacent items in a list

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

Explain how to do a quick sort?

A

Split list in half, keeping order write numbers below and above, then repeat

Use (n+1)/2 and round up

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

Explain how to do a binary search?

A

1) Split ordered list in half ((n+1)/2 and round up)
2a) If T=m search is complete
2b) If Tm discard useless half and repeat until T is found

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

How do you find the maximum iterations needed for a binary search?

A

Use log2^n and round up

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

How do you find the lower bound for bin packing?

A

Sum of heights/bin heights and round up?

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

Explain first fit bin packing and advantage and disadvantage?

A
  • take items in given order, starting with 1 bin go along list putting all items into first available bin

Advantage: quick

Disadvantage: unlikely to lead to a good solution

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

Explain first fit decreasing bin packing and advantage and disadvantage?

A

Same as first fit but order items largest to smallest first

A: good solution/easy to do

D: not optimal solution

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

Explain full bin packing and advantage and disadvantage?

A

Use observation to find combinations to fill a bun + pack these first

A: often good/optimal solution

D: difficult + takes a long time

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

When is the solution optimal for bin packing?

A

When no. of bins used = lower bound

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

What is a graph?

A

Vertices connects by edges

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

What is a weighted graph?

A

When the graph has numbers on each edge

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

What does Euclide algorithm find?

A

HCF

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

What is a subgraph?

A

Part of a graph (same vertices and edges)

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

What is a path?

A

Finite sequence of edges, no repeated vertices

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

What is a walk?

A

Sequence of edges, can return to vertices once only

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

What is a cycle/circuit?

A

Closed path, end vertex of the last edge is the start vertex of the first edge

17
Q

What is a connected graph?

A

A graph where a path can be found between any vertices (all connected)

18
Q

What is a loop?

A

An edge that starts and ends at the same vertex

19
Q

What is a simple graph?

A

No loops, no more than one edge connecting any pair of vertices

20
Q

What is a diagraph?

A

When edges of graph have direction

21
Q

What is a tree?

A

A graph with exactly one path between any two vertices

22
Q

What is a spanning tree?

A

A subgraph which includes all original vertices but is also a tree

23
Q

What is a bipartite graph?

A

A graph that only consists of two sets of vertices, where vertices only join vertices in the other set

24
Q

What is a complete graph?

A

Every vertex is directly connected to every other vertex

25
Q

What is a complete bipartite graph?

A

A bipartite graph where both sets are fully joined

26
Q

What are isomorphic graphs?

A

Graphs that show the same information but are drawn differently

27
Q

What is an adjacency matrix?

A

An adjacency matrix records the number of direct links between vertices

28
Q

What is a distance matrix?

A

A distance matrix records weights on each of the edges ( put - if not joined)

29
Q

Loop on adjacency matrix?

A

Counts as 2

30
Q

What is a minimum spanning tree/MST/minimum connector?

A

A spanning tree such that total length of edges is as small as possible

31
Q

Explain 4 steps of kruskals algorithm and what it does?

A

Finds the MST

1) sort edges into ascending weight order
2) select arc of least weight to start tree
3) consider next arc of least weight:
- if it forms a cycle reject it
- if it doesn’t, add it
4) continue until all vertices are connected

32
Q

Explain 4 steps of prims algorithm and what it does?

A

Finds the MST

1) choose any vertex to start tree
2) select arc of least weight which joins vertex in the tree to a vertex not yet in the tree (if arcs have equal weight choose randomly)
3) repeat step 2 until all connected

33
Q

Why are dummies needed?

A

To show dependency when subsequent activities do not all depend on the same preceding activities

To show that an activity can be uniquely represented in terms of its end events

34
Q

Two common constraints?

A

X greater than or equal to zero

Y greater than or equal to zero

Further Maths (6 decks)

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