Chapter Four. Algorithms and Data Structures

This chapter presents fundamental data types that are essential building blocks for a broad variety of applications. We present full implementations, even though some of them are built into Python, so that you can have a clear idea of how they work and why they are important.

Objects can contain references to other objects, so we can build structures known as linked structures, which can be arbitrarily complex. With linked structures and arrays, we can build data structures to organize information in such a way that we can efficiently process it with associated algorithms. In a data type, we use the set of values to build data structures and the methods that operate on those values to implement algorithms.

The algorithms and data structures that we consider in this chapter introduce a body of knowledge developed over the past several decades that constitutes the basis for the efficient use of computers for a broad variety of applications. From n-body simulation problems in physics to genetic sequencing problems in bioinformatics, the basic approaches we describe have become essential in scientific research; from database systems to search engines, these methods are the foundation of commercial computing. As the scope of computing applications continues to expand, so grows the impact of these basic approaches.

Algorithms and data structures themselves are valid subjects of scientific inquiry. Accordingly, we begin by describing a scientific approach for analyzing the performance of algorithms, which we use throughout the chapter to study the performance characteristics of our implementations.

To study the cost of running them, we study our programs themselves via the scientific method, the commonly accepted body of techniques universally used by scientists to develop knowledge about the natural world. We also apply mathematical analysis to derive concise models of the cost.

Which features of the natural world are we studying? In most situations, we are interested in one fundamental characteristic: time. Whenever we run a program, we are performing an experiment involving the natural world, putting a complex system of electronic circuitry through series of state changes involving a huge number of discrete events that we are confident will eventually stabilize to a state with results that we want to interpret. Although developed in the abstract world of Python programming, these events most definitely are happening in the natural world. What will be the elapsed time until we see the result? It makes a great deal of difference to us whether that time is a millisecond, a second, a day, or a week. Therefore, we want to learn, through the scientific method, how to properly control the situation, just as when we launch a rocket, build a bridge, or smash an atom.

On the one hand, modern programs and programming environments are complex; on the other hand, they are developed from a simple (but powerful) set of abstractions. It is a small miracle that a program produces the same result each time we run it. To predict the time required, we take advantage of the relative simplicity of the supporting infrastructure that we use to build programs. You may be surprised at the ease with which you can develop cost estimates and predict the performance characteristics of many of the programs that you compose.

• Observe some feature of the natural world.

• Hypothesize a model that is consistent with the observations.

• Predict events using the hypothesis.

• Verify the predictions by making further observations.

• Validate by repeating until the hypothesis and observations agree.

One of the key tenets of the scientific method is that the experiments we design must be reproducible, so that others can convince themselves of the validity of the hypothesis. In addition, the hypotheses we formulate must be falsifiable—we have the possibility of knowing for sure when a hypothesis is wrong (and thus needs revision).

Our first qualitative observation about most programs is that there is a problem size that characterizes the difficulty of the computational task. Normally, the problem size is either the size of the input or the value of a command-line argument. Intuitively, the running time should increase with the problem size, but the question of how much it increases naturally arises every time we develop and run a program.

Another qualitative observation for many programs is that the running time is relatively insensitive to the input itself; it depends primarily on the problem size. If this relationship does not hold, we need to run more experiments to better understand, and perhaps better control, the running time’s sensitivity to the input. Since this relationship does often hold, we focus now on the goal of better quantifying the correspondence between problem size and running time.

As a concrete example, we start with threesum.py (PROGRAM 4.1.1), which counts the number of triples in an array of n numbers that sum to 0. This computation may seem contrived to you, but it is deeply related to numerous fundamental computational tasks, particularly those found in computational geometry, so it is a problem worthy of careful study. What is the relationship between the problem size n and the running time for threesum.py?

• Detailed understanding of the program

• Detailed understanding of the system and the computer

• Advanced tools of mathematical analysis

Thus it is best left for experts. Every programmer, however, needs to know how to make back-of-the-envelope performance estimates. Fortunately, we can often acquire such knowledge by using a combination of empirical observations and a small set of mathematical tools.

• The cost of executing each statement

• The frequency of execution of each statement

The former is a property of the system, and the latter is a property of the algorithm. If we know both for all instructions in the program, we can multiply them together and sum for all instructions in the program to get the running time.

The primary challenge is to determine the frequency of execution of the statements. Some statements are easy to analyze; for example, the statement that initializes count to 0 in threesum.countTriples() is executed only once. Others require higher-level reasoning; for example, the if statement in threesum.countTriples() is executed precisely n (n–1)(n–2)/6 times (that is precisely the number of ways to pick three different numbers from the input array—see EXERCISE 4.1.5).

Frequency analyses of this sort can lead to complicated and lengthy mathematical expressions. To substantially simplify matters in the mathematical analysis, we develop simpler approximate expressions in two ways. First, we work with the leading term of mathematical expressions by using a mathematical device known as the tilde notation. We write ~ f(n) to represent any quantity that, when divided by f(n), approaches 1 as n grows. We also write g(n) ~ f(n) to indicate that g(n) / f(n) approaches 1 as n grows. With this notation, we can ignore complicated parts of an expression that represent small values. For example, the if statement in threesum.py is executed ~n³/6 times because n (n–1) (n–2) / 6 = n³/6 – n²/2 + n/3, which, when divided by n³/6, approaches 1 as n grows. This notation is useful when the terms after the leading term are relatively insignificant (for example, when n = 1,000, this assumption amounts to saying that –n²/2 + n/3 ≈ – 499,667 is relatively insignificant by comparison with n³/6 ≈ 166,666,667, which it is). Second, we focus on the instructions that are executed most frequently, sometimes referred to as the inner loop of the program. In this program it is reasonable to assume that the time devoted to the instructions outside the inner loop is relatively insignificant.

The key point in analyzing the running time of a program is this: for a great many programs, the running time satisfies the relationship

T(n) ∼ c f(n)

where c is a constant and f(n) is a function known as the order of growth of the running time. For typical programs, f(n) is a function such as log n, n, n log n, n², or n³, as you will soon see (customarily, we express order-of-growth functions without any constant coefficient). When f(n) is a power of n, as is often the case, this assumption is equivalent to saying that the running time satisfies a power law. In the case of threesum.py, it is a hypothesis already verified by our empirical observations: the order of growth of the running time of threesum.py is n³. The value of the constant c depends both on the cost of executing instructions and on details of the frequency analysis, but we normally do not need to work out the value, as you will now see.

The order of growth is a simple but powerful model of running time. For example, knowing the order of growth typically leads immediately to a doubling hypothesis. In the case of threesum.py, knowing that the order of growth is n³ tells us to expect the running time to increase by a factor of 8 when we double the size of the problem because

T(2n)/T(n) → c (2n)³/(cn³) = 8

This matches the value resulting from the empirical analysis, thus validating both the model and the experiments. Study this example carefully, because you can use the same method to better understand the performance of any program that you compose.

Knuth showed that it is possible to develop an accurate mathematical model of the running time of any program, and many experts have devoted much effort to developing such models. But you do not need such a detailed model to understand the performance of your programs: it is typically safe to ignore the cost of the instructions outside the inner loop (because that cost is negligible by comparison to the cost of the instruction in the inner loop) and not necessary to know the value of the constant in the running-time approximation (because it cancels out when you use a doubling hypothesis to make predictions).

These approximations are significant because they relate the abstract world of a Python program to the real world of a computer running it. The approximations are such that characteristics of the particular machine that you are using do not play a significant role in the models—the analysis separates the algorithm from the system. The order of growth of the running time of threesum.py is n³ does not depend on whether it is implemented in Python or whether it is running on your laptop, someone else’s mobile phone, or a supercomputer; rather, it depends primarily on the fact that it examines all the triples. The properties of the computer and the system are all summarized in various assumptions about the relationship between program statements and machine instructions, and in the actual running times that we observe as the basis for the doubling hypothesis. The algorithm that you are using determines the order of growth. This separation is a powerful concept because it allows us to develop knowledge about the performance of algorithms and then apply that knowledge to any computer. In fact, much of the knowledge about the performance of classic algorithms was developed decades ago, but that knowledge is still relevant to today’s computers.

Empirical and mathematical analyses like those we have described constitute a model (an explanation of what is going on) that might be formalized by listing all of the assumptions mentioned (each instruction takes the same amount of time each time it is executed, running time has the given form, and so forth). Not many programs are worthy of a detailed model, but you need to have an idea of the running time that you might expect for every program that you compose. Pay attention to the cost. Formulating a doubling hypothesis—through empirical studies, mathematical analysis, or (preferably) both—is a good way to start. This information about performance is extremely useful, and you will soon find yourself formulating and validating hypotheses every time you run a program. Indeed, doing so is a good use of your time while you wait for your program to finish!

All of Python’s operations on standard numeric types take constant time. That is, applying an operation to a large number consumes no more time than does applying it to a small number. (One exception is that operations involving integers with a huge number of digits can consume more than constant time; see the Q&A at the end of this section for details.) The functions in Python’s math module also take constant time. Note that we do not specify the size of the constant. For example, the constant for math.atan2() is somewhat larger than the constant for math.hypot().

These classifications are the most common, but certainly not a complete set. Indeed, the detailed analysis of algorithms can require the full gamut of mathematical tools that have been developed over the centuries. Understanding the running time of programs such as factors.py (PROGRAM 1.3.9), primesieve.py (PROGRAM 1.4.3), and euclid.py (PROGRAM 2.3.1) requires fundamental results from number theory. Classic algorithms like hashst.py (PROGRAM 4.4.3) and bst.py (PROGRAM 4.4.4) require careful mathematical analysis. The programs sqrt.py (PROGRAM 1.3.6) and markov.py (PROGRAM 1.6.3) are prototypes for numerical computation: their running time depends on the rate of convergence of a computation to a desired numerical result. Monte Carlo simulations such as gambler.py (PROGRAM 1.3.8) and percolation.py (PROGRAM 2.4.6) and variants are of interest precisely because detailed mathematical models for them are not available.

Nevertheless, a great many of the programs that you will compose have straightforward performance characteristics that can be described accurately by one of the orders of growth that we have considered, as documented in the table on the preceding page. Accordingly, we can usually work with simple higher-level hypotheses, such as the order of growth of the running time of mergesort is linearithmic. For economy, we abbreviate such a statement to just say mergesort is linearithmic. Most of our hypotheses about cost are of this form, or of the form mergesort is faster than insertion sort. Again, a notable feature of such hypotheses is that they are statements about algorithms, not just about programs.

Knowing the order of growth of the running time allows us to make decisions about addressing large problems so that we can invest whatever resources we have to deal with the specific problems that we actually need to solve. We typically use the results of verified hypotheses about the order of growth of the running time of programs in one of the following ways.

for i in range(m):
    for j in range(n):
        if a[i] + b[j] == 0:
            count += 1

In such cases, we treat the parameters m and n separately, holding one fixed while analyzing the other. For example, the order of growth of the running time of this code fragment is mn.

Despite all these caveats, understanding the order of growth of the running time of each program is valuable knowledge for any programmer, and the methods that we have described are powerful and broadly applicable. Knuth’s insight was that we can carry these methods through to the last detail in principle to make detailed, accurate predictions. Typical computer systems are extremely complex and close analysis is best left for experts, but the same methods are effective for developing approximate estimates of the running time of any program. A rocket scientist needs to have some idea of whether a test flight will land in the ocean or in a city; a medical researcher needs to know whether a drug trial will kill or cure all the subjects; and any scientist or engineer using a computer program needs to have some idea of whether it will run for a second or for a year.

For example, such a conservative approach might be appropriate for the software that runs a nuclear reactor or an air traffic control system or the brakes in your car. We must guarantee that such software completes its job within the bounds that we set because the result could be catastrophic if it does not. Scientists normally do not contemplate the worst case when studying the natural world: in biology, the worst case might the extinction of the human race; in physics, the worst case might be the end of the universe. But the worst case can be a very real concern in computer systems, where the input is generated by another (potentially malicious) user, rather than by nature. For example, websites that do not use algorithms with performance guarantees are subject to denial-of-service attacks, where hackers flood them with pathological requests that make them run harmfully slower than planned.

Performance guarantees are difficult to verify with the scientific method, because we cannot test a hypothesis such as mergesort is guaranteed to be linearithmic without trying all possible inputs, which we cannot do because there are far too many of them. We might falsify such a hypothesis by providing inputs for which mergesort is slow, but how can we prove it to be true? We must do so not with experimentation, but rather with mathematical models.

It is the task of the algorithm analyst to discover as much relevant information about an algorithm as possible, and it is the task of the applications programmer to apply that knowledge to develop programs that effectively solve the problems at hand. For example, if you are using a quadratic algorithm to solve a problem but can find an algorithm that is guaranteed to be linearithmic, you will usually prefer the linearithmic one. On rare occasions, you might still prefer the quadratic algorithm because it is faster on the kinds of inputs that you need to solve or because the linearithmic algorithm is too complex to implement.

Ideally, we want algorithms that lead to clear and compact code that provides both a good worst-case guarantee and good performance on inputs of interest. Many of the classic algorithms that we consider in this chapter are of importance for a broad variety of applications precisely because they have all of these properties. Using these algorithms as models, you can develop good solutions yourself for typical problems that you face while programming.

The table on the facing page gives the most commonly used operations for Python lists. Note that several of these operations—indexing, slicing, concatenation, deletion, containment, and iteration—enjoy direct language support in the form of special syntax. As illustrated in the table at right, some of these operations return values while others mutate the invoking list.

We have deferred this API to this section because programmers who use Python lists without following our mantra pay attention to the cost are in for trouble. For example, consider these two code snippets:

Click here to view code image

# quadratic time           # linear time
a = []                     a = []
for i in range(n):         for i in range(n):
    a .insert(0, 'slow')       a.insert(i, 'fast')

The one on the left takes quadratic time; the one on the right takes linear time. To understand why Python list operations have the performance characteristics that they do, you need to learn more about Python’s resizing array representation of lists, which we discuss next.

The main challenge is ensuring that the data structure has sufficient capacity to hold all of the items, but is not so large as to waste an excessive amount of memory. Achieving these two goals turns out to be remarkably easy.

First, if we want to append an item to the end of a resizing array, we check its capacity. If there is room, we simply insert the new item at the end. If not, we double its capacity by creating a new array of twice the length and copying the items from the old array into the new array.

Similarly, if we want to remove an item from the end of the resizing array, we check its capacity. If it is excessively large, we halve its capacity by creating a new array of half the length and copying the items from the old array into the new array. An appropriate test is to check whether the size of the resizing array is less than one-fourth of its capacity. That way, after the capacity is halved, the resizing array is about half full and can accommodate a substantial number of insertions before we have to change its capacity again.

The doubling-and-halving strategy guarantees that the resizing array remains between 25% and 100% full, so that space is linear in the number of items. The specific strategy is not sacrosanct. For example, typical Python implementations expand the capacity by a factor of 9/8 (instead of 2) when the resizing array is full. This wastes less space (but triggers more expansion and shrinking operations).

More precisely, starting from an empty Python list, any sequence of n operations labeled as “constant time” in the API table on page 531 takes time linear in n. In other words, the total cost of any such sequence of Python list operations divided by the number of operations is bounded by a constant. This kind of analysis is known as amortized analysis. This guarantee is not as strong as saying that each operation is constant-time, but it has the same implications in many applications (for example, when our primary interest is in total running time). We leave the full details as an exercise for the mathematically inclined.

For the special case where we perform a sequence of n insertions into an empty resizing array, the idea is simple: each insertion takes constant time to add the item; each insertion that triggers a resizing (when the current size is a power of 2) takes additional time proportional to n to copy the elements from the old array of length n to a new array of length 2n. Thus, assuming n is a power of 2 for simplicity, the total cost is proportional to

(1 + 1 + 1 + ... + 1) + (1 + 2 + 4 + 8 + ... + n) ~ 3n

The first term (which sums to n) accounts for the n insertion operations; the second term (which sums to 2n − 1) accounts for the lg n resizing operations.

Understanding resizing arrays is important in Python programming. For example, it explains why creating a Python list of n items by repeatedly appending items to the end takes time proportional to n (and why creating a list of n items by repeatedly prepending items to the front takes time proportional to n²). Such performance pitfalls are precisely the reason that we recommend using narrower interfaces that address performance.

Click here to view code image

TypeError: 'str' object does not support item assignment

If you want 'Hello', you need to create a completely new string. This difference reinforces the idea of immutability and has significant implications with regard to performance, which we now examine.

• A reference to a place in memory where the characters in the string are stored contiguously

• The length of the string

By contrast, consider the diagram at right, which is an array of one-character strings. We will consider a more detailed analysis later in this section, but you can see that the string representation is certainly significantly simpler. It uses much less space per character and provides faster access to each character. In many applications, these characteristics are very important because strings can be very long. So, it is important both that the memory usage be not much more than is required for the characters themselves and that characters can be quickly accessed by their index, as in an array.

n = len(s)
reverse = ''
for i in range(n):
    reverse = s[i] + reverse

During iteration i of the for loop, the string concatenation operator produces a string of length i+1. Thus, the overall running time is proportional to 1 + 2 + ... + n ~ n² / 2 (see EXERCISE 4.1.4). That is, the code fragment takes quadratic time as a function of the string length n (see EXERCISE 4.1.13 for a linear-time solution).

Understanding differences between data types like strings and Python lists is critical in learning any programming language, and programmers must be vigilant to ensure they avoid performance bugs like the one just described. This has been the case since the early days of data abstraction. For example, the string data type in the C language that was developed in the 1970s has a linear-time length function, and countless programmers using the length in a for loop that iterates through the string have found themselves with a quadratic-time performance bug for a simple linear-time job.

At the outset, you should be aware that the flexibility that we get from Python’s pure approach to object-oriented programming (everything is an object, even boolean values) comes with costs, and one of the most significant costs is the amount of memory consumed. This will become more clear as we examine some specific examples.

Memory usage is well defined for Python on your computer (every value will require precisely the same amount of memory each time that you run your program), but Python is implemented on a very wide range of computational devices, and memory consumption is implementation-dependent. Different versions of Python might implement the same data type in different ways. For economy, we use the word typical to signal values that are particularly subject to machine dependencies. Analyzing memory usage is somewhat different from analyzing time usage, primarily because one of Python’s most significant features is its memory allocation system, which is supposed to relieve you of having to worry about memory. Certainly, you are well advised to take advantage of this feature when appropriate. Still, it is your responsibility to know, at least approximately, when a program’s memory requirements might prevent you from solving a given problem.

Computer memory is divided into bytes, where each byte consists of 8 bits, and where each bit is a single binary digit. To determine the memory usage of a Python program, we count up the number of objects used by the program and weight them by the number of bytes that they require, according to their type. To use that approach, we must know the number of bytes consumed by an object of any given type. To determine the memory consumption of an object, we add the amount of memory used by each of its instance variables to the overhead associated with each object.

Python does not define the sizes of the built-in data types that we have been using (int, float, bool, str, and list); the sizes of objects of those types differ from system to system. Accordingly, the sizes of data types that you create also will differ from system to system because they are based on these built-in data types. The function call sys.getsizeof(x) returns the number of bytes that a built-in object x consumes on your system. The numbers that we give in this section are observations gathered by using this function in interactive Python on one typical system. We encourage you to do the same on your computer!

These basic mechanisms are effective for estimating the memory usage of a great many programs, but there are numerous complicating factors that can make the task significantly more difficult. For example, we have already noted the potential effect of caching. Moreover, memory consumption is a complicated dynamic process when function calls are involved because the system memory allocation mechanism plays a more important role. For example, when your program calls a function, the system allocates the memory needed for the function (for its local variables) from a special area of memory called the stack, and when the method returns to the caller, this memory is returned to the stack. For this reason, creating arrays or other large objects in recursive functions is dangerous, since each recursive call implies significant memory usage. When you create an object, the system allocates the memory needed for the object from another special area of memory known as the heap. Every object lives until no references to it remain, at which point a system process known as garbage collection reclaims its memory for the heap. Such dynamics can make the task of precisely estimating memory usage of a program challenging.

Despite all these caveats, it is important for every Python programmer to understand that each object of a user-defined type is likely to consume a large amount of memory. So, a Python program that defines a large number of objects of a user-defined type can use much more space (and time) than you might expect. That is especially true if each object contains only a few instance variables—in that case, the ratio of memory devoted to overhead versus memory devoted to instance variables is very high. For example, if you compare the performance of our Complex type with Python’s built-in complex type for mandelbrot.py, you will certainly notice this effect. Numerous object-oriented languages have come and gone since the concept was introduced decades ago, and many of them eventually embraced lightweight objects for user-defined types. Python offers two advanced features for this purpose—named tuples and slots—but we will not take advantage of such memory optimizations in this book.

Perhaps the most common mistake made in programming is to pay too much attention to performance characteristics. Your first priority is to make your code clear and correct. Modifying a program for the sole purpose of speeding it up is best left for experts. Indeed, doing so is often counterproductive, as it tends to create code that is complicated and difficult to understand. C. A. R. Hoare (the inventor of quicksort and a leading proponent of composing clear and correct code) once summarized this idea by saying that “premature optimization is the root of all evil,” to which Knuth added the qualifier “(or at least most of it) in programming.” Beyond that, improving the running time is not worthwhile if the available cost benefits are insignificant. For example, improving the running time of a program by a factor of 10 is inconsequential if the running time is only an instant. Even when a program takes a few minutes to run, the total time required to implement and debug an improved algorithm might be substantially longer than the time required simply to run a slightly slower one—you may as well let the computer do the work. Worse, you might spend a considerable amount of time and effort implementing ideas that do not actually make a program any faster.

Perhaps the second most common mistake made in developing an algorithm is to ignore performance characteristics. Faster algorithms are often more complicated than brute-force solutions, so you might be tempted to accept a slower algorithm to avoid having to deal with more complicated code. However, you can sometimes reap huge savings with just a few lines of good code. Users of a surprising number of computer systems lose substantial time waiting for simple quadratic algorithms to finish solving a problem, even though linear or linearithmic algorithms are available that are only slightly more complicated and could therefore solve the problem in a fraction of the time. When we are dealing with huge problem sizes, we often have no choice but to seek better algorithms.

Improving a program to make it clearer, more efficient, and elegant should be your goal every time that you work on it. If you pay attention to the cost all the way through the development of a program, you will reap the benefits every time you use it.

A. Not really. The definition of “very large” is system dependent. For most practical purposes, you can consider operations applied to 32- or 64-bit integers to work in constant time. Modern applications in cryptography involve huge numbers with hundreds or thousands of digits.

Q. How do I find out how long it takes to add or multiply two floats on my computer?

A. Run some experiments! The program timeops.py on the booksite uses Stopwatch to test the execution time of various arithmetic operations on integers and floats. This technique measures the actual elapsed time as would be observed on a wall clock. If your system is not running many other applications, it can produce accurate results. Python also includes the timeit module for measuring the running time of small code fragments.

Q. Is there any way to measure processor time instead of wall clock time?

A. On some systems, the function call time.clock() returns the current processor time as a float, expressed in seconds. When available, you should substitute time.time() with time.clock() for benchmarking Python programs.

Q. How much time do functions such as math.sqrt(), math.log(), and math.sin() take?

A. Run some experiments! Stopwatch makes it easy to compose programs such as timeops.py to answer questions of this sort for yourself. You will be able to use your computer much more effectively if you get in the habit of doing so.

Q. Why does allocating an array (Python list) of size n take time proportional to n?

A. Python initializes all array elements to whatever values the programmer specifies. That is, in Python there is no way to allocate memory for an array without also assigning an object reference to each element of the array. Assigning object references to each element of an array of size n takes time proportional to n.

Q. How do I find out how much memory is available for my Python programs?

A. Since Python will raise a MemoryError when it runs out of memory, it is not difficult to run some experiments. For example, use this program (bigarray.py):

import sys
import stdarray
import stdio

n = int(sys.argv[1])
a = stdarray.create1D(n, 0)
stdio.writeln('finished')

and run it like this:

Click here to view code image

% python bigarray.py 100000000
finished

to show that you have room for 100 million integers. But if you type

Click here to view code image

% python bigarray.py 1000000000

Python will hang, crash, or raise a run-time error; you can conclude that you do not have room for an array of 1 billion integers.

Q. What does it mean when someone says that the worst-case running time of an algorithm is O(n²)?

A. That is an example of a notation known as big-O notation. We write f(n) is O(g(n)) if there exist constants c and n₀ such that f(n) ≤ c g(n) for all n > n₀. In other words, the function f(n) is bounded above by g(n), up to constant factors and for sufficiently large values of n. For example, the function 30n² + 10n+ 7 is O(n²). We say that the worst-case running time of an algorithm is O(g(n)) if the running time as a function of the input size n is O(g(n)) for all possible inputs. This notation is widely used by theoretical computer scientists to prove theorems about algorithms, so you are sure to see it if you take a course in algorithms and data structures. It provides a worst-case performance guarantee.

Q. So can I use the fact that the worst-case running time of an algorithm is O(n³) or O(n²) to predict performance?

A. No, because the actual running time might be much less. For example, the function 30n² + 10n+ 7 is O(n²), but it is also O(n³) and O(n¹⁰) because big-O notation provides only an upper bound on the worst-case running time. Moreover, even if there is some family of inputs for which the running time is proportional to the given function, perhaps these inputs are not encountered in practice. Consequently, you cannot use big-O notation to predict performance. The tilde notation and order-of-growth classifications that we use are more precise than big-O notation because they provide matching upper and lower bounds on the growth of the function. Many programmers incorrectly use big-O notation to indicate matching upper and lower bounds.

Q. How much memory does Python typically use to store a tuple of n items?

A. 56 + 8n bytes, plus whatever memory is needed for the objects themselves. This is a bit less than for arrays because Python can implement a tuple (at the machine level) using an array instead of a resizing array.

Q. Why does Python use so much memory (280 bytes) to store a dictionary that maps an object’s instance variables to its values?

A. In principle, different objects from the same data type can have different instance variables. In this case, Python would need some way to manage an arbitrary number of possible instance variables for each object. But most Python code does not call for this (and, as a matter of style, we never need it in this book).

4.1.2 Modify threesum.py to take a command-line argument x and find a triple of numbers on standard input whose sum is closest to x.

4.1.3 Compose a program foursum.py that reads an integer n from standard input, then reads n integers from standard input, and counts the number of distinct 4-tuples that sum to zero. Use a quadruply nested loop. What is the order of growth of the running time of your program? Estimate the largest n that your program can handle in an hour. Then, run your program to validate your hypothesis.

4.1.4 Prove that 1 + 2 + ... + n = n(n+1)/2.

Solution: We proved this by induction at the beginning of SECTION 2.3. Here is the basis for another proof:

4.1.5 Prove by induction that the number of distinct triples of integers between 0 and n–1 is n(n–1)(n–2)/6.

Solution: The formula is correct for n = 2. For n > 2, count all the triples that do not include n, which is (n–1)(n–2)(n–3)/6 by the inductive hypothesis, and all the triples that do include n–1, which is (n–1)(n–2)/2, to get the total

(n–1)(n–2)(n–3)/6 + (n–1)(n–2)/2 = n(n–1)(n–2)/6.

4.1.6 Show by approximating with integrals that the number of distinct triples of integers between 0 and n–1 is about n³/6.

Solution:

4.1.7 What is the value of x (as a function of n) after running the following code fragment?

Click here to view code image

x = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            x += 1

Solution: n (n–1) (n–2) / 6.

4.1.8 Use tilde notation to simplify each of the following formulas, and give the order of growth of each:

a. n(n – 1)(n – 2) (n – 3)/24
b. (n – 2) (lg n – 2) (lg n +2)
c. n(n +1) – n²
d. n(n +1)/2 +n lg n
e. ln((n – 1)(n – 2) (n – 3))²

4.1.9 Is the following code fragment linear, quadratic, or cubic (as a function of n)?

Click here to view code image

for i in range(n):
    for j in range(n):
        if i == j: c[i][j] = 1.0
        else: c[i][j] = 0.0

4.1.10 Suppose the running time of an algorithm on inputs of size 1,000, 2,000, 3,000, and 4,000 is 5 seconds, 20 seconds, 45 seconds, and 80 seconds, respectively. Estimate how long it will take to solve a problem of size 5,000. Is the algorithm linear, linearithmic, quadratic, cubic, or exponential?

4.1.11 Which would you prefer: a quadratic, linearithmic, or linear algorithm?

Solution: While it is tempting to make a quick decision based on the order of growth, it is very easy to be misled by doing so. You need to have some idea of the problem size and of the relative value of the leading coefficients of the running time. For example, suppose that the running times are n² seconds, 100 n log₂ n seconds, and 10,000n seconds. The quadratic algorithm will be fastest for n up to about 1,000, and the linear algorithm will never be faster than the linearithmic one (n would have to be greater than 2¹⁰⁰—far too large to bother considering).

4.1.12 Apply the scientific method to develop and validate a hypothesis about order of growth of the running time of the following code fragment, as a function of the argument n:

def f(n):
    if (n == 0): return 1
    return f(n-1) + f(n-1)

4.1.13 Apply the scientific method to develop and validate a hypothesis about order of growth of the running time of each of the following code fragments as a function of n:

Click here to view code image

s = ''
for i in range(n):
    if stdrandom.bernoulli(0.5): s += '0'
    else:                        s += '1'

s = ''
for i in range(n):
    oldS = s
    if stdrandom.bernoulli(0.5): s += '0'
    else:                        s += '1'

Solution: On many systems, the first is linear; the second is quadratic. You have no way of knowing why: In the first case, Python detects that s is the only variable that refers to the string, so it appends each character to the string as it would with a list (in amortized constant time) even though the string is immutable! A safer alternative is to create a list containing the characters and concatenate them together with by calling the join() method.

Click here to view code image

a = []
for i in range(n):
    if stdrandom.bernoulli(0.5): a += ['0']
    else:                        a += ['1']
s = ''.join(a)

4.1.14 Each of the four Python functions below returns a string of length n whose characters are all x. Determine the order of growth of the running time of each function. Recall that concatenating two strings in Python takes time proportional to the sum of their lengths.

Click here to view code image

def f1(n):
    if (n == 0):
        return ''
    temp = f1(n // 2)
    if (n % 2 == 0): return temp + temp
    else:            return temp + temp + 'x'

def f2(n):
    s = ''
    for i in range(n):
        s += 'x'
    return s

def f3(n):
    if (n == 0): return ''
    if (n == 1): return 'x'
    return f3(n//2) + f3(n - n//2)

def f4(n):
    temp = stdarray.create1D(n, 'x')
    return ''.join(temp)

def f5(n):
    return 'x' * n

4.1.15 Each of the three Python functions below returns the reverse of a string of length n. What is the order of growth of the running time of each function?

Click here to view code image

def reverse1(s):
    n = len(s)
    reverse = ''
    for i in range(n):
        reverse = s[i] + reverse
    return reverse

def reverse2(s):
    n = len(s)
    if (n <= 1):
        return s
    left = s[0 : n//2]
    right = s[n//2 : n]
    return reverse2(right) + reverse2(left)

def reverse3(s):
    return s[::-1]

The slice expression s[::-1] uses an optional third argument to specify the step size.

4.1.16 The following code fragment (adapted from a Java programming book) creates a random permutation of the integers from 0 to n–1. Determine the order of growth of its running time as a function of n. Compare its order of growth with the shuffling code in SECTION 1.4.

Click here to view code image

a = stdarray.create1D(n, 0)
taken = stdarray.create1D(n, False)
count = 0
while (count < n):
    r = stdrandom.uniform(0, n)
    if not taken[r]:
        a[r] = count
        taken[r] = True
        count += 1

4.1.17 How many times does the following code fragment execute the first if statement in the triply nested loop?

Click here to view code image

for i in range(n):
    for j in range(n):
        for k in range(n):
            if (i < j) and (j < k):
                if a[i] + a[j] + a[k] == 0:
                    count += 1

Use tilde notation to simply your answer.

4.1.18 Apply the scientific method to develop and validate a hypothesis about order of growth of the running time of the collect() method in coupon.py (PROGRAM 2.1.3), as a function of the argument n. Note: Doubling is not effective for distinguishing between the linear and linearithmic hypotheses—you might try squaring the size of the input.

4.1.19 Apply the scientific method to develop and validate a hypothesis about order of growth of the running time of markov.py (PROGRAM 1.6.3), as a function of the arguments moves and n.

4.1.20 Compose a program mooreslaw.py that takes a command-line argument n and writes the increase in processor speed over a decade if processor speed doubles every n months. How much will processor speed increase over the next decade if speeds double every n = 15 months? 24 months?

4.1.21 Using the memory model from the text, give the memory requirements for each object of the following data types from CHAPTER 3:

a. Stopwatch
b. Turtle
c. Vector
d. Body
e. Universe

4.1.22 Estimate, as a function of the grid size n, the amount of memory used by visualizev.py (PROGRAM 2.4.4) with vertical percolation detection (PROGRAM 2.4.2). Extra credit: Answer the same question for the case where the recursive percolation detection method percolation.py (PROGRAM 2.4.6) is used.

4.1.23 Estimate the size of the largest n-by-n array of integers that your computer can hold, and then try to allocate such an array.

4.1.24 Estimate, as a function of the number of documents n and the dimension d, the amount of space used by comparedocuments.py (PROGRAM 3.3.5).

4.1.25 Compose a version of primesieve.py (PROGRAM 1.4.3) that uses an array of integers instead of an array of booleans and uses 32 bits in each integer, to raise the largest value of n that it can handle by a factor of 32.

4.1.26 The following table gives running times for various programs for various values of n. Fill in the blanks with estimates that you think are reasonable on the basis of the information given.

Give hypotheses for the order of growth of the running time of each program.

4.1.28 Closest pair. Design a quadratic algorithm that finds the pair of integers that are closest to each other. (In the next section you will be asked to find a linearithmic algorithm.)

4.1.29 Power law. Show that a log-log plot of the function cn^b has slope b and x-intercept log c. What are the slope and x-intercept for 4 n³ (log n)² ?

4.1.30 Sum furthest from zero. Design an algorithm that finds the pair of integers whose sum is furthest from zero. Can you discover a linear-time algorithm?

4.1.31 The “beck” exploit. A popular web server supports a function no2slash() whose purpose is to collapse multiple / characters. For example, the string /d1///d2////d3/test.html becomes /d1/d2/d3/test.html. The original algorithm was to repeatedly search for a / and copy the remainder of the string:

Click here to view code image

def no2slash(name):
    for x in range(1, len(name)):
        if x > 0:
             if (name[x-1] == '/') and (name[x] == '/'):
                 for y in range(x+1, len(name)):
                     name[y-1] = name[y]
             else:
                 x += 1

Unfortunately, the running time of this code is quadratic in the number of / characters in the input. By sending multiple simultaneous requests with large numbers of / characters, a hacker can deluge a server and starve other processes for CPU time, thereby creating a denial-of-service attack. Develop a version of no2slash() that runs in linear time and does not allow for this type of attack.

4.1.32 Young tableaux. Suppose you have in memory an n-by-n array of integers a[][] such that a[i][j] < a[i+1][j] and a[i][j] < a[i][j+1] for all i and j, like the table below:

 5  23  54  67  89
 6  69  73  74  90
10  71  83  84  91
60  73  84  86  92
99  91  92  93  94

Devise an algorithm whose order of growth is linear in n to determine whether a given integer x is in a given Young tableaux.

4.1.33 Subset sum. Compose a program anysum.py that takes an integer n from standard input, then reads n integers from standard input, and counts the number of subsets that sum to 0. Give the order of growth of the running time of your program.

4.1.34 Array rotation. Given an array of n elements, give a linear-time algorithm to rotate the array by k positions. That is, if the array contains a₀, a₁, ..., a_n-1, the rotated array is a_k, a_k+1, ..., a_n-1, a₀, ..., a_k-1. Use at most a constant amount of extra space (array indices and array values). Hint: Reverse three subarrays.

4.1.35 Finding a duplicated integer. (a) Given an array of n integers from 1 to n with one value repeated twice and one missing, give an algorithm that finds the missing integer, in linear time and constant extra space. (b) Given a read-only array of n integers, where each value from 1 to n–1 occurs once and one occurs twice, give an algorithm that finds the duplicated value, in linear time and constant extra space. (c) Given a read-only array of n integers with values between 1 and n–1, give an algorithm that finds a duplicated value, in linear time and constant extra space.

4.1.36 Factorial. Design a fast algorithm to compute n! for large values of n. Use your program to compute the longest run of consecutive 9s in 1000000!. Develop and validate a hypothesis for the order of growth of the running time of your algorithm.

4.1.37 Maximum sum. Design a linear-time algorithm that finds a contiguous subsequence of at most m in a sequence of n integers that has the highest sum among all such subsequences. Implement your algorithm, and confirm that the order of growth of its running time is linear.

4.1.38 Pattern matching. Given an n-by-n array of black (1) and white (0) pixels, design a linear algorithm that finds the largest square subarray that consists of entirely black pixels. As an example, the following 8-by-8 array contains a 3-by-3 subarray entirely of black pixels:

1 0 1 1 1 0 0 0
0 0 0 1 0 1 0 0
0 0 1 1 1 0 0 0
0 0 1 1 1 0 1 0
0 0 1 1 1 1 1 1
0 1 0 1 1 1 1 0
0 1 0 1 1 0 1 0
0 0 0 1 1 1 1 0

Implement your algorithm and confirm that the order of growth of its running time is linear in the number of pixels. Extra credit: Design an algorithm to find the largest rectangular black subarray.

4.1.39 Maximum average. Compose a program that finds a contiguous subarray of at most m elements in an array of n integers that has the highest average value among all such subarrays, by trying all subarrays. Use the scientific method to confirm that the order of growth of the running time of your program is mn². Next, compose a program that solves the problem by first computing prefix[i] = a[0] + ... + a[i] for each i, then computing the average in the interval from a[i] to a[j] with the expression (prefix[j] - prefix[i]) / (j - i + 1). Use the scientific method to confirm that this method reduces the order of growth by a factor of n.

4.1.40 Sub-exponential function. Find a function whose order of growth is larger than any polynomial function, but smaller than any exponential function. Extra credit: Compose a program whose running time has that order of growth.

4.1.41 Resizing arrays. For each of the following strategies, either show that each resizing array operation takes constant amortized time or find a sequence of n operations (starting from an empty data structure) that takes quadratic time.

a. Double the capacity of the resizing array when it is full and halve the capacity when it is half full.

b. Double the capacity of the resizing array when it is full and halve the capacity when it is one-third full.

c. Increase the capacity of the resizing array by a factor of 9/8 when it is full and decrease it by a factor of 9/8 when it is 80% full.

Sorting and searching are important for commercial applications (businesses keep customer files in order) and scientific applications (to organize data and computation), and have all manner of applications in fields that may appear to have little to do with keeping things in order, including data compression, computer graphics, computational biology, numerical computing, combinatorial optimization, cryptography, and many others.

We use these fundamental problems to illustrate the idea that efficient algorithms are one key to effective solutions for computational problems. Indeed, many different sorting and searching algorithms have been proposed. Which should we use to address a given task? This question is important because different algorithms can have vastly differing performance characteristics, enough to make the difference between success in a practical situation and not coming close to doing so, even on the fastest available computer.

In this section, we will consider in detail two classical algorithms for sorting and searching, along with several applications in which their efficiency plays a critical role. With these examples, you will be convinced not just of the utility of these algorithms, but also of the need to pay attention to the cost whenever you address a problem that requires a significant amount of computation.

• Base case: If hi –lo equals 1, then the secret number is lo.

• Recursive step: Otherwise, ask whether the secret number is greater than or equal to the number mid = (hi + lo) / 2. If so, look for the number in [mid, hi); if not, look for the number in [lo, mid).

This strategy is an example of the general problem-solving algorithm known as binary search, which has many applications. PROGRAM 4.2.1 (questions.py) is an implementation.

• The interval always contains the secret number.

• The interval lengths are the powers of 2, decreasing from 2^k.

The first of these facts is enforced by the code; the second follows by noting that if (hi–lo) is a power of 2, then (hi – lo) / 2 is the next smaller power of 2 and also the length of both halved intervals. These facts are the basis of an induction proof that the algorithm operates as intended. Eventually, the interval length becomes 1, so we are guaranteed to find the number.

T(n) = T(n/2) + 1

with T(1) = 0. Substituting 2^k for n, we can telescope the recurrence (apply it to itself) to immediately get a closed-form expression:

T(2^k) = T(2^k–1) + 1 = T(2^k–2) + 2 = ... = T(1) + k = k.

Substituting back n for 2^k (and lg n for k) gives the result

T(n) = lg n

We normally use this equation to justify a hypothesis that the running time of a program that uses binary search is logarithmic. Note: Binary search and questions.search() work even when n is not a power of 2 (see EXERCISE 4.2.1).

Thinking in terms of the binary representation is another way to understand the linear–logarithmic chasm: when we have a program whose running time is linear in a parameter n, its running time is proportional to the value of n, whereas a logarithmic running time is just proportional to the number of digits in n. In a context that is perhaps slightly more familiar to you, think about the following question, which illustrates the same point: would you rather earn $6 or a six-figure salary?

PROGRAM 4.2.2 (bisection.py) implements this strategy. We start with an interval (lo, hi) known to contain x and use the following recursive procedure:

• Compute mid = (hi + lo) / 2.

• Base case: If hi – lo is less than δ, then return mid as an estimate of x.

• Recursive step: Otherwise, test whether f(mid) > y. If so, look for x in (lo, mid); if not, look for x in (mid, hi).

The key to this approach is the idea that the function is increasing—for any values a and b, knowing that f(a) < f(b) tells us that a < b, and vice versa. The recursive step just applies this knowledge: knowing that y = f(x) < f(mid) tells us that x < mid, so that x must be in the interval (lo, mid), and knowing that y = f(x) > f(mid) tells us that x > mid, so that x must be in the interval (mid, hi). You can think of the problem as determining which of the n = (hi–l o) / δ tiny intervals of length δ within (lo, hi) contains x, with running time logarithmic in n. As with converting an integer to binary, we determine one bit of x in each iteration. In this context, binary search is often called bisection search because we bisect the interval at each stage.

The test client in binarysearch.py is known as an exception filter: it reads in a sorted array of strings from a file (which we refer to as the whitelist) and an arbitrary sequence of strings from standard input, and writes those in the sequence that are not in the whitelist. Exception filters have many direct applications. For example, if the whitelist is the words from a dictionary and standard input is a text document, the exception filter will write the misspelled words. Another example arises in web applications: your email application might use an exception filter to reject any messages that are not on a whitelist that contains the email addresses of your friends, or your operating system might have an exception filter that disallows network connections to your computer from any device having an IP address that is not on a preapproved whitelist.

Fast algorithms are an essential element of the modern world, and binary search is a prototypical example that illustrates the impact of fast algorithms. Whether it be extensive experimental data or detailed representations of some aspect of the physical world, modern scientists are awash in vast amounts of data. With a few quick calculations, you can convince yourself that problems like finding all the misspelled words in a document or protecting your computer from intruders using an exception filter require a fast algorithm like binary search. Take the time to do so—a fast algorithm can certainly make the difference between being able to solve a problem easily and spending substantial resources trying to do so (and failing). You can find the exceptions in a million-word document to a million-entry whitelist in an instant, whereas that task might take days or weeks using the brute-force algorithm. Nowadays, web companies routinely provide services that are based on using binary search billions of times in arrays with billions of elements—without a fast algorithm like binary search, we could not contemplate such services.

The brute-force algorithm we consider is known as insertion sort. It is based on a simple approach that people often use to arrange hands of playing cards—that is, consider the cards one at a time and insert each into its proper place among those already considered (keeping them sorted).

PROGRAM 4.2.4 (insertion.py) contains an implementation of a sort() function that mimics this process to sort elements in an array a[] of length n. The test client reads all the strings from standard input, puts them into the array, calls the sort() function to sort them, and then writes the sorted result to standard output.

In insertion.sort(), the outer for loop sorts the first i elements in the array. The inner while loop completes the sort by putting a[i] into its proper position in the array, as in the following example when i is 6:

Element a[i] is put in its place among the sorted elements to its left by exchanging it (using a tuple-packing variant of the exchange() function that we first encountered in SECTION 2.1) with each larger element to its left, moving from right to left, until it reaches its proper position. The black elements in the three bottom rows in this trace are the ones that are compared (and exchanged, on all but the final iteration).

The insertion process just described is executed first with i equal to 1, then 2, then 3, and so forth, as illustrated in the trace at the top of the next page. When i reaches the end of the array, the whole array is sorted.

This trace displays the contents of the array each time the outer for loop completes, along with the value of j at that time. The highlighted element is the one that was in a[i] at the beginning of the loop, and the other elements printed in black are the other ones that were involved in exchanges and moved to the right one position within the loop. Since the elements a[0] through a[i-1] are in sorted order when the loop completes for each value of i, they are, in particular, in sorted order the final time the loop completes, when the value of i is len(a). This discussion again illustrates the first thing that you need to do when studying or developing a new algorithm: convince yourself that it is correct. Doing so provides the basic understanding that you need to study its performance and use it effectively.

1 + 2 + ... + n–1 ~ n² /2

and the running time is quadratic (see EXERCISE 4.1.4). To understand the performance of insertion sort for randomly ordered arrays, take a careful look at the trace: it is an n-by-n array with one black element corresponding to each exchange. That is, the number of black elements is the frequency of execution of instructions in the inner loop. We expect that each new element to be inserted is equally likely to fall into any position, so that element will move halfway to the left on average. Thus, on the average, we expect only about one-half the elements below the diagonal (about n²/4 in total) to be black. This observation leads immediately to the hypothesis that the expected running time of insertion sort for a randomly ordered array is quadratic.

Happily, our insertion sort and binary search functions work not only with strings but also with any data type that is comparable. Recall from SECTION 3.3 that a data type is comparable if it implements the six comparison methods and they define a total order. Python’s built-in int, float, and str types are all comparable.

You can make a user-defined type comparable by implementing the six special methods corresponding to the <, <=, ==, !=, >=, and > operators. In fact, our insertion sort and binary search functions rely on only the < operator, but it is better style to implement all six special methods.

A more general design is sometimes appropriate for user-defined types. For example, a teacher might wish to sort a file of student grade records by name on some occasions and by grade on some other occasions. One solution that is often used to handle such situations is to pass the function that is to be used to compare keys as an argument to the sort function.

It is more likely than not in natural applications that the running time of insertion sort is quadratic, so we need to consider faster sorting algorithms. As we know from SECTION 4.1, a back-of-the-envelope calculation can tell us that having a faster computer is not much help. A dictionary, a scientific database, or a commercial database can contain billions of elements; how can we sort such a large array? Next, we turn to a classic algorithm for addressing this question.

We process contiguous subarrays of a given array, using the notation a [lo, hi) to refer to a[lo], a[lo+1], ..., a[hi–1], (adopting the same convention as we used for binary search to denote a half-open interval that excludes a[hi]). To sort a[lo, hi), we use the following recursive strategy:

• Base case: If the length of the subarray is 0 or 1, it is already sorted.

• Recursive step: Otherwise, compute mid = (hi + lo) / 2, sort (recursively) the two subarrays a [lo, mid) and a [mid, hi), and merge them.

PROGRAM 4.2.6 (merge.py) is an implementation of this algorithm. The array elements are rearranged by the code that follows the recursive calls, which merges the two halves of the array that were sorted by the recursive calls. As usual, the easiest way to understand the merge process is to study a trace of the contents of the array during the merge. The code maintains one index i into the first half, another index j into the second half, and a third index k into an auxiliary array aux[] that holds the result. The merge implementation is a single loop that sets aux[k] to either a[i] or a[j] (and then increments k and the index for the value that is used). If either i or j has reached the end of its subarray, aux[k] is set from the other; otherwise, it is set to the smaller of a[i] or a[j]. After all of the elements from the two halves have been copied to aux[], the sorted result is copied back to the original array. Take a moment to study the trace just given to convince yourself that this code always properly combines the two sorted subarrays to sort the full array.

The recursive method ensures that the two halves of the array are put into sorted order before the merge. Again, the best way to gain an understanding of this process is to study a trace of the contents of the array each time the recursive sort() method returns. Such a trace for our example is shown next. First a[0] and a[1] are merged to make a sorted subarray in a[0, 2), then a[2] and a[3] are merged to make a sorted subarray in a[2, 4), then these two subarrays of size 2 are merged to make a sorted subarray in a[0, 4), and so forth. If you are convinced that the merge works properly, you need only convince yourself that the code properly divides the array to be convinced that the sort works correctly. Note that when the number of elements is not even, the left half will have one fewer element than the right half.

You are encouraged to run these tests on your computer. If you do so, you certainly will appreciate that merge.sort() is much faster for large arrays than is insertion.sort() and that you can sort huge arrays with relative ease. Validating the hypothesis that the running time is linearithmic (and not linear) is a bit more work, but you certainly can see that mergesort scales, making it possible for us to address sorting problems that we could not contemplate solving with a brute-force algorithm such as insertion sort.

Mergesort traces back to john von Neumann, an accomplished physicist, who was among the first to recognize the importance of computation in scientific research. Von Neumann made many contributions to computer science, including a basic conception of the computer architecture that has been used since the 1950s. When it came to applications programming, von Neumann recognized that:

• Sorting is an essential ingredient in many applications.

• Quadratic algorithms are too slow for practical purposes.

• A divide-and-conquer approach is effective.

• Proving programs correct and knowing their cost is important.

Computers are many orders of magnitude faster and have many orders of magnitude more memory, but these basic concepts remain important today. People who use computers effectively and successfully know, as did von Neumann, that brute-force algorithms are often only a start. That Python and other modern systems still use von Neumann’s method is testimony to the power of these ideas.

to be or not to be to

then the result of the sort is

be be not or to to to

with equal strings, such as the two occurrences of be and the three occurrences of to, brought together in the array. Now, with equal strings all together in the array, we can make a single pass through the array to compute all of the frequencies. The Counter data type (PROGRAM 3.3.2) is the perfect tool for the job. Recall that a Counter has a string instance variable (initialized to the constructor argument), a count instance variable (initialized to 0), and an increment() method, which increments the counter by 1. We maintain a Python list zipf[] of Counter objects and do the following for each string:

• If the string is not equal to the previous one, create a new Counter and append it to the end of zipf[].

• Increment the most recently created Counter.

At the end of this process, zipf[i] contains the ith string and its frequency.

You are likely to find yourself composing a program sometime in the future for a simple task that could easily be solved by first using a sort. With a linearithmic sorting algorithm such as mergesort, you can address such problems even for huge data sets. PROGRAM 4.2.7 (frequencycount.py), which uses two different sorts, is a prime example. Without a good algorithm (and an understanding of its performance characteristics), you might find yourself frustrated by the idea that your fast and expensive computer cannot solve a problem that seems to be a simple one. With an ever-increasing set of problems that you know how to solve efficiently, you will find that your computer can be a much more effective tool than you now imagine.

Since the advent of computing, people have been developing algorithms such as binary search and mergesort that can efficiently solve practical problems. The field of study known as design and analysis of algorithms encompasses the study of design paradigms like divide-and-conquer, techniques to develop hypotheses about algorithms’ performance, and algorithms for solving fundamental problems like sorting and searching that can be put to use for practical applications of all kinds. Implementations of many of these algorithms are found in Python libraries or other specialized libraries, but understanding these basic tools of computation is like understanding the basic tools of mathematics or science. You can use a matrix-processing package to find the eigenvalues of a matrix, but you still need a course in linear algebra to apply the concepts and interpret the results. Now that you know that a fast algorithm can make the difference between spinning your wheels and properly addressing a practical problem, you can be on the lookout for situations where efficient algorithms like binary search and mergesort can do the job or opportunities where algorithm design and analysis can make the difference.

A. To spare ourselves considerable pain. Binary search is a notable example. For example, you now understand binary search; a classic programming exercise is to compose a version that uses a while loop instead of recursion. Try solving EXERCISES 4.2.1–3 without looking back at the code in the book. In a famous experiment, Jon Bentley once asked several professional programmers to do so, and most of their solutions were not correct.

Q. Why introduce the mergesort algorithm when Python provides an efficient sort() method defined in the list data type?

A. As with many topics we have studied, you will be able to use such tools more effectively if you understand the background behind them.

Q. What is the running time of the following version of insertion sort on an array that is already sorted?

Click here to view code image

def sort(a):
    n = len(a)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if a[j] < a[j-1]: exchange(a, j, j-1)
            else:             break

A. Quadratic time in Python 2; linear time in Python 3. The reason is that, in Python 2, range() is a function that returns an array of integers of length equal to the length of the range (which can be wasteful if the loop terminates early because of a break or return statement). In Python 3, range() returns an iterator, which generates only as many integers as needed.

Q. What happens if I try to sort an array of elements that are not all of the same type?

A. If the elements are of compatible types (such as int and float), everything works fine. For example, mixed numeric types are compared according to their numeric value, so 0 and 0.0 are treated as equal. If the elements are of incompatible types (such as str and int), then Python 3 raises a TypeError at run time. Python 2 supports some mixed-type comparisons, using the name of the class to determine which object is smaller. For example, Python 2 treats all integers as less than all strings because 'int' is lexicographically less than 'str'.

Q. Which order is used when comparing strings with operators such as == and < ?

A. Informally, Python uses lexicographic order to compare two strings, as words in a book index or dictionary. For example 'hello' and 'hello' are equal, 'hello' and 'goodbye' are unequal, and 'goodbye' is less than 'hello'. More formally, Python first compares the first character of each string. If those characters differ, then the strings as a whole compare as those two characters compare. Otherwise, Python compares the second character of each string. If those characters differ, then the strings as a whole compare as those two characters compare. Continuing in this manner, if Python reaches the ends of the two strings simultaneously, then it considers them to be equal. Otherwise, it considers the shorter string to be the smaller one. Python uses Unicode for character-by-character comparisons. We list a few of the most important properties:

• '0' is less than '1', and so forth.

• 'A' is less than 'B', and so forth.

• 'a' is less than 'b', and so forth.

• Decimal digits ('0' to '9') are less than the uppercase letters ('A' to 'Z').

• Uppercase letters ('A' to 'Z') are less than lowercase letters ('a' to 'z').

4.2.2 Compose a nonrecursive version of binary search (PROGRAM 4.2.3).

4.2.3 Modify binarysearch.py so that if the search key is in the array, it returns the smallest index i for which a[i] is equal to key, and otherwise it returns the largest index i for which a[i] is smaller than key (or –1 if no such index exists).

4.2.4 Describe what happens if you apply binary search to an unordered array. Why shouldn’t you check whether the array is sorted before each call to binary search? Could you check that the elements binary search examines are in ascending order?

4.2.5 Describe why it is desirable to use immutable keys with binary search.

4.2.6 Let f() be a monotonically increasing function with f(a) < 0 and f(b) > 0. Compose a program that computes a value x such that f(x) = 0 (up to a given error tolerance).

4.2.7 Add code to insertion.py to produce the trace given in the text.

4.2.8 Add code to merge.py to produce the trace given in the text.

4.2.9 Give traces of insertion sort and mergesort in the style of the traces in the text, for the input it was the best of times it was.

4.2.10 Compose a program dedup.py that reads strings from standard input and writes them to standard output with all duplicates removed (and in sorted order).

4.2.11 Compose a version of mergesort (PROGRAM 4.2.6) that creates an auxiliary array in each recursive call to _merge() instead of creating only one auxiliary array in sort() and passing it as an argument. What impact does this change have on performance?

4.2.12 Compose a nonrecursive version of mergesort (PROGRAM 4.2.6).

4.2.13 Find the frequency distribution of words in your favorite book. Does it obey Zipf’s law?

4.2.14 Analyze mergesort mathematically when n is a power of 2, as we did for binary search.

Solution: Let M(n) be the frequency of execution of the instructions in the inner loop. Then M(n) must satisfy the following recurrence relation:

M(n) = 2M(n/2) + n

with M(1) = 0. Substituting 2^k for n gives

M(2^k) = 2 M(2^k–1) + 2^k

which is similar to but more complicated than the recurrence that we considered for binary search. But if we divide both sides by 2^k, we get

M(2^k)/2^k = M(2^k–1)/2^k–1 + 1

which is precisely the recurrence that we had for binary search. That, is M(2^k)/ 2^k = T(2^k) = k. Substituting back n for 2^k (and lg n for k) gives the result M(n) = n lg n.

4.2.15 Analyze mergesort for the case when n is not a power of 2.

Partial solution: When n is an odd number, one subarray has to have one more element than the other, so when n is not a power of 2, the subarrays on each level are not necessarily all the same size. Still, every element appears in some subarray, and the number of levels is still logarithmic, so the linearithmic hypothesis is justified for all n.

4.2.16 Median. Implement the function median() in stdstats.py so that it computes the median in linearithmic time. Hint: Reduce to sorting.

4.2.17 Mode. Add to stdstats.py a function mode() that computes in linearithmic time the mode (the value that occurs most frequently) of a sequence of n integers. Hint: Reduce to sorting.

4.2.18 Integer sort. Compose a linear-time filter that reads from standard input a sequence of integers that are between 0 and 99 and writes the integers in sorted order to standard output. For example, presented with the input sequence

Click here to view code image

98 2 3 1 0 0 0 3 98 98 2 2 2 0 0 0 2

your program should write the output sequence

Click here to view code image

0 0 0 0 0 0 1 2 2 2 2 2 3 3 98 98 98

4.2.19 Floor and ceiling. Given a sorted array of n comparable keys, compose functions floor() and ceiling() that return the index of the largest (or smallest) key not larger (or smaller) than an argument key in logarithmic time.

4.2.20 Bitonic maximum. An array is bitonic if it consists of an increasing sequence of keys followed immediately by a decreasing sequence of keys. Given a bitonic array, design a logarithmic algorithm to find the index of a maximum key.

4.2.21 Search in a bitonic array. Given a bitonic array of n distinct integers, design a logarithmic-time algorithm to determine whether a given integer is in the array.

4.2.22 Closest pair. Given an array of n floats, compose a function to find in linearithmic time the pair of integers that are closest in value.

4.2.23 Furthest pair. Given an array of n floats, compose a function to find in linear time the pair of integers that are furthest apart in value.

4.2.24 Two sum. Compose a function that takes as an argument an array of n integers and determines in linearithmic time whether any two of them sum to 0.

4.2.25 Three sum. Compose a function that takes as an argument an array of n integers and determines whether any three of them sum to 0. Your program should run in time proportional to n² log n. Extra credit: Develop a program that solves the problem in quadratic time.

4.2.26 Majority. Given an array of n elements, an element is a majority if it appears more than n/2 times. Compose a function that takes an array of n strings as an argument and identifies a majority (if it exists) in linear time.

4.2.27 Common element. Compose a function that takes as an argument three arrays of strings, determines whether there is any string common to all three arrays, and if so, returns one such string. The running time of your method should be linearithmic in the total number of strings.

4.2.28 Largest empty interval. Given n timestamps for when a file is requested from web server, find the largest interval of time in which no file is requested. Compose a program to solve this problem in linearithmic time.

4.2.29 Prefix-free codes. In data compression, a set of strings is prefix-free if no string is a prefix of another. For example, the set of strings 01, 10, 0010, and 1111 is prefix-free, but the set of strings 01, 10, 0010, 1010 is not prefix-free because 10 is a prefix of 1010. Compose a program that reads in a set of strings from standard input and determines whether the set is prefix-free.

4.2.30 Partitioning. Compose a function that sorts an array that is known to have at most two different values. Hint: Maintain two pointers, one starting at the left end and moving right, and the other starting at the right end and moving left. Maintain the invariant that all elements to the left of the left pointer are equal to the smaller of the two values and all elements to the right of the right pointer are equal to the larger of the two values.

4.2.31 Dutch national flag. Compose a function that sorts an array that is known to have at most three different values. (Edsgar Dijkstra named this the Dutch-national-flag problem because the result is three “stripes” of values like the three stripes in the flag.)

4.2.32 Quicksort. Compose a recursive program that sorts an array of randomly ordered distinct values. Hint: Use a method like the one described in EXERCISE 4.2.31. First, partition the array into a left part with all elements less than v, followed by v, followed by a right part with all elements greater than v. Then, recursively sort the two parts. Extra credit: Modify your method (if necessary) to work properly when the values are not necessarily distinct.

4.2.33 Reverse domain. Compose a program to read in a list of domain names from standard input and write the reverse domain names in sorted order. For example, the reverse domain of cs.princeton.edu is edu.princeton.cs. This computation is useful for web log analysis. To do so, create a data type Domain that implements the special comparison methods, using reverse domain name order.

4.2.34 Local minimum in an array. Given an array of n floats, compose a function to find in logarithmic time a local minimum (an index i such that a[i] < a[i–1] and a[i] < a[i+1]).

4.2.35 Discrete distribution. Design a fast algorithm to repeatedly generate numbers from the discrete distribution. Given an array p[] of nonnegative floats that sum to 1, the goal is to return index i with probability p[i]. Form an array s[] of cumulated sums such that s[i] is the sum of the first i elements of p[]. Now, generate a random float s between 0 and 1, and use binary search to return the index i for which s[i] <= r < s[i+1].

4.2.36 Rhyming words. Tabulate a list that you can use to find words that rhyme. Use the following approach:

• Read in a dictionary of words into an array of strings.

• Reverse the letters in each word (confound becomes dnuofnoc, for example).

• Sort the resulting array.

• Reverse the letters in each word back to their original order.

For example, confound is adjacent to words such as astound and surround in the resulting list.

When we insert an item, our intent is clear. But when we remove an item, which one do we choose? You have encountered different ways to answer this question in various real-world situations, perhaps without thinking about it.

Each kind of collection is characterized by the rule used for remove. Moreover, depending on the removal rule each kind of collection is amenable to various implementations with differing performance characteristics. For example, the rule used for a queue is to always remove the item that has been in the collection the most amount of time. This policy is known as first-in first-out, or FIFO. People waiting in line to buy a ticket follow this discipline: the line is arranged in the order of arrival, so the person who leaves the line is the one who has been there longer than any other person in the line.

A policy with quite different behavior is the rule used for a stack: always remove the item that has been in the collection the least amount of time. This policy is known as last-in first-out, or LIFO. For example, you follow a policy closer to LIFO when you enter and leave the coach cabin in an airplane: people near the front of the cabin board last and exit before those who boarded earlier.

Stacks and queues are broadly useful, so it is important for you to be familiar with their basic properties and the kind of situation where each might be appropriate. They are excellent examples of fundamental data types that we can use to address higher-level programming tasks. They are widely used in systems and applications programming, as we will see in several examples in this section. The implementations and data structures that we consider also serve as models for other removal rules, some of which we examine in the exercises at the end of this section.

When you keep your mail in a pile on your desk, you are using a stack. You pile pieces of new mail on the top when they arrive and take each piece of mail from the top when you are ready to read it. People do not process as much paper mail as they did in the past, but the same organizing principle underlies several of the applications that you use regularly on your computer. For example, many people organize their email as a stack, where messages go on the top when they are received and are taken from the top, with most recently received first (last in, first out). The advantage of this strategy is that we see interesting email as soon as possible; the disadvantage is that some old email might never get read if we never empty the stack.

You have likely encountered another common example of a stack when surfing the web. When you click a link, your browser displays the new page (and inserts it onto a stack). You can keep clicking on links to visit new pages, but you can always revisit the previous page by clicking the back button (remove it from a stack). The last-in-first-out policy offered by a stack provides just the behavior that you expect.

Such uses of stacks are intuitive, but perhaps not persuasive. In fact, the importance of stacks in computing is fundamental and profound, but we defer further discussions of applications to later in this section. For the moment, our goal is to make sure that you understand how stacks work and how to implement them.

Programmers have been using stacks since the earliest days of computing. By tradition, we name the stack insert operation push and the stack remove operation pop, as indicated in the API at the top of the next page:

The API includes the core push() and pop() methods, along with a method isEmpty() to test whether the stack is empty and the built-in function len() to get the number of items on the stack. The pop() method raises a run-time error if it is called when the stack is empty. It is the client’s responsibility to call isEmpty() to avoid doing so. Next we consider two implementations of this API: arraystack.py and linkedstack.py.

Important note: When we include performance specifications in an API, as we have in Stack, we consider them to be requirements. An implementation that does not meet them might implement a SlowStack or a SpaceWastingStack, but not a Stack. We want clients to be able to depend on the performance guarantees.

Naturally, you need an instance variable a[] to hold the stack items in a Python list. Should you maintain the items in order of their insertion, with the least recently inserted item in a[0], the second in a[1], and so forth? Or should you maintain the items in reverse order of their insertion? For efficiency, we store the items in order of their insertion because inserting and deleting from the end of a Python list takes constant amortized time per operation (whereas inserting and deleting from the front takes linear time per operation).

We could hardly hope for a simpler implementation of the stack API than stack.py (PROGRAM 4.3.1)—all of the methods are one-liners! The instance variable is a Python list _a[] that holds the items in the stack in order of their insertion. To push an item, we append it to the end of the list using the += operator; to pop an item, we call the pop() method, which removes and returns the item from the end of the list; to determine the size of the stack, we call the built-in len() function. These operations preserve the following properties:

• That stack contains len(_a) items.

• The stack is empty when len(_a) is 0.

• The list _a[] contains the stack items, in order of their insertion.

• The item most recently inserted onto the stack (if nonempty) is _a[len(_a) - 1].

As usual, thinking in terms of invariants of this sort is the easiest way to verify that an implementation operates as intended.

Be sure that you fully understand this implementation. Perhaps the best way to do so is to carefully examine a trace of the list contents for a sequence of push() and pop() operations. The test client in stack.py allows for testing with an arbitrary sequence of operations: it does a push() for each string on standard input except the string consisting of a minus sign, for which it does a pop(). The diagram at right is a trace for the test input shown.

The primary characteristics of this implementation are that it uses space linear in the number of items in the stack and that the push and pop operations take constant amortized time. These properties follow immediately from the corresponding properties for Python lists that we discussed at the end of SECTION 3.1, which, in turn, depend on Python’s resizing array implementation of Python lists. If your programming language provides fixed-size arrays as a built-in data type (but not resizing arrays), you can implement a stack by implementing your own resizing array (see EXERCISE 4.3.45).

A linked list is a recursive data structure defined as follows: it is either empty (null) or a reference to a node having a reference to a linked list. The node in this definition is an abstract entity that might hold any kind of data, in addition to the node reference that characterizes its role in building linked lists. As with a recursive program, the concept of a recursive data structure can be a bit mind bending at first, but is of great value because of its simplicity.

With object-oriented programming, implementing linked lists is not difficult. We start with a class for the node abstraction:

Click here to view code image

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next

An object of type Node has two instance variables: item (a reference to an item) and next (a reference to another Node object). The next instance variable characterizes the linked nature of the data structure. To emphasize that we are just using the Node class to structure the data, we define no methods other than the constructor. We also omit leading underscores from the names of the instance variables, thus indicating that it is permissible for code external to the data type (but still within our Stack implementation) to access those instance variables.

Now, from the recursive definition, we can represent a linked list with a reference to a Node object, which contains a reference to an item and a reference to another Node object, which contains a reference to an item and a reference to another Node object, and so forth. The final Node object in the linked list must indicate that it is, indeed, the final Node object. In Python, we accomplish that by assigning None to the next instance variable of the final Node object. Recall that None is a Python keyword—a variable assigned the value None references no object.

Note that our definition of the Node class conforms to our recursive definition of a linked list. With our Node class we can represent a linked list as a variable whose value is either (1) None or (2) a reference to a Node object whose next field is a reference to a linked list. We create an object of type Node by calling the constructor with two arguments: a reference to an item and a reference to the next Node object in the linked list.

For example, to build a linked list that contains the items 'to', 'be', and 'or', we execute this code:

third  = Node('or', None)
second = Node('be', third)
first  = Node('to', second)

The end result of these operations is actually to create three linked lists:

• third is a linked list—it is a reference to a Node object that contains 'or' and None, which is the reference to an empty linked list.

• second is a linked list—it is a reference to a Node object that contains 'be' and a reference to third, which is a linked list.

• first is a linked list—it is a reference to a Node object that contains 'to' and a reference to second, which is a linked list.

A linked list represents a sequence of items. In this example, first represents the sequence 'to', 'be', 'or'.

We might also use an ordinary array (or Python list) to represent a sequence. For example, we could use the array ['to', 'be', 'or'] to represent the same sequence of strings. One key difference is that linked lists enable efficient insertion of items into (or deletion of items from) either the front or back of the sequence. Next, we consider code to accomplish these tasks.

When tracing code that uses linked lists and other linked structures, we use a visual representation where:

• We draw a rectangle to represent each object.

• We put the values of instance variables within the rectangle.

• We use arrows that point to the referenced objects to depict references.

This visual representation captures the essential characteristic of linked lists. For economy, we use the term link to refer to a Node reference. For simplicity, when the item is a string (as in our examples), we put it within the node rectangle (rather than using the more accurate rendition in which the node holds a reference to a string object, which is external to the node). This visual representation allows us to focus on the links.

Suppose that you want to remove the first node from a linked list. This operation is easy: simply assign to first the value first.next. Normally, you would retrieve the item (by assigning it to some variable) before doing this assignment, because once you change the variable first, you may lose any access to the node to which it was referring previously. Typically, the Node object becomes an orphan, and Python’s memory management system eventually reclaims it.

Now, suppose that you want to insert a new node into a linked list. The easiest place to do so is at the beginning of the linked list. For example, to insert the string 'not' at the beginning of a given linked list whose first node is first, we save first in a variable oldFirst; create a new Node whose item instance variable is 'not' and whose next instance variable is oldFirst; and assign first to refer to that new Node.

This code for inserting and removing a node from the beginning of a linked list involves just a few assignment statements and thus takes constant time (independent of the length of the list). If you hold a reference to a node at an arbitrary position in a list, you can use similar (but more complicated) code to remove the node after it or to insert a node after it, also in constant time, no matter how long the list. We leave those implementations as exercises (see EXERCISES 4.3.22 and 4.3.24) because inserting and removing at the beginning are the only linked-list operations that we need to implement stacks.

The Stack class defined in linkedstack.py itself has just one instance variable: a reference to the linked list that represents the stack, with the item most recently inserted in the first node. That single link suffices to directly access the item at the top of the stack and also provides access to the rest of the items in the stack for push() and pop().

Again, be sure that you understand this implementation—it is the prototype for several implementations using linked structures that we will examine later in this chapter.

With a linked-list implementation we can implement collections of all sorts without having to worry much about space usage, so linked lists are widely used in programming. Indeed, typical implementations of the Python memory management system are based on maintaining linked lists corresponding to blocks of memory of various sizes. Before the widespread use of high-level languages like Python, the details of memory management and programming with linked lists were critical parts of any programmer’s arsenal. In modern systems, most of these details are encapsulated in the implementations of a few data types like the pushdown stack, including the queue, the symbol table, and the set, which we will consider later in this chapter. If you take a course in algorithms and data structures, you will learn several others and gain expertise in creating and debugging programs that manipulate linked lists. Otherwise, you can focus your attention on understanding the role played by linked lists in implementing these fundamental data types.

For stacks, linked lists are significant because they allow us to implement the push() and pop() methods in constant time in the worst case, while using only a small constant factor of extra space (for the links). If you are uncertain about the value of linked structures, you might think about how you might achieve the same performance specifications for our stack API without using them.

Specifically, arraystack.py does not implement performance specifications in the API, because resizing arrays do not provide a constant-time guarantee for every operation. In many practical situations, the distinction between amortized and guaranteed worst-case performance is a minor one, but you might want to think about whether there might be some huge Python list being resized the next time your phone does not respond to a swipe, the next time your plane is readying for takeoff, or the next time you step on the brakes in your car.

Still, Python programmers usually prefer Python lists (resizing arrays), primarily because of the substantial Python overhead for user-defined types like our linked-list Node. The same principles apply to collections of any sort. For some data types that are more complicated than stacks, resizing arrays are also preferred over linked lists because the ability to access any item in the array in constant time (through indexing) is critical for implementing certain operations (see, for example, RandomQueue in EXERCISE 4.3.40). For some other data types, linked structures are easier to manipulate, as we will see in SECTION 4.4.

Click here to view code image

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

If you multiply 4 by 5, add 3 to 2, multiply the result, and then add 1, you get the value 101. But how does Python do this calculation? Without going into the details of how Python is built, we can address the essential ideas just by composing a Python program that can take a string as input (the expression) and produce the number represented by the expression as output. For simplicity, we begin with the following explicit recursive definition: an arithmetic expression is either a number or a left parenthesis followed by an arithmetic expression followed by an operator followed by another arithmetic expression followed by a right parenthesis. For simplicity, this definition applies to fully parenthesized arithmetic expressions, which specifies precisely which operators apply to which operands. With a bit more work, we could also handle expressions like 1 + 2 * 3, which use precedence rules instead of parentheses, but we avoid that complication here. For specificity, we support the familiar binary operators *, +, and -, as well as a square-root operator sqrt that takes only one argument. We could easily allow more operators and more kinds of operators to embrace a large class of familiar mathematical expressions, involving trigonometric, exponential, and logarithmic functions and whatever other operators we might wish to include. Our focus here, however, is on understanding how to interpret the string of parentheses, operators, and numbers to enable performing in the proper order the low-level arithmetic operations that are available on any computer.

• Push operands onto the operand stack.

• Push operators onto the operator stack.

• Ignore left parentheses.

• On encountering a right parenthesis, pop an operator, pop the requisite number of operands, and push onto the operand stack the result of applying that operator to those operands.

After the final right parenthesis has been processed, there is one value on the stack, which is the value of the expression. This method may seem mysterious at first, but it is easy to convince yourself that it computes the proper value: anytime the algorithm encounters a subexpression consisting of two operands separated by an operator, all surrounded by parentheses, it leaves the result of performing that operation on those operands on the operand stack. The result is the same as if that value had appeared in the input instead of the subexpression, so we can think of replacing the subexpression by the value to get an expression that would yield the same result. We can apply this argument again and again until we get a single value. For example, the algorithm computes the same value of all of these expressions:

Click here to view code image

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
( 1 + ( 5 * ( 4 * 5 ) ) )
( 1 + ( 5 * 20 ) )
( 1 + 100 )
101

PROGRAM 4.3.3 (evaluate.py) is an implementation of this algorithm. This code is a simple example of an interpreter: a program that interprets the computation specified by a given string and performs the computation to arrive at the result. A compiler is a program that converts the string into code on a lower-level machine that can do the job. This conversion is a more complicated process than the step-by-step conversion used by an interpreter, but it is based on the same underlying mechanism. Initially, Python was based on using an interpreter. Now, however, it includes a compiler that converts arithmetic expressions (and, more generally, Python programs) into code for the Python virtual machine, an imaginary machine that is easy to simulate on an actual computer.

Click here to view code image

( 1 ( ( 2 3 + ) ( 4 5 * ) * ) + )

In other words, we can put each operator after its two operands instead of between them. In such an expression, each right parenthesis immediately follows an operator so we can ignore both kinds of parentheses, writing the expressions as follows:

1 2 3 + 4 5 * * +

This notation is known as reverse Polish notation, or postfix. To evaluate a postfix expression, we use one stack (see EXERCISE 4.3.13). Proceeding from left to right, taking these entities one at a time, we manipulate the stacks according to just two possible cases:

• Push operands onto the operand stack.

• On encountering an operator, pop the requisite number of operands and push onto the operand stack the result of applying the operator to those operands.

Again, this process leaves one value on the stack, which is the value of the expression. This representation is so simple that some programming languages, such as Forth (a scientific programming language) and PostScript (a page description language that is used on most printers) use explicit stacks. For example, the string 1 2 3 + 4 5 * * + is a legal program in both Forth and PostScript that leaves the value 101 on the execution stack. Aficionados of these and similar stack-based programming languages prefer them because they are simpler for many types of computation. Indeed, the Python virtual machine itself is stack-based.

Indeed, most programs use stacks implicitly because they support a natural way to implement function calls, as follows: at any point during the execution of a function, define its state to be the values of all of its variables and a pointer to the next instruction to be executed. One of the fundamental characteristics of computing environments is that every computation is fully determined by its state (and the value of its inputs). In particular, the system can suspend a computation by saving away its state, then restart it by restoring the state. If you take a course about operating systems, you will learn the details of this process, because it is critical to much of the behavior of computers that we take for granted (for example, switching from one application to another is simply a matter of saving and restoring state). Now, the natural way to implement the function-call abstraction, which is used by almost all modern programming environments, is to use a stack. To call a function, push the state on a stack. To return from a function call, pop the state from the stack to restore all variables to their values before the function call, substitute the function return value (if there is one) in the expression containing the function call (if there is one), and resume execution at the next instruction to be executed (whose location was saved as part of the state of the computation). This mechanism works whenever functions call one another, even recursively. Indeed, if you think about the process carefully, you will see that it is essentially the same process that we just examined in detail for expression evaluation. A program is a sophisticated expression.

The pushdown stack is a fundamental computational abstraction. Stacks have been used for expression evaluation, implementing the function-call abstraction, and other basic tasks since the earliest days of computing. We will examine another (tree traversal) in SECTION 4.4. Stacks are used explicitly and extensively in many areas of computer science, including algorithm design, operating systems, compilers, and numerous other computational applications.

The policy of doing tasks in the same order that they arrive is one that we encounter frequently in everyday life, from people waiting in line at a theater, to cars waiting in line at a toll booth, to tasks waiting to be serviced by an application on your computer.

One bedrock principle of any service policy is the perception of fairness. The first idea that comes to mind when most people think about fairness is that whoever has been waiting the longest should be served first. That is precisely the FIFO discipline, so queues play a central role in numerous applications. Queues are a natural model for so many everyday phenomena—their properties were studied in detail even before the advent of computers.

As usual, we begin by articulating an API. Again by tradition, we name the queue insert operation enqueue and the remove operation dequeue, as indicated in the API below.

Applying our knowledge from stacks, we can use either Python lists (resizing arrays) or linked lists to develop implementations where the operations take constant time and the memory associated with the queue grows and shrinks with the number of elements in the queue. As with stacks, each of these implementations represents a classic programming exercise. You may wish to think about how you might achieve these goals in an implementation before reading further.

PROGRAM 4.3.4 (linkedqueue.py) is a linked-list implementation of Queue that has the same performance properties as Stack: all of the methods are constant-time operations, and space usage is linear in the number of items on the queue.

The stack, queue, and random queue APIs are essentially identical—they differ only in the choice of class and method names (which are chosen arbitrarily). Thinking about this situation is a good way to cement your understanding of the basic issues surrounding data types that we introduced in SECTION 3.3. The true differences among these data types are in the semantics of the remove operation—which item is to be removed? The differences between stacks and queues are embodied in the English-language descriptions of what they do. These differences are akin to the differences between math.sin(x) and math.log(x), but we might want to articulate them with a formal description of stacks and queues (in the same way as we have mathematical descriptions of the sine and logarithm functions). But precisely describing what we mean by first-in-first-out or last-in-first-out or random-out is not so simple. For starters, which language would you use for such a description? English? Python? Mathematical logic? The problem of describing how a program behaves is known as the specification problem, and it leads immediately to deep issues in computer science. One reason for our emphasis on clear and concise code is that the code itself can serve as the specification for simple data types such as stacks and queues.

Perhaps the ultimate queue application is the Internet itself, which is based on huge numbers of messages moving through huge numbers of queues that have all sorts of different properties and are interconnected in all sorts of complicated ways. Understanding and controlling such a complex system involves solid implementations of the queue abstraction, application of mathematical results of queueing theory, and simulation studies involving both. We consider next a classic example to give a flavor of this process.

• There is one server—a FIFO queue.

• Interarrival times to a queue obey an exponential distribution with rate λ per minute.

• Service times from a nonempty queue obey an exponential distribution with rate μ per minute.

The average time between arrivals is 1/λ minutes and the average time between services (when the queue is nonempty) is 1/μ minutes. So, the queue will grow without bound unless μ > λ; otherwise, customers enter and leave the queue in an interesting dynamic process.

• The average number of customers in the system L is λ / (μ – λ).

• The average time a customer spends in the system W is 1 / (μ – λ).

For example, if the cars arrive at a rate of λ = 10 per minute and the service rate is μ = 15 per minute, then the average number of cars in the system will be 2 and the average time that a customer spends in the system will be 1/5 minutes or 12 seconds. These formulas confirm that the wait time (and queue length) grows without bound as λ approaches μ. They also obey a general rule known as Little’s law: the average number of customers in the system is λ times the average time a customer spends in the system (L = λW) for many types of queues.

• nextService is the time of the next service.

• nextArrival is the time of the next arrival.

To simulate an arrival event, we enqueue a float nextArrival (the time of arrival); to simulate a service, we dequeue a float, compute the wait time wait (which is the time that the service is completed minus the time that the customer arrived and entered the queue), and add the wait time to a histogram (see PROGRAM 3.2.3). The shape that results after a large number of trials is characteristic of the M/M/1 queueing system. From a practical point of view, one of the most important characteristics of the process, which you can discover for yourself by running mm1queue.py for various values of the parameters λ and μ, is that the average time a customer spends in the system (and the average number of customers in the system) can increase dramatically when the service rate approaches the arrival rate. When the service rate is high, the histogram has a visible tail where the frequency of customers having a given wait time decreases to a negligible duration as the wait time increases. But when the service rate is close to the arrival rate, the tail of the histogram stretches to the point that most values are in the tail, so the frequency of customers having at least the highest wait time displayed dominates.

As in many other applications that we have studied, the use of simulation to validate a well-understood mathematical model is a starting point for studying more complex situations. In practical applications of queues, we may have multiple queues, multiple servers, multistage servers, limits on queue length, and many other restrictions. Moreover, the distributions of interarrival and service times may not be possible to characterize mathematically. In such situations, we may have no recourse but to use simulations. It is quite common for a system designer to build a computational model of a queuing system (such as mm1queue.py) and to use it to adjust design parameters (such as the service rate) to properly respond to the outside environment (such as the arrival rate).

We will consider the kind of program that the central authority might use to distribute the items, ignoring the dynamics of deleting items from the systems, adding and deleting servers, and so forth.

If we use a round-robin policy, cycling through the servers to make the assignments, we get a balanced allocation, but it is rarely possible for a distributor to have such complete control over the situation. For example, there might be a large number of independent distributors, so none of them could have up-to-date information about the servers. Accordingly, such systems often use a random policy, where the assignments are based on random choice. An even better policy is to choose a random sample of servers and assign a new item to the one that has smallest number of items. For small queues, differences among these policies is immaterial, but in a system with millions of items on thousands of servers, the differences can be quite significant, since each server has a fixed amount of resources to devote to this process. Indeed, similar systems are used in Internet hardware, where some queues might be implemented in special-purpose hardware, so queue length translates directly to extra equipment cost. But how big a sample should we take?

PROGRAM 4.3.6 (loadbalance.py) is a simulation of the sampling policy, which we can use to study this question. This program makes good use of the RandomQueue data type that we have been considering to provide an easily understood program that we can use for experimentation. The simulation maintains a random queue of queues and builds the computation around an inner loop where each new request for service goes on the smallest of a sample of queues, using the sample() method from RandomQueue to randomly sample queues. The surprising end result is that samples of size 2 lead to near-perfect balancing, so there is no point in taking larger samples.

We have considered in detail the issues surrounding the time and memory usage of basic implementations of the stack and queue APIs not just because these data types are important and useful, but also because you are likely to encounter the very same issues in the context of your own data-type implementations.

Should you use a pushdown stack, a FIFO queue, or a random queue when developing a client that maintains collections of data? The answer to this question depends on a high-level analysis of the client to determine which of the LIFO, FIFO, or random disciplines is appropriate.

Should you use a linked list or a resizing array to structure your data? The answer to this question depends on low-level analysis of performance characteristics. A linked list has the advantage that you can add items at either end but the disadvantage that you cannot access an arbitrary item in constant time. A resizing array has the advantage that you can access any item in constant time but the disadvantage that the constant running time is only for insertions and deletions at one end (and it is constant time only in the amortized sense). Each data structure is appropriate in various different situations; you are likely to encounter both in most programming environments.

The careful attention to performance guarantees that we have emphasized in our Stack and Queue APIs are not to be taken for granted. They are just the first in a progression of data types that provide the underpinnings of our computational infrastructure. The next section is devoted to an even more important one, the symbol table, and you will learn about others when you take a course on data structures and algorithms. By now, you know that learning to use a new data type is not so different from learning to ride a bicycle or implement helloworld.py: it seems completely mysterious until you have done it for the first time, but quickly becomes second nature. And learning to design and implement a new data type by developing a new data structure is a challenging, fruitful, and satisfying activity. As you will see in the exercises that follow, stacks, queues, linked lists, and resizing arrays raise a host of fascinating questions, but they are also just the beginning.