22 Abstract Data Types and Algorithms A1m1=1; B:m:#1; ming=A【1】; for i:=2 to n do for i :=2 to n do ifA[i】<A[m】then ifA[i】<min then m :=i; begin m1=i; min:=A[m】 end; 1.7.An English dictionary is an ordered list of words with approximately 1100 pages.To search for a particular word using binary search we need to examine a maximum of 10 pages.Is there a better way of doing the search?Assume that the distribution of words is uniform;that is,the num- ber of words beginning with 'A',B',...and 'Z'are approximately equal. Hint:Divide the sequence not in the middle,but at a place more likely to be closer to the actual location (interpolation search). 1.8.Write bad and good programs to evaluate polynomials.For instance, evaluate 2x+4x2+5x3+13x4 at x 5.Design the necessary data structures and write the programs.Com- pare their time complexities. 1.9.Design a recursive algorithm for computing x(assume n is a power of 2) of the sequence x0=0 x1=1x2=1 Xn =xn/2 +3xn/4 1.10.Formulate a non-recursive efficient algorithm for the sequence of exercises 1.9 by not evaluating xk more than once (for a given k). 1.11.What is the time complexity of your solution to exercise 1.10. 1.12.Write a program to compute e c(n)=n+ 2!3!4! +.+n0 10！ What is the time complexity of your solution? 1.13.Find the asymptotic equivalent of the following functions: 3n2+10n n2+2” 10 21+1 n log n3 10log 3m
The Complexity of Algorithms 23 (f(n)+10)2 when f(n)=O(n) 1.14.Which of the following are valid? 0(1)=0(100) 0(1)=100 1.15.Show that if a computer executes algorithm A6 of size S in T units of time, then a computer which is 60 times faster would execute the algorithm in T time for size x where x=S+- loge60 logeS-1 Hint:n!≈ e 1.16.Can you give guidelines,as is done in section 1.5,for finding the best-case time complexities?If not,why not? 1.17.Verify the solutions to the recurrence relations of section 1.5. Bibliographic Notes and Further Reading The discussion of the complexity theory in this chapter is very pragmatic.In order to reason about the behaviour of algorithms more accurately and for com- paring algorithms,more precise and mathematical models of computation are needed.These include the Turing Machine,Decision Trees,the Random Access Machine etc.More on these models and their relationship to one another can be found in Aho et al.(1974).The effect of complexity of an algorithm on the size of problems which can be solved on faster computers can be found in Aho et al. (1974,1983),Stubbs and Webre (1985)and Knuth(1973).The double-loop of section 1.3 and the worst-case analysis of Pascal programs in section 1.5 are similar to those of Aho et al.(1983).Table 1.1 is from Aho et al.(1974).Wulf et al.(1981)show a more rigorous approach for deriving time complexities using assertions regarding time requirements of a program. The sequence problem of section 1.1 is the famous Fibonacci series.Note that in the seql procedure,the time complexity of the program to generate the sequence was bounded below by the sequence itself. In chapter 12,where 'hard'problems are discussed,some issues regarding exponential algorithms are discussed and the bibliographical notes give more relevant references. More on the interpolation search of exercise 1.7 which is of O(log log n)can be found in Gonnet et al.(1980).Apart from best-case,worst-case and average- case complexities,there is also amortised time complexity which is a measure of executing a program M number of times.For instance,when maintaining a linear
24 Abstract Data Types and Algorithms list with the search operation it is possible to have an unordered list,but every time an element is searched it is moved to the front of the list.In this example, although the worst-case complexity for one search operation remains O(n),how- ever,performing n search operations may require much less than O(n2)because of some locality of accesses to the elements of the list.This particular problem and a few algorithms are further discussed in Sleator and Tarjan (1985).Another example of this type of analysis is applied to the data type Component Set'of Kruskal's algorithm in section 7.3. Aho,A.,Hopcroft,J.and Ullman,J.(1974).The Design and Analysis of Com- puter Algorithms,Addison-Wesley,Reading,Massachusetts. Aho,A.V.,Hopcroft,J.E.and Ullman,J.D.(1983).Data Structures and Algorithms,Addison-Wesley,Reading,Massachusetts. Gonnet,G.H.,Rogers,L.D.and George,J.A.(1980).'An algorithmic and complexity analysis of interpolation search',Acta Informatica,Vol.13, pp.39-52. Knuth,D.E.(1973).The Art of Computer Programming.Volume 1:Funda- mental Algorithms,2nd edition,Addison-Wesley,Reading,Massachusetts. Sleator,D.D.and Tarjan,R.E.(1985).'Amortised efficiency of list update and paging rules',in CACM,Vol.28,No.2,pp.202-208. Stubbs,D.and Webre,N.(1985).Data Structures with Abstract Data Types and Pascal,Brooks/Cole Publishing,Monterey,California. Wulf,W.A.,Shaw,M.,Hilfinger,P.and Flon,L.(1981).Fundamental Structures of Computer Science,Addison-Wesley,Reading,Massachusetts
2 Abstract Data Types and Program Design A computer program (at an assembly-language level)can be informally defined as a sequence of instructions for a computer to perform a particular task.The exact form and sequencing of the instructions for a given task depend largely on the underlying architecture of a computer (physical machine).Writing a com- puter program therefore requires decisions on how to represent the task to be achieved in terms of the constructs of the architecture.However,more often than not,the formulation of a task as a specification is very different from its representation in terms of the architectural-level instructions.Such a disparity between these two levels of programming implies a considerable intellectual and organisational effort to produce a correct program for a task.In most cases, however,the organisational details are numerous and they become difficult to handle.To reduce the amount of such detailed organisational activity,we can define 'idealised'architectures on top of the machine architecture,and in this way we will provide a new framework for programmers so that they can express their requirements more easily and effectively.In this chapter we shall briefly discuss the main components of a program using an 'assembly-language'-level architecture,and then describe a more idealised architecture which would accom- modate higher-level constructs for certain programming elements:operation, control and data.The effect of using the new higher-level architecture is the removal of unnecessary details,which can be dealt with at a later stage in pro- gram development. 2.1 Elements of Program Design It is assumed that the reader is familiar with at least one assembly language.An assembly language directly reflects the physical architecture of the computer under consideration.Figure 2.1 shows a simplified architecture of a computer. The essential features of such an architecture are the particular representation of data,operations and control. Data.The structure of data used at this level is a linear memory unit (MU) organised as a linear sequence of bytes or words,and also a set of registers(RU) where each one can store one word of data. Operations.Pieces of data are manipulated by performing operations on them. Such operations as arithmetic (addition,subtraction,division,multiplication) and logical operations (and,or,not etc.)(ALU),data transfer to and from memory (MU)or registers (RU)(instructions such as move and store),and 25
26 Abstract Data Types and Algorithms Memory Register Arithmetic and Logic Unit(MU) Unit(RU) Unit (ALU) Control Unit (CU) Input Output Figure 2.1 A simple computer architecture. special operations such as shift,rotate etc.(CU)are supported at this level. Control.In order to achieve a given task,the operations on data have to be per- formed in a certain sequence.This sequencing of operations is known as control. Default sequencing (in Pascal),different branch (goto or jump)commands, jump-to_subroutine and return_from_subroutine are among control mechanisms at the machine level (CU). To design a program,first the data to be used in the program must be organised and allocated.Then,using the correct control constructs and operations,the data should be manipulated to produce the required results. Using these minimal and primitive facilities the task of developing large pro- grams is very difficult,if not impossible.Although the programs can be broken down into procedures (subroutines),however the assembly language environ- ment lacks mechanisms for more abstract definitions of data and specification of parameters to sub-programs.Also,there is no standard method for passing para- meters to sub-programs.This in turn implies that reasoning about the behaviour of programs becomes very difficult as their size and complexity grow.The major reason for this difficulty is the amount of detail (data definition,procedure definition,parameter passing etc.)which must be handled at any moment.As an example,let us consider the operation of adding an extra number to the end of a list of numbers stored in the memory.Let us denote this operation as add_to_ end(n)where n should be added to the end of the list.To be able to do this,we aim to write a procedure and we should consider the following details: Where are the elements of this list stored in the main memory? Are the elements stored in consecutive locations of memory or not? If not,how are the elements linked together?