Decision 1 Useful Things to Remember

Algorithms:

Bubble sort- compare adjacent items in a list

Quick sort- select a pivot and split the items into two sub-lists greater and less than

Binary search- will sort an ordered list to find an item

First-fit bin packing- takes items in order given; quick but not good solution

First-fit decreasing bin packing- items sorted into descending order first; good solution and easy but no optimal solution

Full-bin packing- uses inspection to find items that will combine to fill bins; good solution but difficult in large amounts

Graphs and Networks:

Graph- consists of vertices (nodes) connected by edges (arcs)

Subgraph- part of a graph

Weighted graph (network)- each edge has a number associated with it

Degree/Valency/Order- the number of edges incident to a vertex

Path- finite sequence of edges, such that the end vertex of one edge is the start vertex of the next and no vertex is repeated

Walk- a path where you can return to vertices more than once

Cycle (circuit)- closed path where the end vertex of last edge is start vertex of first

Connected- a path between two vertices; graph connected if all vertices are

Loop- edge that starts and finishes at same vertex

Simple graph- no loops and not more than one edge connecting any vertices

Digraph- a graph with directed edges; edges have an associated direction

Tree- a connected graph with no cycles

Spanning tree- a subgraph including all vertices of the graph and is also a tree

Bipartite graph- edges join vertices in one set only to vertices in…