Algorithms: The Basic Programming Model

From the book

Algorithms: Part I, 4th Edition

Learn More Buy

From the book

From the book 

Algorithms: Part I, 4th Edition

Learn More Buy

APIs

A critical component of modular programming is documentation that explains the operation of library methods that are intended for use by others. We will consistently describe the library methods that we use in this book in application programming interfaces (APIs) that list the library name and the signatures and short descriptions of each of the methods that we use. We use the term client to refer to a program that calls a method in another library and the term implementation to describe the Java code that implements the methods in an API.

Example. 

The following example, the API for commonly used static methods from the standard Math library in java.lang, illustrates our conventions for APIs:

public class Math

static double

abs(double a)

static double

max(double a, double b)

static double

min(double a, double b)

static double

sin(double theta)

static double

cos(double theta)

static double

tan(double theta)

static double

exp(double a)

static double

log(double a)

static double

pow(double a, double b)

static double

random()

static double

sqrt(double a)

static double

E

static double

PI

API for Java’s mathematics library (excerpts)

These methods implement mathematical functions—they use their arguments to compute a value of a specified type (except random(), which does not implement a mathematical function because it does not take an argument). Since they all operate on double values and compute a double result, you can consider them as extending the double data type—extensibility of this nature is one of the characteristic features of modern programming languages. Each method is described by a line in the API that specifies the information you need to know in order to use the method. The Math library also defines the precise constant values PI (for π) and E (for e), so that you can use those names to refer to those constants in your programs. For example, the value of Math.sin(Math.PI/2) is 1.0 and the value of Math.log(Math.E) is 1.0 (because Math.sin() takes its argument in radians and Math.log() implements the natural logarithm function).

Java libraries. 

Extensive online descriptions of thousands of libraries are part of every Java release, but we excerpt just a few methods that we use in the book, in order to clearly delineate our programming model. For example, BinarySearch uses the sort() method from Java’s Arrays library, which we document as follows:

public class Arrays

static void sort(int[] a)

Excerpt from Java’s Arrays library (java.util.Arrays)

The Arrays library is not in java.lang, so an import statement is needed to use it, as in BinarySearch. Actually, Chapter 2 of this book is devoted to implementations of sort() for arrays, including the mergesort and quicksort algorithms that are implemented in Arrays.sort(). Many of the fundamental algorithms that we consider in this book are implemented in Java and in many other programming environments. For example, Arrays also includes an implementation of binary search. To avoid confusion, we generally use our own implementations, although there is nothing wrong with using a finely tuned library implementation of an algorithm that you understand.

Our standard libraries. 

We have developed a number of libraries that provide useful functionality for introductory Java programming, for scientific applications, and for the development, study, and application of algorithms. Most of these libraries are for input and output; we also make use of the following two libraries to test and analyze our implementations. The first extends Math.random() to allow us to draw random values from various distributions; the second supports statistical calculations:

public class StdRandom

static    void

initialize(long seed)

static  double

random()

static     int

uniform(int N)

static     int

uniform(int lo, int hi)

static  double

uniform(double lo, double hi)

static boolean

bernoulli(double p)

static  double

gaussian()

static  double

gaussian(double m, double s)

static     int

discrete(double[] a)

static    void

shuffle(double[] a)

API for our library of static methods for random numbers

public class StdStats

static double

max(double[] a)

static double

min(double[] a)

static double

mean(double[] a)

static double

var(double[] a)

static double

stddev(double[] a)

static double

median(double[] a)

API for our library of static methods for data analysis

The setSeed() method in StdRandom allows us to seed the random number generator so that we can reproduce experiments involving random numbers. For reference, implementations of many of these methods are given on page 32. Some of these methods are extremely easy to implement; why do we bother including them in a library? Answers to this question are standard for well-designed libraries:

• They implement a level of abstraction that allow us to focus on implementing and testing the algorithms in the book, not generating random objects or calculating statistics. Client code that uses such methods is clearer and easier to understand than homegrown code that does the same calculation.
• Library implementations test for exceptional conditions, cover rarely encountered situations, and submit to extensive testing, so that we can count on them to operate as expected. Such implementations might involve a significant amount of code. For example, we often want implementations for various types of data. For example, Java’s Arrays library includes multiple overloaded implementations of sort(), one for each type of data that you might need to sort.

These are bedrock considerations for modular programming in Java, but perhaps a bit overstated in this case. While the methods in both of these libraries are essentially self-documenting and many of them are not difficult to implement, some of them represent interesting algorithmic exercises. Accordingly, you are well-advised to both study the code in StdRandom.java and StdStats.java on the booksite and to take advantage of these tried-and-true implementations. The easiest way to use these libraries (and to examine the code) is to download the source code from the booksite and put them in your working directory; various system-dependent mechanisms for using them without making multiple copies are also described on the booksite.

Your own libraries. 

It is worthwhile to consider every program that you write as a library implementation, for possible reuse in the future.

• Write code for the client, a top-level implementation that breaks the computation up into manageable parts.
• Articulate an API for a library (or multiple APIs for multiple libraries) of static methods that can address each part.
• Develop an implementation of the API, with a main() that tests the methods independent of the client.

Not only does this approach provide you with valuable software that you can later reuse, but also taking advantage of modular programming in this way is a key to successfully addressing a complex programming task.

public static double uniform(double a, double b)
{  return a + StdRandom.random() * (b-a);  }

public static int uniform(int N)
{  return (int) (StdRandom.random() * N);  }

public static int uniform(int lo, int hi)
{  return lo + StdRandom.uniform(hi - lo);  }

public static int discrete(double[] a)
{  // Entries in a[] must sum to 1.
     double r = StdRandom.random();
     double sum = 0.0;
     for (int i = 0; i < a.length; i++)
{
        sum = sum + a[i];
        if (sum >= r) return i;
     }
     return -1;
}

public static void shuffle(double[] a)
{
   int N = a.length;
   for (int i = 0; i < N; i++)
   {  // Exchange a[i] with random element in a[i..N-1]
      int r = i + StdRandom.uniform(N-i);
      double temp = a[i];
      a[i] = a[r];
      a[r] = temp;
   }
}

Implementations of static methods in StdRandom library

The purpose of an API is to separate the client from the implementation: the client should know nothing about the implementation other than information given in the API, and the implementation should not take properties of any particular client into account. APIs enable us to separately develop code for various purposes, then reuse it widely. No Java library can contain all the methods that we might need for a given computation, so this ability is a crucial step in addressing complex programming applications. Accordingly, programmers normally think of the API as a contract between the client and the implementation that is a clear specification of what each method is to do. Our goal when developing an implementation is to honor the terms of the contract. Often, there are many ways to do so, and separating client code from implementation code gives us the freedom to substitute new and improved implementations. In the study of algorithms, this ability is an important ingredient in our ability to understand the impact of algorithmic improvements that we develop.