# D1

Revision

- Created by: Katie Moffatt
- Created on: 05-04-11 17:34

## The Matching Algorithm

1. Put all possible matches on a bipartite graph

2. Start the matching, by matching as many of each vertices together, one to one

3. Start at an unmatched vertex

4. Create a path which alternates matched and unmatched edges and finishes with and unmatched vertex

5. Write BREAKTHROUGH and the alternating path out (A-1=B-2)

6. Change the staus of the alternating path and draw a new bipartite graph

7. Replace the matchings that have changed with the new ones

8. Draw and write out the final matching

## Kruskal's Algorithm

1. Select the shortest edge not in the the minimum spanning tree ( edges already selected )

2. Add this edge to the minimum spanning tree (highlight it) **UNLESS IT COMPLETES A CYCLE**

3. Repete 1. and 2. untill finished

**MUST LIST THE EDGES IN THE ORDER THEY ARE CHOSEN**

## Prim's Algorithm

1. Choose a starting vertex

2. Select the shortest edge connecting a vertex in the minimum spanning tree to one not in the minimum spanning tree

3. Add this edge to the minimum spanning tree (highlight it ) **UNLESS IT COMPLETES A CYCLE**

4. Repeat 2. and 3. until finished

**MUST LIST THE EDGES IN THE ORDER YOU CHOOSE THEM**

## Prim's Algorithm on a Matrix

1. Choose a column ( a place to start) and label column 1 and cross out row that corresponds

2. Select smallest edge in that column, circle it, cross out rest of row

3. Label column of the circled number

4. Select smallest edge (**NOT CIRCLED OR CROSSED OUT**) in the labelled columns, circle it, cross out rest of row

5. Repeat steps 3. and 4. until complete ( all columns are labelled/ highlighted)

6. List the edges in the order they were chosen and add up the total.

7. Draw the final network

## Linear Programming

1. Write out variables and set constraints, including non negativity constraints

2. Set out the objective function (e.g. Maximise P = 10x + 5y)

3. If necessary make a 3 variable problem into a 2 variable problem by using the relationship between the 3 variables

4. Draw a graph, showing constraints by hashing the regions not wanted

5. Label the feasible region (unshaded area) on the graph

6. Draw the objective line on the graph

7. Find the optimal (**MAX OR MIN**) point, by sliding ruler parallel to the objective line in the feasible region, at the last point it touches

8. Find the values of x and y

## Dijkstra's Algorithm

1. Label the starting point 0 and box it

2. Update all the working vertices

3. Find the shortest distance and box it

4. Repeat steps 2. and 3. until the end point is boxed

5. Work out and write the path by working backwards

## Route Inspection / Chinese Postman Algorithm

1. Identify the odd vertices

2. Write down the possible pair combinations

3. Form the distances for the pairs and add them up

4. Pick the set of pairs which is the shortest

5. Add up the original network total

6. Add the new pair total with the original network total

7. Draw in the new paths and identify the new route

## Sorting Algorithms - The Bubble Sort

1. Count the number of items

2. Compare the 1st and 2nd items

3. Swap if needed

4. Repeat steps 2. and 3. for all numbers until the largest is at the end

5. Repeat whole process for the remaining items (one less each time)

6. Stop when only one is not in its correct place **OR** entire pass with no swaps

**KEEP TRACK OF ALL SWAPS AND COMPARISONS IN 2 COLUMNS AT THE SIDE OF EACH PASS**

## Sorting Algorithms - The Shuttle Sort

1. Compare the 1st and 2nd number

2. If the 2nd is smaller than the 1st then move it to the left

3. Compare the 2nd and 3rd numbers

4. If the 3rd is smaller than the 2nd then move it to the left and compare and swap if smaller to those on the left

5. Repeat steps 4. and 5. until the largest number is at the end

**KEEP TRACK OF ALL SWAPS AND COMPARISONS IN 2 COLUMNS AT THE SIDE OF EACH PASS**

## Sorting Algorithms - Quick/Pivot Sort

1. Select the first number as the pivot and underline it

2. Compare pivot with all numbers to the right

3. If they are smaller move them to the left of the pivot if not keep them on the right hand side, box the pivot

4. The numbers at the start of each subgroup now becomes the pivot (underline it).

5. Repeat steps 2 and 3 with all numbers until all but one boxes are boxed

□ = fixed place

_ = pivot

## Comments