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. The actual search is performed in the recursive helper function search, and the currently considered sub-array of \(A\) is indicated by its start and end indices lo and hi.

// 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 and so on.

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)(using ord: Ordering[T]) =
  def inner(lo: Int, hi: Int): Boolean =
    if lo <= hi then
      val mid = lo + ((hi - lo) / 2)
      val cmp = ord.compare(e, arr(mid))
      if cmp == 0 then true                 // e == arr(mid)
      else if cmp < 0 then 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 using 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 {.