Flashcards in Rest of Decision Deck (103)
Loading flashcards...
1
What is an algorithm?
A finite sequence of step-by-step instructions carried out to solve a problem
2
What does an oval shaped box mean in a flow chart?
The start/end
3
What does a rectangular box mean in a flowchart?
It’s an instruction
4
What does a diamond shaped box mean in a flowchart?
A decision
5
Describe how to carry out a bubble sort
You compare adjacent items in a list:
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
6
Describe how to carry out a quick sort
You select a pivot then split the items into two sub-lists:
One sub list contains items less than the pivot
The other sub list contains items greater than the pivot
You then select further pivots from within each sub list and repeat the process
7
What are the three bin packing algorithms?
First fit
First fit decreasing
Full bin
8
Describe how to carry out first fit bin packing
Take the items in the order given
Place each item in the first available bin that can take it. Start from bin one each time
9
What is the advantage/disadvantage of first fit bin packing?
Ad: It is quick to implement
Dis: It is not likely to lead to a good solution
10
Describe how to carry our first fit decreasing bin packing
Sort the items so that they are in descending order
Apply the first fit algorithm to the re-ordered list
11
What are the advantages/disadvantages of first fit decreasing bin packing?
Ad: You usually get a fairly good solution. It is easy to implement
Dis: You may not get an optimal solution
12
Describe how to carry out full bin packing
Use observation to find combinations of items that will fill a bin. Pack these items first.
Any remaining items are packed using the first fit algorithm
13
What are the advantages/disadvantages of full bin packing?
Ad: You usually get a good solution
Dis: It is difficult to do, especially when the numbers are plentiful and awkward
14
What is the order of an algorithm?
Tells you how changes in the size of a problem affect the approximate time taken for its completion
15
What order is bubble sort?
Quadratic: 0.5(n-1)n
16
In any undirected graph, the sum of the degrees of the vertices equals...?
2 x the no. of edges
17
What is Euler’s handshaking lemma?
The number of orders vertices must be even, including possibly zero
18
What is a planar graph?
One that can be drawn in a plane such that no two edges meet except at a vertex
19
What is a minimum spanning tree?
A spanning tree such that the total length of it arcs is as small as possible
20
Which algorithms find the minimum spanning tree?
Kruskal’s (list all edges) and Prim’s (either pick one node on the graph, and find MST. Or use distance matrix)
21
What is the main difference between Kruskal’s and Prim’s?
Kruskal’s looks at edges
Prim’s looks at nodes
22
What can Dijkstra’s algorithm be used for?
Find the shortest path from the start vertex, to any other vertex in the graph
23
Floyd’s algorithm: explain how you know that the graph contains directed edges, (given the distance table and route table)
The distance table is not symmetrical about the leading diagonal
24
What is the difference in output between Floyd’s algorithm and Dijkatra’s?
The output of Floyd’s gives the shortest distance between every pair of nodes
The output of Dijkstra’s gives the shortest distance from the start mode to every other node
25
Floyd’s algorithm is applied to an n x n distance matrix. State the number of comparisons that are made with each iteration
(n-1)(n-2) = n^2 - 3n + 2
26
What is the order of Floyd’s algorithm?
Cubic
27
What is an Eulerian graph?
One which contains a trail that includes every edge and starts and finishes at the same vertex. This trail is called an Eulerian circuit. Any connected graph who is vertices are all even is Eulerian
28
What is a semi-Eulerian graph?
One which contains a trail that includes every edge that starts and finishes at different vertices. Any connected graph with exactly two odd vertices is semi-Eulerian
29
If all the vertices in a network have even degree, then the length of the shortest route will be…?
The total weight of the network
30
