O'Reilly Media | Mastering Algorithms with C

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

When I was 12, my brother and I studied piano. Each week we would make a trip to our teacher's house; while one of us had our lesson, the other would wait in her parlor. Fortunately, she always had a few games arranged on a coffee table to help us pass the time while waiting. One game I remember consisted of a series of pegs on a small piece of wood. Little did I know it, but the game would prove to be an early introduction to data structures and algorithms.

The game was played as follows. All of the pegs were white, except for one, which was blue. To begin, one of the white pegs was removed to create an empty hole. Then, by jumping pegs and removing them much like in checkers, the game continued until a single peg was left, or the remaining pegs were scattered about the board in such a way that no more jumps could be made. The object of the game was to jump pegs so that the blue peg would end up as the last peg and in the center. According to the game's legend, this qualified the player as a "genius." Additional levels of intellect were prescribed for other outcomes. As for me, I felt satisfied just getting through a game without our teacher's kitten, Clara, pouncing unexpectedly from around the sofa to sink her claws into my right shoe. I suppose being satisfied with this outcome indicated that I simply possessed "common sense."

I remember playing the game thinking that certainly a deterministic approach could be found to get the blue peg to end up in the center every time. What I was looking for was an algorithm. Algorithms are well-defined procedures for solving problems. It was not until a number of years later that I actually implemented an algorithm for solving the peg problem. I decided to solve it in LISP during an artificial intelligence class in college. To solve the problem, I represented information about the game in various data structures. Data structures are conceptual organizations of information. They go hand in hand with algorithms because many algorithms rely on them for efficiency.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Data comes in all shapes and sizes, but often it can be organized in the same way. For example, consider a list of things to do, a list of ingredients in a recipe, or a reading list for a class. Although each contains a different type of data, they all contain data organized in a similar way: a list. A list is one simple example of a data structure. Of course, there are many other common ways to organize data as well. In computing, some of the most common organizations are linked lists, stacks, queues, sets, hash tables, trees, heaps, priority queues, and graphs, all of which are discussed in this book. Three reasons for using data structures are efficiency, abstraction, and reusability.

Efficiency: Data structures organize data in ways that make algorithms more efficient. For example, consider some of the ways we can organize data for searching it. One simplistic approach is to place the data in an array and search the data by traversing element by element until the desired element is found. However, this method is inefficient because in many cases we end up traversing every element. By using another type of data structure, such as a hash table (see Chapter 8) or a binary tree (see Chapter 9) we can search the data considerably faster.
Abstraction: Data structures provide a more understandable way to look at data; thus, they offer a level of abstraction in solving problems. For example, by storing data in a stack (see Chapter 6), we can focus on things that we do with stacks, such as pushing and popping elements, rather than the details of how to implement each operation. In other words, data structures let us talk about programs in a less programmatic way.
Reusability: Data structures are reusable because they tend to be modular and context-free. They are modular because each has a prescribed interface through which access to data stored in the data structure is restricted. That is, we access the data using only those operations the interface defines. Data structures are context-free because they can be used with any type of data and in a variety of situations or contexts. In C, we make a data structure store data of any type by using void pointers to the data rather than by maintaining private copies of the data in the data structure itself.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Algorithms are well-defined procedures for solving problems. In computing, algorithms are essential because they serve as the systematic procedures that computers require. A good algorithm is like using the right tool in a workshop. It does the job with the right amount of effort. Using the wrong algorithm or one that is not clearly defined is like cutting a piece of paper with a table saw, or trying to cut a piece of plywood with a pair of scissors: although the job may get done, you have to wonder how effective you were in completing it. As with data structures, three reasons for using formal algorithms are efficiency, abstraction, and reusability.

Efficiency: Because certain types of problems occur often in computing, researchers have found efficient ways of solving them over time. For example, imagine trying to sort a number of entries in an index for a book. Since sorting is a common task that is performed often, it is not surprising that there are many efficient algorithms for doing this. We explore some of these in Chapter 12.
Abstraction: Algorithms provide a level of abstraction in solving problems because many seemingly complicated problems can be distilled into simpler ones for which well-known algorithms exist. Once we see a more complicated problem in a simpler light, we can think of the simpler problem as just an abstraction of the more complicated one. For example, imagine trying to find the shortest way to route a packet between two gateways in an internet. Once we realize that this problem is just a variation of the more general single-pair shortest-paths problem (see Chapter 16), we can approach it in terms of this generalization.
Reusability: Algorithms are often reusable in many different situations. Since many well- known algorithms solve problems that are generalizations of more complicated ones, and since many complicated problems can be distilled into simpler ones, an efficient means of solving certain simpler problems potentially lets us solve many others.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

As mentioned at the start of this chapter, a good understanding of data structures and algorithms is an important part of developing well-crafted software. Equally important is a dedication to applying sound practices in software engineering in our implementations. Software engineering is a broad subject, but a great deal can be gleaned from a few concepts, which are presented here and applied throughout the examples in this book.

Modularity: One way to achieve modularity in software design is to focus on the development of black boxes. In software, a black box is a module whose internals are not intended to be seen by users of the module. Users interact with the module only through a prescribed interface made public by its creator. That is, the creator publicizes only what users need to know to use the module and hides the details about everything else. Consequently, users are not concerned with the details of how the module is implemented and are prevented (at least in policy, depending on the language) from working with the module's internals. These ideas are fundamental to data hiding and encapsulation, principles of good software engineering enforced particularly well by object-oriented languages. Although languages that are not object-oriented do not enforce these ideas to the same degree, we can still apply them. One example in this book is the design of abstract datatypes. Fundamentally, each datatype is a structure. Exactly what one can do with the structure is dictated by the operations defined for the datatype and publicized in its header.
Readability: We can make programs more readable in a number of ways. Writing meaningful comments, using aptly named identifiers, and creating code that is self-documenting are a few examples. Opinions on how to write good comments vary considerably, but a good fundamental philosophy is to document a program so that other developers can follow its logic simply by reading its comments. On the other hand, sections of self-documenting code require few, if any, comments because the code reads nearly the same as what might be stated in the comments themselves. One example of self-documenting code in this book is the use of header files as a means of defining and documenting public interfaces to the data structures and algorithms presented.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

This book was designed to be read either as a textbook or a reference, whichever is needed at the moment. It is organized into three parts. The first part consists of introductory material and includes chapters on pointer manipulation, recursion, and the analysis of algorithms. These subjects are useful when working in the rest of the book. The second part presents fundamental data structures, including linked lists, stacks, queues, sets, hash tables, trees, heaps, priority queues, and graphs. The third part presents common algorithms for solving problems in sorting, searching, numerical analysis, data compression, data encryption, graph theory, and computational geometry.

Each of the chapters in the second and third parts of the book has a consistent format to foster the book's ease of use as a reference and its readability in general. Each chapter begins with a brief introduction followed by a list of specific topics and a list of real applications. The presentation of each data structure or algorithm begins with a description, followed by an interface, followed by an implementation and analysis. For many data structures and algorithms, examples are presented as well. Each chapter ends with a series of questions and answers, and a list of related topics for further exploration.

The presentation of each data structure or algorithm starts broadly and works toward an implementation in real code. Thus, readers can easily work up to the level of detail desired. The descriptions cover how the data structures or algorithms work in general. The interfaces serve as quick references for how to use the data structures or algorithms in a program. The implementations and analyses provide more detail about exactly how the interfaces are implemented and how each implementation performs. The questions and answers, as well as the related topics, help those reading the book as a textbook gain more insight about each chapter. The material at the start of each chapter helps clearly identify topics within the chapters and their use in real applications.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

In C, for any type T, we can form a corresponding type for variables that contain addresses in memory where objects of type T reside. One way to look at variables like this is that they actually "point to" the objects. Thus, these variables are called pointers. Pointers are very important in C, but in many ways, they are a blessing and a curse. On the one hand, they are a powerful means of building data structures and precisely manipulating memory. On the other hand, they are easy to misuse, and their misuse often leads to unpredictably buggy software; thus, they come with a great deal of responsibility. Considering this, it is no surprise that pointers embody what some people love about C and what other people hate. Whatever the case, to use C effectively, we must have a thorough understanding of them. This chapter presents several topics on pointers and introduces several of the techniques using pointers that are employed throughout this book.

This chapter covers:

Pointer fundamentals: Including one of the best techniques for understanding pointers: drawing diagrams. Another fundamental aspect of pointer usage is learning how to avoid dangling pointers.
Storage allocation: The process of reserving space in memory. Understanding pointers as they relate to storage allocation is especially important because pointers are a virtual carte blanche when it comes to accessing memory.
Aggregates and pointer arithmetic: In C, aggregates are structures and arrays. Pointer arithmetic defines the rules by which calculations with pointers are performed. Pointers to structures are important in building data structures. Arrays and pointers in C use pointer arithmetic in the same way.
Pointers as parameters to functions: The means by which C simulates call-by-reference parameter passing. In C, it is also common to use pointers as an efficient means of passing arrays and large structures.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Recall that a pointer is simply a variable that stores the address where a piece of data resides in memory rather than storing the data itself. That is, pointers contain memory addresses. Even for experienced developers, at times this level of indirection can be a bit difficult to visualize, particularly when dealing with more complicated pointer constructs, such as pointers to other pointers. Thus, one of the best things we can do to understand and communicate information about pointers is to draw diagrams (see Figure 2.1). Rather than listing actual addresses in diagrams, pointers are usually drawn as arrows linking one location to another. When a pointer points to nothing at all—that is, when it is set to NULL—it is illustrated as a line terminated with a double bar (see Figure 2.1, step 4).

As with other types of variables, we should not assume that a pointer points anywhere useful until we explicitly set it. It is also important to remember that nothing prevents a pointer in C from pointing to an invalid address. Pointers that point to invalid addresses are sometimes called dangling pointers. Some examples of programming errors that can lead to dangling pointers include casting arbitrary integers to pointers, adjusting pointers beyond the bounds of arrays, and deallocating storage that one or more pointers still reference.

Figure 2.1: An illustration of some operations with pointers

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

When we declare a pointer in C, a certain amount of space is allocated for it, just as for other types of variables. Pointers generally occupy one machine word, but their size can vary. Therefore, for portability, we should never assume that a pointer has a specific size. Pointers often vary in size as a result of compiler settings and type specifiers allowed by certain C implementations. It is also important to remember that when we declare a pointer, space is allocated only for the pointer itself; no space is allocated for the data the pointer references. Storage for the data is allocated in one of two ways: by declaring a variable for it or by allocating storage dynamically at runtime (using malloc or realloc, for example).

When we declare a variable, its type tells the compiler how much storage to set aside for it as the program runs. Storage for the variable is allocated automatically, but it may not be persistent throughout the life of the program. This is especially important to remember when dealing with pointers to automatic variables. Automatic variables are those for which storage is allocated and deallocated automatically when entering and leaving a block or function. For example, since iptr is set to the address of the automatic variable a in the following function f, iptr becomes a dangling pointer when f returns. This situation occurs because once f returns, a is no longer valid on the program stack (see Chapter 3).

int f(int **iptr) {

int a = 10;
*iptr = &a;

return 0;

}

In C, when we dynamically allocate storage, we get a pointer to some storage on the heap (see Chapter 3). Since it is then our responsibility to manage this storage ourselves, the storage remains valid until we explicitly deallocate it. For example, the storage allocated by malloc in the following code remains valid until we call free at some later time. Thus, it remains valid even after

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

One of the most common uses of pointers in C is referencing aggregate data. Aggregate data is data composed of multiple elements grouped together because they are somehow related. C supports two classes of aggregate data: structures and arrays. (Unions, although similar to structures, are considered formally to be in a class by themselves.)

Structures are sequences of usually heterogeneous elements grouped so that they can be treated together as a single coherent datatype. Pointers to structures are an important part of building data structures. Whereas structures allow us to group data into convenient bundles, pointers let us link these bundles to one another in memory. By linking structures together, we can organize them in meaningful ways to help solve real problems.

As an example, consider chaining a number of elements together in memory to form a linked list (see Chapter 5). To do this, we might use a structure like ListElmt in the following code. Using a ListElmt structure for each element in the list, to link a sequence of list elements together, we set the next member of each element to point to the element that comes after it. We set the next member of the last element to NULL to mark the end of the list. We set the data member of each element to point to the data the element contains. Once we have a list containing elements linked in this way, we can traverse the list by following one next pointer after another.

typedef struct ListElmt_ {

void               *data;
struct ListElmt_   *next;

} ListElmt;

The ListElmt structure illustrates another important aspect about pointers with structures: structures are not permitted to contain instances of themselves, but they may contain pointers to instances of themselves. This is an important idea in building data structures because many data structures are built from components that are self-referential. In a linked list, for example, each

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Pointers are an essential part of calling functions in C. Most importantly, they are used to support a type of parameter passing called call-by-reference. In call-by-reference parameter passing , when a function changes a parameter passed to it, the change persists after the function returns. Contrast this with call-by-value parameter passing, in which changes to parameters persist only within the function itself. Pointers are also an efficient means of passing large amounts of data in and out of functions, whether we plan to modify the data or not. This method is efficient because only a pointer is passed instead of a complete copy of the data. This technique is used in many of the examples in this book.

Formally, C supports only call-by-value parameter passing. In call-by-value parameter passing , private copies of a function's calling parameters are made for the function to use as it executes. However, we can simulate call-by-reference parameter passing by passing pointers to parameters instead of passing the parameters themselves. Using this approach, a function gets a private copy of a pointer to each parameter in the caller's environment.

To understand how this works, first consider swap1, which illustrates an incorrect implementation of a function to swap two integers using call-by-value parameter passing without pointers. Figure 2.4 illustrates why this does not work. The function swap2 corrects the problem by using pointers to simulate call-by-reference parameter passing. Figure 2.5 illustrates how using pointers makes swapping proceed correctly.

Incorrect Swap	Correct Swap
void swap1(int x, int y) { int tmp; tmp = x; x = y; y = tmp; return; }	void swap2(int x, int y) { int tmp; tmp = x; x = y; y = tmp; return; }

Figure 2.4: An illustration of swap1, which uses call-by-value parameter passing and fails to swap two integers in the caller's environment

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Recall that pointer variables in C have types just like other variables. The main reason for this is so that when we dereference a pointer, the compiler knows the type of data being pointed to and can access the data accordingly. However, sometimes we are not concerned about the type of data a pointer references. In these cases we use generic pointers, which bypass C's type system.

Normally C allows assignments only between pointers of the same type. For example, given a character pointer sptr (a string) and an integer pointer iptr, we are not permitted to assign sptr to iptr or iptr to sptr. However, generic pointers can be set to pointers of any type, and vice versa. Thus, given a generic pointer gptr, we are permitted to assign sptr to gptr or gptr to sptr. To make a pointer generic in C, we declare it as a void pointer .

There are many situations in which void pointers are useful. For example, consider the standard C library function memcpy, which copies a block of data from one location in memory to another. Because memcpy may be used to copy data of any type, it makes sense that its pointer parameters are void pointers. Void pointers can be used to make other types of functions more generic as well. For example, we might have implemented the swap2 function presented earlier so that it swapped data of any type, as shown in the following code:

#include <stdlib.h>
#include <string.h>

int swap2(void *x, void *y, int size) {

void *tmp;

if ((tmp = malloc(size)) == NULL)
   return -1;

memcpy(tmp, x, size); memcpy(x, y, size); memcpy(y, tmp, size);
free(tmp);

return 0;

}

Void pointers are particularly useful when implementing data structures because they allow us to store and retrieve data of any type. Consider again the ListElmt structure presented earlier for linked lists. Recall that this structure contains two members,

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Function pointers are pointers that, instead of pointing to data, point to executable code or to blocks of information needed to invoke executable code. They are used to store and manage functions as if they were pieces of data. Function pointers have a type that is described in terms of a return value and parameters that the function accepts. Declarations for function pointers look much like declarations for functions, except that an asterisk ( * ) appears before the function name, and the asterisk and name are surrounded by parentheses for reasons of associativity. For example, in the following code, match is declared as a pointer to a function that accepts two void pointers and returns an integer:

int (*match)(void *key1, void *key2);

This declaration means that we can set match to point to any function that accepts two void pointers and returns an integer. For example, suppose match_int is a function that accepts two void pointers to integers and returns 1 if the integers match, or otherwise. Assuming the previous declaration, we could set match to point to this function by executing the following statement:

match = match_int;

To execute a function referenced by a function pointer, we simply use the function pointer wherever we would normally use the function itself. For example, to invoke the function referenced by match earlier, we execute the following statement, assuming x, y, and retval have been declared as integers:

retval = match(&x, &y);

One important use of function pointers in this book is to encapsulate functions into data structures. For example, in the implementation of chained hash tables (see Chapter 8), the data structure has a match member similar to the function pointer just described. This pointer is used to invoke a function whenever we need to determine whether an element we are searching for matches an element in the table. We assign a function to this pointer when the table is initialized. The function we assign has the same prototype as

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Q: One of the difficulties with pointers is that often when we misuse them, our errors are not caught by the compiler at compile time; they occur at runtime. Which of the following result in compile-time errors? Which of the following result in runtime errors? Why?

a)

char *sptr = "abc",*tptr;
*tptr = sptr;

b)

char *sptr = "abc",*tptr;
tptr = sptr;

c)

char *sptr = "abc",*tptr;
*tptr = *sptr;

d)

int *iptr = (int *)10;
*iptr = 11;

e)

int *iptr = 10;
*iptr = 11;

f )

int *iptr = (int *)10;
iptr = NULL;

A: a) A compile-time error occurs because when we dereference tptr, we get a character, whereas sptr is a pointer to a character. Thus, the code is trying to assign a character pointer to a character, which is a type conflict. b) No error occurs because both tptr and sptr are character pointers. c) A runtime error is likely to occur because no storage has been allocated for tptr. When we dereference tptr, we cannot be sure where it points. d) A runtime error is likely to occur because assigning an integer pointer a fixed address is dangerous. When dereferencing iptr, we try to write 11 at address 10, which is probably invalid. e) A compile-time error or warning occurs because the code is trying to initialize an integer pointer to an integer, which is a type conflict. f ) No error occurs because although the code first performs the dangerous step of initializing iptr to a fixed address, it is then immediately reset to NULL, which is valid.

Q: Recall that calculations with pointers are performed using pointer arithmetic. If p contains the address 0x10000000, what address does the following expression access? How many bytes are accessed at this address?

*(p + 5)

A: The answer to this question depends on the type of p. Recall that when we add an integer i to a pointer p, the result is not the address stored in p plus i bytes, but the address in

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

C++: An object-oriented language that enforces many practices of good software engineering. As one example, it supports constructors and destructors for datatypes. These mechanisms provide a compact way of managing memory within instances of the type, thus avoiding many of the problems associated with memory leaks and pointers in C.
Heap-based allocation: The type of memory allocation provided by the C functions malloc and realloc. Heap-based allocation is often called dynamic storage allocation. This allows a program to request more memory as it needs it rather than allocating a fixed amount at compile time.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Recursion is a powerful principle that allows something to be defined in terms of smaller instances of itself. Perhaps there is no better way to appreciate the significance of recursion than to look at the mysterious ways nature uses it. Think of the fragile leaf of a fern, in which each individual sprig from the leaf's stem is just a smaller copy of the overall leaf. Think of the repeating patterns in a reflection, in which two shiny objects reflect each other. Examples like these convince us that even though nature is a great force, in many ways it has a paradoxical simplicity that is truly elegant. The same can be said for recursive algorithms; in many ways, recursive algorithms are simple and elegant, yet they can be extremely powerful.

In computing, recursion is supported via recursive functions. A recursive function is a function that calls itself. Each successive call works on a more refined set of inputs, bringing us closer and closer to the solution of a problem. Most developers are comfortable with the idea of dividing a larger problem into several smaller ones and writing separate functions to solve them. However, many developers are less comfortable with the idea of solving a larger problem with a single function that calls itself. Admittedly, looking at a problem in this way can take some getting used to. This chapter explores how recursion works and shows how to define some problems in a recursive manner. Some examples of recursive approaches in this book are found in tree traversals (see Chapter 9), breadth-first and depth-first searches with graphs (see Chapter 11), and sorting (see Chapter 12 ).

This chapter covers:

Basic recursion: A powerful principle that allows a problem to be defined in terms of smaller and smaller instances of itself. In computing, we solve problems defined recursively by using recursive functions, which are functions that call themselves.
Tail recursion: A form of recursion for which compilers are able to generate optimized code. Most modern compilers recognize tail recursion. Therefore, we should make use of it whenever we can.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

To begin, let's consider a simple problem that normally we might not think of in a recursive way. Suppose we would like to compute the factorial of a number n. The factorial of n, written n!, is the product of all numbers from n down to 1. For example, 4! = (4)(3)(2)(1). One way to calculate this is to loop through each number and multiply it with the product of all preceding numbers. This is an iterative approach, which can be defined more formally as:

n! = (n)(n - 1)(n - 2) . . . (1)

Another way to look at this problem is to define n! as the product of smaller factorials. To do this, we define n! as n times the factorial of n - 1. Of course, solving (n - 1)! is the same problem as n!, only a little smaller. If we then think of (n - 1)! as n - 1 times (n - 2)!, (n - 2)! as n - 2 times (n - 3)!, and so forth until n = 1, we end up computing n!. This is a recursive approach, which can be defined more formally as:

Figure 3.1 illustrates computing 4! using the recursive approach just described. It also delineates the two basic phases of a recursive process: winding and unwinding . In the winding phase, each recursive call perpetuates the recursion by making an additional recursive call itself. The winding phase terminates when one of the calls reaches a terminating condition. A terminating condition defines the state at which a recursive function should return instead of making another recursive call. For example, in computing the factorial of n, the terminating conditions are n = 1 and n = 0, for which the function simply returns 1. Every recursive function must have at least one terminating condition; otherwise, the winding phase never terminates. Once the winding phase is complete, the process enters the unwinding phase, in which previous instances of the function are revisited in reverse order. This phase continues until the original call returns, at which point the recursive process is complete.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

A recursive function is said to be tail recursive if all recursive calls within it are tail recursive. A recursive call is tail recursive when it is the last statement that will be executed within the body of a function and its return value is not a part of an expression. Tail-recursive functions are characterized as having nothing to do during the unwinding phase. This characteristic is important because most modern compilers automatically generate code to take advantage of it.

When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack. The compiler can do this because the recursive call is the last statement to be executed in the current activation; thus, there is nothing left to do in the activation when the call returns. Consequently, there is no reason to keep the current activation around. By replacing the current activation record instead of stacking another one on top of it, stack usage is greatly reduced, which leads to better performance in practice. Thus, we should make recursive functions tail recursive whenever we can.

To understand how tail recursion works, let's revisit computing a factorial recursively. First, it is helpful to understand the reason the previous definition was not tail recursive. Recall that the original definition computed n! by multiplying n times (n - 1)! in each activation, repeating this for n = n - 1 until n = 1. This definition was not tail recursive because the return value of each activation depended on multiplying n times the return value of subsequent activations. Therefore, the activation record for each call had to remain on the stack until the return values of subsequent calls were determined. Now consider a tail-recursive definition for computing n!, which can be defined formally as:

This definition is similar to the one presented earlier, except that it uses a second parameter,

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Q: The following recursive definition has an error. What is it, and how can we fix it? For a positive integer n, the definition, in its proper form, is common in formally computing the running time of divide-and-conquer algorithms, such as merge sort (see Chapter 12). Merge sort divides a set of data in half, then divides the halves in half, and continues this way until each division contains a single element. Then, during the unwinding phase, the divisions are merged to produce a final sorted set.

A: The problem with this definition is that it never reaches the terminating condition, n = 0, for any initial value of n greater than 0. To fix the problem, it needs an obtainable terminating condition. The condition n = 1 works well, which means we should also change the second condition in the function. A recursive definition with an acceptable terminating condition is presented here:

This happens to be the correct definition for the running time of merge sort. Such a function is called a recurrence. In more formal analysis, recurrences are used frequently to describe the running times of recursive algorithms.

Q: Describe a recursive approach for computing the prime factors of a number. Determine whether the approach is tail recursive, and describe why or why not.

A: Recursion is a natural way to find the prime factors of a number because factoring is really just the same problem over and over again, only a little smaller, as we determine each factor. A recursive approach to this problem can be defined as shown:

This definition says that to determine the prime factors of a number n recursively, determine its smallest prime factor i, record this in a set of factors P, and repeat the process for n = n /i. Continue this way until n is found to be prime itself, which is the terminating condition. This definition is tail recursive because there is nothing that needs to be done during the unwinding phase, as Figure 3.6 confirms.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Compiler design: The basics behind the code translators that ultimately dictate how efficiently programs will run, at least at the instruction level. Whereas generally in algorithm design we focus on complexity as a measure of performance (see Chapter 4), understanding the issues compilers deal with in translating code can help us tune performance in practice. Understanding tail recursion is a good example.
Tail recursion elimination: A process in which the final tail-recursive call in a function is replaced with an iterative control structure. This does not change the outcome of the function, but helps avoid the overhead of an extra function call. Tail recursion elimination is a fundamental principle studied in compiler design.
Recursion trees: Illustrations that help us visualize calling sequences with recursive functions. Recursion trees vary in their formality. Figures Figure 3.1 and Figure 3.4 for recursively computing a factorial and Figure 3.6 for determining the prime factors of a number are recursion trees. Recursion trees are most often used with functions containing two or more recursive calls within each activation.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Whether we are designing an algorithm or applying one that is widely accepted, it is important to understand how the algorithm will perform. There are a number of ways we can look at an algorithm's performance, but usually the aspect of most interest is how fast the algorithm will run. In some cases, if an algorithm uses significant storage, we may be interested in its space requirement as well. Whatever the case, determining how an algorithm performs requires a formal and deterministic method.

There are many reasons to understand the performance of an algorithm. For example, we often have a choice of several algorithms when solving problems. Understanding how each performs helps us differentiate between them. Understanding the burden an algorithm places on an application also helps us plan how to use the algorithm more effectively. For instance, garbage collection algorithms, algorithms that collect dynamically allocated storage to return to the heap (see Chapter 3), require considerable time to run. Knowing this, we can be careful to run them only at opportune moments, just as LISP and Java do, for example.

This chapter covers:

Worst-case analysis: The metric by which most algorithms are compared. Other cases we might consider are the average case and best case. However, worst-case analysis usually offers several advantages.
O-notation: The most common notation used to formally express an algorithm's performance. O -notation is used to express the upper bound of a function within a constant factor.
Computational complexity: The growth rate of the resources (usually time) an algorithm requires with respect to the size of the data it processes. O -notation is a formal expression of an algorithm's complexity.

Most algorithms do not perform the same in all cases; normally an algorithm's performance varies with the data passed to it. Typically, three cases are recognized: the

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Most algorithms do not perform the same in all cases; normally an algorithm's performance varies with the data passed to it. Typically, three cases are recognized: the best case, worst case, and average case. For any algorithm, understanding what constitutes each of these cases is an important part of analysis because performance can vary significantly between them. Consider even a simple algorithm such as linear search. Linear search is a natural but inefficient search technique in which we look for an element simply by traversing a set from one end to the other. In the best case, the element we are looking for is the first element we inspect, so we end up traversing only a single element. In the worst case, however, the desired element is the last one we inspect, in which case we end up traversing all of the elements. On average, we can expect to find the element somewhere in the middle.

A basic understanding of how an algorithm performs in all cases is important, but usually we are most interested in how an algorithm performs in the worst case. There are four reasons why algorithms are generally analyzed by their worst case:

Many algorithms perform to their worst case a large part of the time. For example, the worst case in searching occurs when we do not find what we are looking for at all. Imagine how frequently this takes place in some database applications.
The best case is not very informative because many algorithms perform exactly the same in the best case. For example, nearly all searching algorithms can locate an element in one inspection at best, so analyzing this case does not tell us much.
Determining average-case performance is not always easy. Often it is difficult to determine exactly what the "average case" even is. Since we can seldom guarantee precisely how an algorithm will be exercised, usually we cannot obtain an average-case measurement that is likely to be accurate.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

O -notation is the most common notation used to express an algorithm's performance in a formal manner. Formally, O -notation expresses the upper bound of a function within a constant factor. Specifically, if g (n) is an upper bound of f (n), then for some constant c it is possible to find a value of n, call it n ₀, for which any value of n ≥ n ₀ will result in f (n) ≤ cg (n).

Normally we express an algorithm's performance as a function of the size of the data it processes. That is, for some data of size n, we describe its performance with some function f (n). However, while in many cases we can determine f exactly, usually it is not necessary to be this precise. Primarily we are interested only in the growth rate of f, which describes how quickly the algorithm's performance will degrade as the size of the data it processes becomes arbitrarily large. An algorithm's growth rate, or order of growth, is significant because ultimately it describes how efficient the algorithm is for arbitrary inputs. O -notation reflects an algorithm's order of growth.

When we look at some function f (n) in terms of its growth rate, a few things become apparent. First, we can ignore constant terms because as the value of n becomes larger and larger, eventually constant terms will become insignificant. For example, if T (n) = n + 50 describes the running time of an algorithm, and n, the size of the data it processes, is only 1024, the constant term in this expression already constitutes less than 5% of the running time. Second, we can ignore constant multipliers of terms because they too will become insignificant as the value of n increases. For example, if T ₁(n) = n ² and T ₂(n) = 10n describe the running times of two algorithms for solving the same problem,

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

When speaking of the performance of an algorithm, usually the aspect of interest is its complexity, which is the growth rate of the resources (usually time) it requires with respect to the size of the data it processes. O -notation describes an algorithm's complexity. Using O -notation, we can frequently describe the worst-case complexity of an algorithm simply by inspecting its overall structure. Other times, it is helpful to employ techniques involving recurrences and summation formulas (see the related topics at the end of the chapter), and statistics.

To understand complexity, let's look at one way to surmise the resources an algorithm will require. It should seem reasonable that if we look at an algorithm as a series of k statements, each with some cost (usually time) to execute, c_i , we can determine the algorithm's total cost by summing the costs of all statements from c ₁ to c_k in whatever order each is executed. Normally statements are executed in a more complicated manner than simply in sequence, so this has to be taken into account when totaling the costs. For example, if some subset of the statements is executed in a loop, the costs of the subset must be multiplied by the number of iterations. Consider an algorithm consisting of k = 6 statements. If statements 3, 4, and 5 are executed in a loop from 1 to n and the other statements are executed sequentially, the overall cost of the algorithm is:

T(n) = c ₁ + c ₂ + n(c ₃ + c ₄ + c ₅) + c ₆

Using the rules of O -notation, this algorithm's complexity is O (n) because the constants are not significant. Analyzing an algorithm in terms of these constant costs is very thorough. However, recalling what we have seen about growth rates, remember that we do not need to be so precise. When inspecting the overall structure of an algorithm, only two steps need to be performed: we must determine which parts of the algorithm depend on data whose size is not constant, and then derive functions that describe the performance of each part. All other parts of the algorithm execute with a constant cost and can be ignored in figuring its overall complexity.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

This section presents an analysis of the worst-case running time of insertion sort , a simple sorting algorithm that works by inserting elements into a sorted set by scanning the set to determine where each new element belongs. A complete description of insertion sort appears in Chapter 12. The code for the sort is shown in Example 4.1.

We begin by identifying which lines of code are affected by the size of the data to be sorted. These are the statements that constitute the nested loop, whose outer part iterates from 1 to size - 1 and whose inner part iterates from j - 1 to wherever the correct position for the element being inserted is found. All other lines run in a constant amount of time, independent of the number of elements to be sorted. Typically, the generic variable n is used to refer to the parameter on which an algorithm's performance depends. With this in mind, the outer loop has a running time of T (n) = n - 1, times some constant amount of time. Examining the inner loop and considering the worst case, we assume that we will have to go all the way to the other end of the array before inserting each element into the sorted set. Therefore, the inner loop iterates once for the first element, twice for the second, and so forth until the outer loop terminates. Effectively, this becomes a summation from 1 to n - 1, which results in a running time of T (n) = (n (n + 1)/2) - n, times some constant amount of time. (This equation is from the well-known formula for summing a series from 1 to n.) Consequently:

Example 4.1. Implementation of Insertion Sort from Chapter 12

/*****************************************************************************
*                                                                            *
*  ------------------------------- issort.c -------------------------------  *
*                                                                            *
*****************************************************************************/

#include <stdlib.h>
#include <string.h>

#include "sort.h"

/*****************************************************************************
*                                                                            *
*  -------------------------------- issort --------------------------------  *
*                                                                            *
*****************************************************************************/

int issort(void *data, int size, int esize, int (*compare)(const void *key1, 
   const void *key2)) {

char               *a = data;

void               *key;

int                i,
                   j;

/*****************************************************************************
*                                                                            *
*  Allocate storage for the key element.                                     *
*                                                                            *
*****************************************************************************/

if ((key = (char *)malloc(esize)) == NULL)
   return -1;

/*****************************************************************************
*                                                                            *
*  Repeatedly insert a key element among the sorted elements.                *
*                                                                            *
*****************************************************************************/

for (j = 1; j < size; j++) {

   memcpy(key, &a[j * esize], esize);
   i = j - 1;

   /**************************************************************************
   *                                                                         *
   *  Determine the position at which to insert the key element.             *
   *                                                                         *
   **************************************************************************/

   while (i >= 0 && compare(&a[i * esize], key) > 0) {

      memcpy(&a[(i + 1) * esize], &a[i * esize], esize);
      i--;

   }

   memcpy(&a[(i + 1) * esize], key, esize);

}

/*****************************************************************************
*                                                                            *
*  Free the storage allocated for sorting.                                   *
*                                                                            *
*****************************************************************************/

free(key);

return 0;

}

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content pr

Table of Contents