D1 Flashcards
What is a bubble sort?
Comparing adjacent items in a list
Explain how to do a quick sort?
Split list in half, keeping order write numbers below and above, then repeat
Use (n+1)/2 and round up
Explain how to do a binary search?
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 do you find the maximum iterations needed for a binary search?
Use log2^n and round up
How do you find the lower bound for bin packing?
Sum of heights/bin heights and round up?
Explain first fit bin packing and advantage and disadvantage?
- 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
Explain first fit decreasing bin packing and advantage and disadvantage?
Same as first fit but order items largest to smallest first
A: good solution/easy to do
D: not optimal solution
Explain full bin packing and advantage and disadvantage?
Use observation to find combinations to fill a bun + pack these first
A: often good/optimal solution
D: difficult + takes a long time
When is the solution optimal for bin packing?
When no. of bins used = lower bound
What is a graph?
Vertices connects by edges
What is a weighted graph?
When the graph has numbers on each edge
What does Euclide algorithm find?
HCF
What is a subgraph?
Part of a graph (same vertices and edges)
What is a path?
Finite sequence of edges, no repeated vertices
What is a walk?
Sequence of edges, can return to vertices once only
What is a cycle/circuit?
Closed path, end vertex of the last edge is the start vertex of the first edge
What is a connected graph?
A graph where a path can be found between any vertices (all connected)
What is a loop?
An edge that starts and ends at the same vertex
What is a simple graph?
No loops, no more than one edge connecting any pair of vertices
What is a diagraph?
When edges of graph have direction
What is a tree?
A graph with exactly one path between any two vertices
What is a spanning tree?
A subgraph which includes all original vertices but is also a tree
What is a bipartite graph?
A graph that only consists of two sets of vertices, where vertices only join vertices in the other set
What is a complete graph?
Every vertex is directly connected to every other vertex
What is a complete bipartite graph?
A bipartite graph where both sets are fully joined
What are isomorphic graphs?
Graphs that show the same information but are drawn differently
What is an adjacency matrix?
An adjacency matrix records the number of direct links between vertices
What is a distance matrix?
A distance matrix records weights on each of the edges ( put - if not joined)
Loop on adjacency matrix?
Counts as 2
What is a minimum spanning tree/MST/minimum connector?
A spanning tree such that total length of edges is as small as possible
Explain 4 steps of kruskals algorithm and what it does?
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
Explain 4 steps of prims algorithm and what it does?
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
Why are dummies needed?
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
Two common constraints?
X greater than or equal to zero
Y greater than or equal to zero
