The full bin packing algorithm is more likely to produce an optimal solution – using the least possible number of bins – than the first fit decreasing and first fit algorithms. It works by matching object so as to fill as many bins as possible. Suppose boxes of heights 0.2, 1.4, 0.4, 0.8, 1.1, 1.0, […]

# Archive | D1

## An Algorithm for Determining Whether or Not a Graph is Planar

A graph is planar if it can be drawn in such a way that no arc crosses any other arc. There are algorithms for determining whether or not a graph is planar. The algorithm below can only be applied to graphs that have a Hamiltonian cycle (a cycle that passes through every vertex of the […]

## The Russian Peasant Algorithm

The Russian Peasant Algorithm multiplies two numbers together. The steps are: 1. Write down the two numbers in the two columns of a table. 2. Divide the number in column 1 by 2 and write the result in the second row below the first number, ignoring decimals and remainders. 3. Multiply the number in column […]

## The Order of an Algorithm

Suppose in a room full of people, every person is to shake hands with every other person. If the are people, a particular persona shakes hands with all the otherpeople. The shaking of hands is repeated until all thepeople have shaken hands with the otherpeople. It might be thought there arehandshakes altogether. In fact, we […]

## Constraints in Linear Programming

Deriving constraints in linear programming can be a consuming affair. The question must be properly read and understood. Below are examples of how to derive typical constraints. Example: A factory produces two cars, A and B. Each A car requires 3 hours of labour and each B car requires 5 hours. There are 480 hours […]

## Finding Conditions on Distances With Djikstra’s Algorithm

Using Djikstr’s algorithm we can find the least distance from one point to another in a network. If the network contains unknown distances however, and we know which is the shortest route, we may be able to find conditions on the unknown length. The network below contains the unknown distance Suppose we know that the […]

## Kruskal’s Algorithm in Table Form

Kruskal’s algorithm for the minimum spanning tree has a table equivalent. This is useful for large problems where drawing the network diagram would be hard or time-consuming. The table algorithm is also very suitable for automation. Kruskal’s table algorithm has the following steps. Choose the smallest number (arc length) in the table. Cross out the […]

## Flow Charts

A flow chart presents a series of instruction s to implement an algorithm in graphical form. A flow chart contains three types of boxes: The boxes are connected with arrows to point the way through the flowchart. Decision boxes may ask a question, which require a yes or no answer. One of the answers may […]

## The Shuttle Sort Algorithm

The Shuttle Sort is similar to the Bubble Sort – in each pass through the numbers, we compare the andnumbers. It is different in that if we have to swap them, indicated by dashes in the table below. We then compare the smallest of this pair with the preceding number, and swap if necessary. Each […]

## The Quick Sort Algorithm

The mid-point of a list has position [½(N+1)] where [x] is the smallest integer greater than or equal to x e.g. for 3, 6, 7, 11, 15 [½ (5+1)] = [3] = 3 mid-point = 7 for A, C, Y, B, D, R [½ (6+1)] = [3½] = 4 mid-point = B Step […]