# Archive | D1

## First Fit Decreasing Algorithm

Firstly, reorder the items so that they are in decreasing order. Then apply the first-fit algorithm to the reordered list. The reordered list (using a sorting algorithm if necessary): 15 14 9 9 8 8 7 7 6 6 5 The are packed as in the following diagram. With each being fitted into the first […]

## Critical Path Analysis – A Brief Explanation

Critical path analysis is algorithm that allows large projects to be planned. Each projects consists of a series of activities that must be completed. Before an activity can be started, certain other activities must be completed. The algorithm allows the ordering of activities, maybe doing several activities at the same time, so that the project […]

## Bin Packing Algorithms – First Fit Algorithm

We are seeking to pack bins (of given size) with various items. To find the lower bound, sum the numbers to be packed and divide this total by the size of the bin. The lower bound is the least integer greater than or equal to the result. Example Pack the following items in bins of […]

## Dijkstra’s Algorithm

Dijkstra’s algorithm is used to find the shortest path tree from a given node to any (or every) other node in a network. Dijkstra’s algorithm requires that each node in the network be assigned values (labels). The labels are assigned in order of distance from the starting point, with the labels assigned as we work […]

## Terminology

Graph – A visual representation of a set objects and relationships. Each member of X is represented as a vertex or node. Relationships are represented by edges or arcs.Vertex or Node – A point representing a member of the set.Edge or Arc – A link between vertices. An edge must have a vertex at each […]

## Kruskal’s Algorithm

Kruskal’s algorithm is a method of find the minimum spanning tree for a network. The network is separated completely into it’s constituent arcs. Arcs are selected in order of magnitude, shortest first, and added to the tree, with the poviso that any arc added does not form a cycle. It must be noted, that unlike […]

## Complete Graphs

A complete graph is such that every pair of vertices must be connected by a single edge. The above diagram is of a complete graph with 6 vertices. We can to find out the total number of edges in this graph. We could list all possible edges in terms of the vertices they connect.: AB, […]

## The Bubble Sort Algorithm

We apply this algorithm to sort a jumbled list into order. The list might be a list of numbers, letters, both or some other type. Each member of the list has a fixed place in a hierarchy compared to the others. If our list is a list of letters, the hierarchy would be alphabetical order. […]

## Vertex Testing

Solving a linear programming problem using the graphical method may give non integer solutions. Such solutions may not be practical, and we must look for integer solutions for each variable. The process of looking for integer solutions is called vertex testing. Suppose we have solved the linear programming problem: Maximisesubject to the constraintsand The graphical […]

## Eulerian From Non – Eulerian Graphs

Any network containing odd nodes is non – Eulerian. This means every arc cannot be traced just once, returning to the starting point and returning to the start point. Such a route, from a point traversing every arc once and returning to the start point, is called an Eulerian path. A network containing odd arcs […]