Classification of Algorithms

Iterative Algorithms

Algorithms can usually be classified based on the type of strategy used to solve the problem. If we look at sorting, specifically, the bubble sort algorithm:

do

    hasSwapped = false

    for i = 1 to size(A) - 1:

        if A[i-1] > A[i] then

            swap (A[i-1], A[i])

            hasSwapped = true

        end if

    end for

while hasSwapped

What we notice here is that the algorithm occurs with a loop inside of a loop. Each loop must finish in order to complete the algorithm. This type of algorithm is called an Iterative Algorithm. Characteristics of iterative algorithms are:

Steps are performed in a loop structure until the algorithm completes
The "state" of progress of the algorithm is held in variables which are updated every time we iterate

Other sorts, such as Insertion Sort and Selection Sort are also iterative. Examples of iterative methods can be seen below:

Multiply 2 Numbers by Using Repeated Addition

function multiply (integer a, integer b)

    integer sum = 0

    for i start at 0, end at b, count by 1

        sum = sum + a

    return sum

Reverse a String, One Character at a Time

function reverse(String input)

    String output = ""

    for i starting at length of input - 1, end at 0, count by -1

        concatenate input[i] onto the end of output

    return output

Neither one of these iterative methods is terribly groundbreaking, but you can clearly identify them as iterative: They both have loops and state variables that are maintained until the algorithm completes.

Recursive Algorithms

We have also explored the idea of recursion: Methods which call themselves in order to complete a task. The example used in class was that of the Fibonacci Sequence. This example is called a simple recursive algorithm, which is characterized by the following:

A base case used to end the recursion
A recursive case that calls the same method we are currently executing using a slightly modified data set. The number of recursive calls is >= 1 for every recursive case. In the case of the Fibonacci function, we reduce n by 1 and 2 in our recursive call.

function fib(integer n)

    // n must be >= 0

    if n == 0 or n == 1

        return 1

    return fib(n-1) + fib(n-2)

function factorial(integer n)

    if n == 0 or n == 1

        return 1

    return n * factorial (n-1)

Recursive algorithms also have some other types of sub-problems, such as Divide-And-Conquer Algorithms, which are characterized as follows:

A base case used to end the recursion
A recursive case that calls the same executing method using a split data set into at least two subsets. The number of recursive calls >= 2.

Examples of a Divide and Conquer algorithms can be seen below:

function MergeSort(arr[], l,  r)

    If r > l

        // 1. Find the middle point of the array:

        middle m = (l+r)/2

        // 2. Call mergeSort for first half:

        Call mergeSort(arr, l, m)

        // 3. Call mergeSort for second half:

        Call mergeSort(arr, m+1, r)

        // 4. Merge the two halves sorted in step 2 and 3:

        Call merge(arr, l, m, r)

function BinarySearch(A[], value, low, high) {

      if (high < low)

          return not_found

      mid = (low + high) / 2

      if (A[mid] > value)

          return BinarySearch(A, value, low, mid-1)

      else if (A[mid] < value)

          return BinarySearch(A, value, mid+1, high)

      else

          return mid

Greedy Algorithms

A Greedy Algorithm has one main characteristic:

During each iteration, the immediate best solution is followed, regardless of future outcomes

A classic algorithm description of a greedy algorithm is that of making change for totals less than one dollar using the fewest number of Canadian coins possible:

The coins are valued a 1 (penny) (though not anymore...), 5 (nickel), 10 (dime) and 25 (quarter) cents a piece.
At any point, choose the largest coin you can still select.

As an example, find change for 63 cents:

First, choose 2 quarters because 25 is the largest coin less than our total - 50 cents, 13 cents remaining
Next choose 1 dime because we can no longer choose a quarter, but a dime still works. - 60 cents, 3 cents remaining
Finally, choose 3 pennies because we can no longer choose dimes, nor can we choose nickels because 3 cents is less than 5 cents - 67 cents, 0 remaining

In total, we chose 6 coins, which is in fact the fewest possible coins to make 63 cents. This algorithm, using the specified coins will always choose the fewest number of coins. However, if we change the coin amounts, this algorithm can produce errors:

Imagine a set of coins that are worth 1, 7 and 10 cents.
What is the fewest coins necessary to make 15 cents?

Using our algorithm, we would choose one 10 cent piece, followed by 5 one cent pieces, for a total of 6 coins. The fewest possible is 3: 7 cents x 2, and 1 cent x 1.

This exemplifies the downfall of greedy algorithms: Sometimes they will not produce the most correct result. Because of this, greedy algorithms are sometimes used to approximate answers as they give generally decent answers, but much faster than a brute force type of implementation. This type of approach to solving problems is sometimes called a "heuristic" approach: Sacrifice exact accuracy for speed because a perfect solution is not necessary.

Backtracking

Backtracking algorithms have the following characteristics:

Solve the problem until a decision must be made about two or more possible solutions.
Pick one of those possible solutions and fully explore it until it is determined that it does not work.
If a solution does not work, discard the solution and return to the previous decision to choose a different possibility.
Keep track of all explored/discarded solutions.
(Optional) Find the set of ALL working solutions and choose the best one.

In the video, a backtracking solution is provided for solving a maze. Other common types of backtracking solutions are Depth First and Breadth First Searches, which you have already explored. Most backtracking algorithms use recursion because it is a natural extension of the idea, however recursion is NOT necessary.

Activities

Below is a method signature.

/**

 * The method fewest coins returns the count of the fewest coins

 * necessary to make change for the specified value.

 * @param value - the change value required

 * @param coinValues - a sorted array of available coin values. Sorted in ascending order.

 * @return int - the fewest number of coins necessary.

*/

public static int fewestCoins(double value, double[] coinValues)

1. a) Create a method that implements the coin greedy algorithm using the above method signature. This method is allowed to return incorrect, but "close enough" values (like the 1, 7 and 10 example above)

b) Create a method that implements the above method signature using another algorithm. This method MUST return the correct answer.

c) Run each method through 10 different tests (i.e. pick 10 different sets of input values and coin values), 100 times a piece. What is the difference in execution time? Based on your tests, is the difference in performance worth the accuracy? Justify your position. Be sure to include situations where the greedy algorithm does NOT produce the correct answer.

2. Google the "8-Queens" problem and find a backtracking algorithm which you can implement in Java.

Report abuse