Algorithms and definitions Flashcards
What is an algorithm?
An algorithm is a finite sequence of step-by-step instructions carried out to solve a problem.
Describe the bubble sort algorithm.
In a bubble sort, you can compare adjacent items in a list.
The algorithm is;
1) Start at the beginning of the working list and move from left to right comparing adjacent items.
•If they are in order leave them.
•If they aren’t in order, leave them.
2) When you get to the end of the working list, the last item will be in its final position. This item is then no longer in the working list.
If you have made some swaps in the last pass, repeat step 1.
When a pass is completed without any swaps, every item is in its final position and the list is in order.
Describe the quick sort algorithm.
In a quick sort algorithm, you select a pivot, then split the items into two sub-lists.
The algorithm is;
1) Choose the item at the midpoint of the list to be the first pivot.
2) Write down all the items that are less than the pivot, keeping their order, in a sub-list.
3) Write down the pivot.
4) Write down the remaining items, those greater than the pivot) in a sub-list.
5) Apply steps 1 to 4 to each sub-list.
6) When all items have been chosen as pivots, stop.
What is a pass?
Going from the start to the end of the working list. The length of the working list reduces by 1 with each pass.
Going from the start to the end of the working list. The length of the working list reduces by 1 with each pass.
The first-fit algorithm works by considering items in the order they are given.
The algorithm is;
1) Take the items in the order given.
2) Place each item in the first available bin that can take it. Start from bin 1 each time.
Describe the first-fit decreasing algorithm.
The first-fit decreasing algorithm requires the items to be in descending order before applying the algorithm.
The algorithm is;
1) Sort the items so that they are in descending order.
2) Apply the first-fit algorithm to the reordered list.
Describe the full-bin packing algorithm.
Full-bin packing uses inspection to select items that will combine to fill bins. Remaining items are packed using the first-fit algorithm.
The algorithm is;
1) Use observation to find combinations of items that will fill a bin. Pack these items first.
2) Any remaining items are packed using the first-fit algorithm.
Describe the first-fit algorithm.
The first-fit algorithm works by considering items in the order they are given.
The algorithm is;
1) Take the items in the order given.
2) Place each item in the first available bin that can take it. Start from bin 1 each time.
What is the order of a bubble sort?
½𝑛(𝑛-1) or ½𝑛²-½𝑛. The bubble sort algorithm is said to have a quadratic order.
What is a vertex?
A vertex is a point on a graph. Vertices are sometimes called nodes.
What is an edge?
An edge is a line segment joining vertices. Edges are sometimes called arcs.
What is the vertex set?
The list of vertices comprising a graph.
What is a subgraph?
A graph, each of whose vertices belongs to the original graph and each of whose edges belong to the original graph.
It is simply a part of the original graph.
What is the degree of a vertex?
The degree or valency or order of a vertex is the number of edges incident. If the degree of a vertex is even, it is said to have even degree.
What is a walk?
A route through the graph along edges from one vertex to the next.
OR
A walk in a network is a finite sequence of edges such that the end vertex of one edge is the start vertex of the next.
What is a path?
A path is a walk in which no vertex is visited more than once.
What is a trail?
A trail is a walk in which no edge is visited more than once.
What is a cycle?
A cycle is 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 Hamiltonian cycle is a cycle that includes every vertex.
What does it mean for two vertices to be connected?
Two vertices are connected if there is a path between them.
