First, an acknowledgement to Prof. Wayne Brown from the University of Arizona whose well written lesson Introduction to Algorithmic Thinking forms a significant basis of the statements made here, including verbatim phrases.

Properties of algorithms are as follows:

1. An algorithm does not solve a problem; instead, it gives a set of statements or instructions to find a solution to a problem.

For example, the quadratic formula is an algorithm for finding the roots of a quadratic equation. It does not solve the problem, but rather, if you plug in the coefficients of the expanded form of the quadratic polynomial, you get the two roots.

Similarly, Dijkstra's algorithm give you the shortest path between two points on a map. It does not examine all possible paths between the starting location and the destination, but rather it is a set of instructions which, if followed, gives you the shortest path. The computer that steps through this algorithm does not know why this algorithm finds the shortest path; instead, by following the statements or instructions, the resulting path happens to be the shortest path.

2. There are usually many different algorithms that solve the same problem.

Even in the projects for this course, you will find that there are different algorithms for finding a solution to the same problem. For example, to determine if a number is divisible by $100$, you can either perform long division and see if the remainder is zero, or more easily check if the last two digits are $00$.

In secondary school, you saw the quadratic formula, an algorithm for finding the roots of a quadratic polynomial in expanded form:

$\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$.

There is, however, another formulation by rationalizing the numerator:

$\frac{-2c}{b \pm \sqrt{b^2 - 4ac}}$.

This formula, too, gives both roots, and in your course on numerical analysis, you will find why this formula, under certain circumstances, is better than the formula you memorized from secondary school.

3. Not all algorithms are equally efficient.

Different algorithms may find the same solution to a problem, but one may be more efficient than another. Suppose, for example, you'd like to sort $42$ objects in Figure 1 from smallest to largest.

Figure 1. Forty-two objects to be sorted.

One algorithm is as follows:

1. Find the largest entry and move it to the last location.
2. Find the next largest entry and move it to the second-last location.
3. Continue this procedure until the objects are sorted from smallest to largest.

After performing three steps (depending on how you get the next-largest object to the end of the list), the objects now look like that seen in Figure 2.

Figure 2. The objects in Figure 1 after three steps of moving the next-largest to the end.

After an additional thirty-nine steps, the list of objects will be sorted from smallest to largest.

On the other hand, consider the following algorithm:

1. Pick a random entry (say the one in the middle).
2. Separate the remaining entries into two groups: those smaller than the chosen entry, and those larger.
3. On each of these two groups, reapply this algorithm, returning to Step 1.

Now, after three steps, the list of objects look like that shown in Figure 3.

Figure 3. The objects in Figure 1 after three steps of selecting and grouping.

This is an algorithm called quicksort. If you look the list, it already looks significantly closer to be sorted from smallest to largest than that shown in Figure 2; even though getting to the third step required approximately the same amount of work.

4. To be useful, it should be clear that the algorithm will ultimately finish.

Some algorithms will not work under certain circumstances. For example, one rule for getting through a maze is to always follow the left-hand wall. Figure 4 shows two mazes where the object is to get from the start (a green arrow) to the end (a red 'x').

Figure 4. Two mazes.

In the first case, this rule gets you to the destination; but in the second, you would forever wander in a loop never reaching the destination.

4. To be useful, it should be clear that the algorithm will ultimately finish.

Some algorithms will not work under certain circumstances. For example, one rule for getting through a maze is to always follow the left-hand wall. Figure 4 shows two mazes where the object is to get from the start (a green arrow) to the end (a red 'x').

5. Not all algorithms are guaranteed to find a solution.

Sometimes, an algorithm may not be able to find a solution; thus, following the instructions may result in a solution or an indication that the algorithm cannot find a solution.

6. Algorithms may not find the best or optimal solution.

The following algorithm is a reasonable one for getting the average person in Ontario to Ottawa:

1. Determine which is closer to your current location: Highway 401 or Highway 416, and drive to that highway.
2. If Highway 401 was closer, travel in the direction of Highway 416 and take that cut-off.
3. Follow Highway 416 in the direction of Ottawa.

This is a simple algorithm that will get the driver to Ottawa, and for the vast majority of persons in Ontario, this will get them to Ottawa in a reasonably efficient manner. It is, however,

5. Not all algorithms are guaranteed to find a solution.

Sometimes, an algorithm may not be able to find a solution; thus, following the instructions may result in a solution or an indication that the algorithm cannot find a solution.

6. Algorithms may not find the best or optimal solution.

The following algorithm is a reasonable one for getting the average person in Ontario to Ottawa:

1. Determine which is closer to your current location: Highway 401 or Highway 416, and drive to that highway.
2. If Highway 401 was closer, travel in the direction of Highway 416 and take that cut-off.
3. Follow Highway 416 in the direction of Ottawa.

This is a simple algorithm that will get the driver to Ottawa, and for the vast majority of persons in Ontario, this will get them to Ottawa in a reasonably efficient manner. It is, however, not necessarily the best. For example, if you were in Peterborough, it may be easier and faster to follow Highway 7 rather than backtracking to Highway 401 and adding approximately half an hour onto your travel time.

Suppose you were in Manhattan, New York. One algorithm to get to a destination is:

1. If your destination is between you and the next intersection, go to the destination—you are finished.
2. Otherwise, move to the next intersection that is closest to your destination and return to Step 1. Note: in the unlikely circumstance that two intersections are equally close, choose either.

The grid layout allows this simple algorithm to work. However, if you were to apply this algorithm in suburbia, with circles and crescents, this algorithm may fail. For example, consider the map in Figure 5. To get from Point A to Point B, the algorithm would have you move to Intersection 1, then to 2, but this would immediately return you back to Intersection 1, as that is the next intersection that is closest to the destination. Similarly, to get from Point B to A, the algorithm would see you moving between Intersections 4 and 3.

Figure 5. A map of Waterloo in Laurelwood (from maps.google.ca).

Now, you could improve the algorithm by flagging all intersections initially as unvisited; then, when you visit an intersection, flag it as visited and move to the next unvisited intersection that is closest to your destination. While this algorithm may work, it now introduces two problems:

• The path may not be the most optimal: to get from Point A to B, this algorithm would first take you to Intersection 1, then 2, 3 and 4, and only then to the destination. An optimal algorithm would skip Intersection 1.
• Next, the question is how do you find the next unvisited intersection? In Manhattan, it may be quite easy to determine which intersection is closest; in Waterloo, this may be significantly more difficult.

7. Well-defined parameters and output.

An algorithm requires inputs that are used to find the solution. If the requisite inputs are not provided, the algorithm may not be able to even execute, or if the inputs are invalid, the algorithm may fail.

For example, in one of the algorithms you were asked to describe, it was assumed that a polynomial had integer roots and you described an algorithm for factoring that polynomial. If you provided a polynomial that had non-integer roots, the algorithm would fail.