# 150 Graphs and Algorithms

## Iain Phillips

Lecture material is provisional and subject to change/additions.

## Algorithm Workbench

You can run the algorithms directly on these web pages by supplying suitable input. Alternatively you can download the code and run it yourself. The programming language used is Python.

### Shortest Path

The following algorithms are implemented:
• Dijkstra's algorithm
• Floyd's algorithm
Enter the distance matrix (n rows of n integers separated by spaces; diagonal elements should be 0, and 0 on off-diagonal elements is interpreted as no arc; the example in the lectures has been pre-entered):

Enter the start and finish nodes (numbers between 0 and n-1):
The Python module matrix.py.

### Searching

The following algorithms are implemented and numbers of comparisons calculated:
• Linear Search
• Modified Linear Search (for ordered lists)
• Binary Search
Enter the list (integers separated by spaces): Enter the number to be found:

### Sorting

The following algorithms are implemented and numbers of comparisons calculated:
• Insertion Sort
• Mergesort
• Quicksort
• Parallel Mergesort
• Odd/even Mergesort
Enter the list (integers separated by spaces):
The Python module list.py. A typical interactive session might be:
```% python
>>> from list import List
>>> a = List([1,2,3])
>>> a.binsearch(3)
>>> (2,2)
```
Here we assume that list.py is in the current directory. The answer (2,2) means that the item 3 was found at index 2, and the binary search took 2 comparisons.