Describing algorithms¶

In an abstract view, an algorithm can be seen as a method that transforms some input to output.

For instance, a sorting algorithm transforms an array of elements into another array that contains the same elements but in a sorted order. In order to communicate algorithms to other people, we have to describe them in some way. Of course, one could describe the algorithm by giving its implementation in some concrete programming language. However, in many cases, it can be easier and beneficial to describe an algorithm

in a natural language, or
in some form of pseudocode.

As an example, recall the binary search algorithm discussed in the CS-A1120 Programming 2 course. In the input/output-level abstraction, the algorithm fulfills the following specification:

Input: a sorted array \(A\) of elements and an element \(e\).
Output: “true” if \(e\) appears in \(A\), “false” otherwise.

In a natural language (English in this case), we may describe the binary search algorithm in the following structured way:

Initially, consider the whole array.
If the considered array is empty, return “false”
If the middle element of the array is \(e\), return “true”.
Otherwise, if the middle element is greater than \(e\), go to step 2 but only consider the subarray from the beginning to (but not including) the middle element.
Otherwise, the middle element is less than \(e\) and we go to step 2 but consider the subarray from (but not including) the middle element to the end of the array.

In pseudocode, we may describe the binary search algorithm as follows. Note that the same algorithmic idea is given as a slightly different variant: the helper function searches for the index in which the element must occur if it occurs in \(A\) at all, and terminates the search when the considered sub-array is of size 1.

// Search for the element \( e \) in the sorted array \( A \)
binary-search(\( A \), \( e \)):
   return search(\( A \), \( e \), \( 1 \), \( \ALengthOf{A} \))

// A recursive helper function doing the actual search
search(\( A \), \( e \), \( \Lo \), \( \Hi \)):
   if \( \Lo \le \Hi \): // sub-array of size 1 or more?
      \( \Mid \Asgn \Lo + \Floor{(\Hi - \Lo) / 2} \)
      if \( A[\Mid] \Eq e \):    return true
      else if \( e < A[\Mid] \): return search(\( A \), \( e \), \( \Lo \), \( \Mid-1 \))
      else:                  return search(\( A \), \( e \), \( \Mid+1 \), \( \Hi \))
   else:
      return false
 

The pseudocode presentation only expresses the essential operations needed to communicate the algorithm idea: many details, such as type information, are simply omitted. As in many programming languages (but not in Scala), array indexing is denoted with the square brackets. Please also notice that in many cases, array indexing starts (i) from \(1\) in pseudocode and in mathematics but (ii) from \(0\) in real programming languages. Take this into account when implementing algorithms from books, wikipedia, scientific articles etc.

Of course, we may also describe an algorithm by giving an implementation in some programming language. For instance, below is an implementation of the binary search algorithm in Scala.

def binarySearch[T](arr: Array[T], e: T)(implicit ord: Ordering[T]): Boolean = {
  def inner(lo: Int, hi: Int): Boolean = {
    if(lo <= hi) {
      val mid = lo + ((hi - lo) / 2)
      val cmp = ord.compare(e, arr(mid))
      if(cmp == 0) true                 // e == arr(mid)
      else if(cmp < 0) inner(lo, mid-1) // e < arr(mid)
      else inner(mid+1, hi)             // e > arr(mid)
    } else
      false
  }
  inner(0, arr.length-1)
}

Similarly, the same implementation but in C++11:

#include <functional>
#include <vector>

template<typename T>
bool binarySearch(std::vector<T>& arr, T& e) {
  std::function<int(int,int)> inner = [&](int lo, int hi) -> int {
    if(lo <= hi) {
      const int mid = lo + ((hi - lo) / 2);
      if(e == arr[mid])
	return true;
      else if(e < arr[mid])
	return inner(lo, mid-1);
      else // e > arr[mid]
	return inner(mid+1, hi);
    } else
      return false;
  };
  return inner(0, arr.size()-1);
}

These descriptions have the drawback that a reader who is unfamiliar with the applied programming language may get lost in language specific details when trying to understand the core idea of the algorithm. For instance, in the above Scala code, is implicit ord: Ordering[T] relevant for the algorithm itself? Similarly, a reader who is not familiar with C++ may feel lost when encountering the line std::function<int(int,int)> inner = [&](int low, int hi) -> int {.