2.1 Insertion sort 21 counter in each iteration,and we use the keyword downto when a for loop decrements its loop counter.When the loop counter changes by an amount greater than 1,the amount of change follows the optional keyword by. ·The symbol“∥"indicates that the remainder of the line is a comment. A multiple assignment of the form i =j=e assigns to both variables i and j the value of expression e;it should be treated as equivalent to the assignment j=e followed by the assignment i j. Variables (such as i,j,and key)are local to the given procedure.We shall not use global variables without explicit indication. We access array elements by specifying the array name followed by the in- dex in square brackets.For example,A[i]indicates the ith element of the array A.The notation".."is used to indicate a range of values within an ar- ray.Thus,A[1..j]indicates the subarray of A consisting of the j elements A[1,A2],.,AUj] We typically organize compound data into objects,which are composed of attributes.We access a particular attribute using the syntax found in many object-oriented programming languages:the object name,followed by a dot, followed by the attribute name.For example,we treat an array as an object with the attribute length indicating how many elements it contains.To specify the number of elements in an array A,we write A.length. We treat a variable representing an array or object as a pointer to the data rep- resenting the array or object.For all attributes f of an object x,setting y =x causes y.f to equal x.f.Moreover,if we now set x.f 3,then afterward not only does x.f equal 3,but y.f equals 3 as well.In other words,x and y point to the same object after the assignment y =x. Our attribute notation can"cascade."For example,suppose that the attribute f is itself a pointer to some type of object that has an attribute g.Then the notation x.f.g is implicitly parenthesized as (x.f).g.In other words,if we had assigned y =x.f,then x.f.g is the same as y.g. Sometimes,a pointer will refer to no object at all.In this case,we give it the special value NIL. We pass parameters to a procedure by value:the called procedure receives its own copy of the parameters,and if it assigns a value to a parameter,the change is not seen by the calling procedure.When objects are passed,the pointer to the data representing the object is copied,but the object's attributes are not.For example,ifx is a parameter of a called procedure,the assignment x =y within the called procedure is not visible to the calling procedure.The assignment x.f =3,however,is visible.Similarly,arrays are passed by pointer,so that
2.1 Insertion sort 21 counter in each iteration, and we use the keyword downto when a for loop decrements its loop counter. When the loop counter changes by an amount greater than 1, the amount of change follows the optional keyword by. The symbol “//” indicates that the remainder of the line is a comment. A multiple assignment of the form i D j D e assigns to both variables i and j the value of expression e; it should be treated as equivalent to the assignment j D e followed by the assignment i D j . Variables (such as i, j , and key) are local to the given procedure. We shall not use global variables without explicit indication. We access array elements by specifying the array name followed by the index in square brackets. For example, AŒi indicates the ith element of the array A. The notation “: :” is used to indicate a range of values within an array. Thus, AŒ1 : : j indicates the subarray of A consisting of the j elements AŒ1; AŒ2; : : : ; AŒj . We typically organize compound data into objects, which are composed of attributes. We access a particular attribute using the syntax found in many object-oriented programming languages: the object name, followed by a dot, followed by the attribute name. For example, we treat an array as an object with the attribute length indicating how many elements it contains. To specify the number of elements in an array A, we write A:length. We treat a variable representing an array or object as a pointer to the data representing the array or object. For all attributes f of an object x, setting y D x causes y:f to equal x:f . Moreover, if we now set x:f D 3, then afterward not only does x:f equal 3, but y:f equals 3 as well. In other words, x and y point to the same object after the assignment y D x. Our attribute notation can “cascade.” For example, suppose that the attribute f is itself a pointer to some type of object that has an attribute g. Then the notation x:f :g is implicitly parenthesized as .x:f/:g. In other words, if we had assigned y D x:f , then x:f :g is the same as y:g. Sometimes, a pointer will refer to no object at all. In this case, we give it the special value NIL. We pass parameters to a procedure by value: the called procedure receives its own copy of the parameters, and if it assigns a value to a parameter, the change is not seen by the calling procedure. When objects are passed, the pointer to the data representing the object is copied, but the object’s attributes are not. For example, if x is a parameter of a called procedure, the assignment x D y within the called procedure is not visible to the calling procedure. The assignment x:f D 3, however, is visible. Similarly, arrays are passed by pointer, so that
22 Chapter 2 Getting Started a pointer to the array is passed,rather than the entire array,and changes to individual array elements are visible to the calling procedure. A return statement immediately transfers control back to the point of call in the calling procedure.Most return statements also take a value to pass back to the caller.Our pseudocode differs from many programming languages in that we allow multiple values to be returned in a single return statement. The boolean operators“and”and“or”are short circuiting.That is,when we evaluate the expression "x and y"we first evaluate x.If x evaluates to FALSE, then the entire expression cannot evaluate to TRUE,and so we do not evaluate y. If,on the other hand,x evaluates to TRUE,we must evaluate y to determine the value of the entire expression.Similarly,in the expression "x or y"we eval- uate the expression y only ifx evaluates to FALSE.Short-circuiting operators allow us to write boolean expressions such as“x≠NIL andx,f=y”without worrying about what happens when we try to evaluate x.f when x is NIL. The keyword error indicates that an error occurred because conditions were wrong for the procedure to have been called.The calling procedure is respon- sible for handling the error,and so we do not specify what action to take. Exercises 2.1-1 Using Figure 2.2 as a model,illustrate the operation of INSERTION-SORT on the array A=(31,41,59,26,41,58). 2.1-2 Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of non- decreasing order. 2.1-3 Consider the searching problem: Input:A sequence of n numbers A =(a1,a2,...,an)and a value v. Output:An index i such that v=Ai]or the special value NIL if v does not appear in A. Write pseudocode for linear search,which scans through the sequence,looking for v.Using a loop invariant,prove that your algorithm is correct.Make sure that your loop invariant fulfills the three necessary properties. 2.1-4 Consider the problem of adding two n-bit binary integers,stored in two n-element arrays A and B.The sum of the two integers should be stored in binary form in
22 Chapter 2 Getting Started a pointer to the array is passed, rather than the entire array, and changes to individual array elements are visible to the calling procedure. A return statement immediately transfers control back to the point of call in the calling procedure. Most return statements also take a value to pass back to the caller. Our pseudocode differs from many programming languages in that we allow multiple values to be returned in a single return statement. The boolean operators “and” and “or” are short circuiting. That is, when we evaluate the expression “x and y” we first evaluate x. If x evaluates to FALSE, then the entire expression cannot evaluate to TRUE, and so we do not evaluate y. If, on the other hand, x evaluates to TRUE, we must evaluate y to determine the value of the entire expression. Similarly, in the expression “x or y” we evaluate the expression y only if x evaluates to FALSE. Short-circuiting operators allow us to write boolean expressions such as “x ¤ NIL and x:f D y” without worrying about what happens when we try to evaluate x:f when x is NIL. The keyword error indicates that an error occurred because conditions were wrong for the procedure to have been called. The calling procedure is responsible for handling the error, and so we do not specify what action to take. Exercises 2.1-1 Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A D h31; 41; 59; 26; 41; 58i. 2.1-2 Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order. 2.1-3 Consider the searching problem: Input: A sequence of n numbers A D ha1; a2;:::;ani and a value . Output: An index i such that D AŒi or the special value NIL if does not appear in A. Write pseudocode for linear search, which scans through the sequence, looking for . Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties. 2.1-4 Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in
2.2 Analyzing algorithms 23 an (n+1)-element array C.State the problem formally and write pseudocode for adding the two integers. 2.2 Analyzing algorithms Analyzing an algorithm has come to mean predicting the resources that the algo- rithm requires.Occasionally,resources such as memory,communication band- width,or computer hardware are of primary concern,but most often it is compu- tational time that we want to measure.Generally,by analyzing several candidate algorithms for a problem,we can identify a most efficient one.Such analysis may indicate more than one viable candidate,but we can often discard several inferior algorithms in the process. Before we can analyze an algorithm,we must have a model of the implemen- tation technology that we will use,including a model for the resources of that technology and their costs.For most of this book,we shall assume a generic one- processor,random-access machine (RAM)model of computation as our imple- mentation technology and understand that our algorithms will be implemented as computer programs.In the RAM model,instructions are executed one after an- other,with no concurrent operations. Strictly speaking,we should precisely define the instructions of the RAM model and their costs.To do so,however,would be tedious and would yield little insight into algorithm design and analysis.Yet we must be careful not to abuse the RAM model.For example,what if a RAM had an instruction that sorts?Then we could sort in just one instruction.Such a RAM would be unrealistic,since real computers do not have such instructions.Our guide,therefore,is how real computers are de- signed.The RAM model contains instructions commonly found in real computers: arithmetic (such as add,subtract,multiply,divide,remainder,floor,ceiling),data movement (load,store,copy),and control (conditional and unconditional branch, subroutine call and return).Each such instruction takes a constant amount of time. The data types in the RAM model are integer and floating point(for storing real numbers).Although we typically do not concern ourselves with precision in this book,in some applications precision is crucial.We also assume a limit on the size of each word of data.For example,when working with inputs of size n,we typ- ically assume that integers are represented by c lgn bits for some constant c1. We require c>1 so that each word can hold the value of n,enabling us to index the individual input elements,and we restrict c to be a constant so that the word size does not grow arbitrarily.(If the word size could grow arbitrarily,we could store huge amounts of data in one word and operate on it all in constant time-clearly an unrealistic scenario.)
2.2 Analyzing algorithms 23 an .n C 1/-element array C. State the problem formally and write pseudocode for adding the two integers. 2.2 Analyzing algorithms Analyzing an algorithm has come to mean predicting the resources that the algorithm requires. Occasionally, resources such as memory, communication bandwidth, or computer hardware are of primary concern, but most often it is computational time that we want to measure. Generally, by analyzing several candidate algorithms for a problem, we can identify a most efficient one. Such analysis may indicate more than one viable candidate, but we can often discard several inferior algorithms in the process. Before we can analyze an algorithm, we must have a model of the implementation technology that we will use, including a model for the resources of that technology and their costs. For most of this book, we shall assume a generic oneprocessor, random-access machine (RAM) model of computation as our implementation technology and understand that our algorithms will be implemented as computer programs. In the RAM model, instructions are executed one after another, with no concurrent operations. Strictly speaking, we should precisely define the instructions of the RAM model and their costs. To do so, however, would be tedious and would yield little insight into algorithm design and analysis. Yet we must be careful not to abuse the RAM model. For example, what if a RAM had an instruction that sorts? Then we could sort in just one instruction. Such a RAM would be unrealistic, since real computers do not have such instructions. Our guide, therefore, is how real computers are designed. The RAM model contains instructions commonly found in real computers: arithmetic (such as add, subtract, multiply, divide, remainder, floor, ceiling), data movement (load, store, copy), and control (conditional and unconditional branch, subroutine call and return). Each such instruction takes a constant amount of time. The data types in the RAM model are integer and floating point (for storing real numbers). Although we typically do not concern ourselves with precision in this book, in some applications precision is crucial. We also assume a limit on the size of each word of data. For example, when working with inputs of size n, we typically assume that integers are represented by c lg n bits for some constant c 1. We require c 1 so that each word can hold the value of n, enabling us to index the individual input elements, and we restrict c to be a constant so that the word size does not grow arbitrarily. (If the word size could grow arbitrarily, we could store huge amounts of data in one word and operate on it all in constant time—clearly an unrealistic scenario.)
24 Chapter 2 Getting Started Real computers contain instructions not listed above,and such instructions rep- resent a gray area in the RAM model.For example,is exponentiation a constant- time instruction?In the general case,no;it takes several instructions to compute xy when x and y are real numbers.In restricted situations,however,exponentiation is a constant-time operation.Many computers have a"shift left"instruction,which in constant time shifts the bits of an integer by k positions to the left.In most computers,shifting the bits of an integer by one position to the left is equivalent to multiplication by 2,so that shifting the bits by k positions to the left is equiv- alent to multiplication by 2.Therefore,such computers can compute 2k in one constant-time instruction by shifting the integer I by k positions to the left,as long as k is no more than the number of bits in a computer word.We will endeavor to avoid such gray areas in the RAM model,but we will treat computation of 2 as a constant-time operation when k is a small enough positive integer. In the RAM model,we do not attempt to model the memory hierarchy that is common in contemporary computers.That is,we do not model caches or virtual memory.Several computational models attempt to account for memory-hierarchy effects,which are sometimes significant in real programs on real machines.A handful of problems in this book examine memory-hierarchy effects,but for the most part,the analyses in this book will not consider them.Models that include the memory hierarchy are quite a bit more complex than the RAM model,and so they can be difficult to work with.Moreover,RAM-model analyses are usually excellent predictors of performance on actual machines. Analyzing even a simple algorithm in the RAM model can be a challenge.The mathematical tools required may include combinatorics,probability theory,alge- braic dexterity,and the ability to identify the most significant terms in a formula. Because the behavior of an algorithm may be different for each possible input,we need a means for summarizing that behavior in simple,easily understood formulas. Even though we typically select only one machine model to analyze a given al- gorithm,we still face many choices in deciding how to express our analysis.We would like a way that is simple to write and manipulate,shows the important char- acteristics of an algorithm's resource requirements,and suppresses tedious details. Analysis of insertion sort The time taken by the INSERTION-SORT procedure depends on the input:sorting a thousand numbers takes longer than sorting three numbers.Moreover,INSERTION- SORT can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are.In general,the time taken by an algorithm grows with the size of the input,so it is traditional to describe the running time of a program as a function of the size of its input.To do so,we need to define the terms“running time'”and“size of input'"more carefully
24 Chapter 2 Getting Started Real computers contain instructions not listed above, and such instructions represent a gray area in the RAM model. For example, is exponentiation a constanttime instruction? In the general case, no; it takes several instructions to compute xy when x and y are real numbers. In restricted situations, however, exponentiation is a constant-time operation. Many computers have a “shift left” instruction, which in constant time shifts the bits of an integer by k positions to the left. In most computers, shifting the bits of an integer by one position to the left is equivalent to multiplication by 2, so that shifting the bits by k positions to the left is equivalent to multiplication by 2k. Therefore, such computers can compute 2k in one constant-time instruction by shifting the integer 1 by k positions to the left, as long as k is no more than the number of bits in a computer word. We will endeavor to avoid such gray areas in the RAM model, but we will treat computation of 2k as a constant-time operation when k is a small enough positive integer. In the RAM model, we do not attempt to model the memory hierarchy that is common in contemporary computers. That is, we do not model caches or virtual memory. Several computational models attempt to account for memory-hierarchy effects, which are sometimes significant in real programs on real machines. A handful of problems in this book examine memory-hierarchy effects, but for the most part, the analyses in this book will not consider them. Models that include the memory hierarchy are quite a bit more complex than the RAM model, and so they can be difficult to work with. Moreover, RAM-model analyses are usually excellent predictors of performance on actual machines. Analyzing even a simple algorithm in the RAM model can be a challenge. The mathematical tools required may include combinatorics, probability theory, algebraic dexterity, and the ability to identify the most significant terms in a formula. Because the behavior of an algorithm may be different for each possible input, we need a means for summarizing that behavior in simple, easily understood formulas. Even though we typically select only one machine model to analyze a given algorithm, we still face many choices in deciding how to express our analysis. We would like a way that is simple to write and manipulate, shows the important characteristics of an algorithm’s resource requirements, and suppresses tedious details. Analysis of insertion sort The time taken by the INSERTION-SORT procedure depends on the input: sorting a thousand numbers takes longer than sorting three numbers. Moreover, INSERTIONSORT can take different amounts of time to sort two input sequences of the same size depending on how nearly sorted they already are. In general, the time taken by an algorithm grows with the size of the input, so it is traditional to describe the running time of a program as a function of the size of its input. To do so, we need to define the terms “running time” and “size of input” more carefully
2.2 Analyzing algorithms 25 The best notion for input size depends on the problem being studied.For many problems,such as sorting or computing discrete Fourier transforms,the most nat- ural measure is the number of items in the input-for example,the array size n for sorting.For many other problems,such as multiplying two integers,the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation.Sometimes,it is more appropriate to describe the size of the input with two numbers rather than one.For instance,if the input to an algo- rithm is a graph,the input size can be described by the numbers of vertices and edges in the graph.We shall indicate which input size measure is being used with each problem we study. The running time of an algorithm on a particular input is the number of primitive operations or "steps"executed.It is convenient to define the notion of step so that it is as machine-independent as possible.For the moment,let us adopt the following view.A constant amount of time is required to execute each line of our pseudocode.One line may take a different amount of time than another line,but we shall assume that each execution of the ith line takes time ci,where ci is a constant.This viewpoint is in keeping with the RAM model,and it also reflects how the pseudocode would be implemented on most actual computers.> In the following discussion,our expression for the running time of INSERTION- SoRT will evolve from a messy formula that uses all the statement costs ci to a much simpler notation that is more concise and more easily manipulated.This simpler notation will also make it easy to determine whether one algorithm is more efficient than another. We start by presenting the INSERTION-SORT procedure with the time"cost" of each statement and the number of times each statement is executed.For each j=2,3,...,n,where n =A.length,we let ti denote the number of times the while loop test in line 5 is executed for that value of j.When a for or while loop exits in the usual way (i.e.,due to the test in the loop header),the test is executed one time more than the loop body.We assume that comments are not executable statements,and so they take no time. 5There are some subtleties here.Computational steps that we specify in English are often variants of a procedure that requires more than just a constant amount of time.For example,later in this book we might say "sort the points by x-coordinate,"which,as we shall see,takes more than a constant amount of time.Also,note that a statement that calls a subroutine takes constant time, though the subroutine,once invoked,may take more.That is,we separate the process of calling the subroutine-passing parameters to it,etc.-from the process of executing the subroutine
2.2 Analyzing algorithms 25 The best notion for input size depends on the problem being studied. For many problems, such as sorting or computing discrete Fourier transforms, the most natural measure is the number of items in the input—for example, the array size n for sorting. For many other problems, such as multiplying two integers, the best measure of input size is the total number of bits needed to represent the input in ordinary binary notation. Sometimes, it is more appropriate to describe the size of the input with two numbers rather than one. For instance, if the input to an algorithm is a graph, the input size can be described by the numbers of vertices and edges in the graph. We shall indicate which input size measure is being used with each problem we study. The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed. It is convenient to define the notion of step so that it is as machine-independent as possible. For the moment, let us adopt the following view. A constant amount of time is required to execute each line of our pseudocode. One line may take a different amount of time than another line, but we shall assume that each execution of the ith line takes time ci, where ci is a constant. This viewpoint is in keeping with the RAM model, and it also reflects how the pseudocode would be implemented on most actual computers.5 In the following discussion, our expression for the running time of INSERTIONSORT will evolve from a messy formula that uses all the statement costs ci to a much simpler notation that is more concise and more easily manipulated. This simpler notation will also make it easy to determine whether one algorithm is more efficient than another. We start by presenting the INSERTION-SORT procedure with the time “cost” of each statement and the number of times each statement is executed. For each j D 2; 3; : : : ; n, where n D A:length, we let tj denote the number of times the while loop test in line 5 is executed for that value of j . When a for or while loop exits in the usual way (i.e., due to the test in the loop header), the test is executed one time more than the loop body. We assume that comments are not executable statements, and so they take no time. 5There are some subtleties here. Computational steps that we specify in English are often variants of a procedure that requires more than just a constant amount of time. For example, later in this book we might say “sort the points by x-coordinate,” which, as we shall see, takes more than a constant amount of time. Also, note that a statement that calls a subroutine takes constant time, though the subroutine, once invoked, may take more. That is, we separate the process of calling the subroutine—passing parameters to it, etc.—from the process of executing the subroutine