1.2 Algorithms as a technology 11 Exercises 1.1-1 Give a real-world example that requires sorting or a real-world example that re- quires computing a convex hull. 1.1-2 Other than speed,what other measures of efficiency might one use in a real-world setting? 1.1-3 Select a data structure that you have seen previously,and discuss its strengths and limitations. 1.1-4 How are the shortest-path and traveling-salesman problems given above similar? How are they different? 1.1-5 Come up with a real-world problem in which only the best solution will do.Then come up with one in which a solution that is"approximately"the best is good enough. 1.2 Algorithms as a technology Suppose computers were infinitely fast and computer memory was free.Would you have any reason to study algorithms?The answer is yes,if for no other reason than that you would still like to demonstrate that your solution method terminates and does so with the correct answer. If computers were infinitely fast,any correct method for solving a problem would do.You would probably want your implementation to be within the bounds of good software engineering practice(for example,your implementation should be well designed and documented),but you would most often use whichever method was the easiest to implement. Of course,computers may be fast,but they are not infinitely fast.And memory may be inexpensive,but it is not free.Computing time is therefore a bounded resource,and so is space in memory.You should use these resources wisely,and algorithms that are efficient in terms of time or space will help you do so
1.2 Algorithms as a technology 11 Exercises 1.1-1 Give a real-world example that requires sorting or a real-world example that requires computing a convex hull. 1.1-2 Other than speed, what other measures of efficiency might one use in a real-world setting? 1.1-3 Select a data structure that you have seen previously, and discuss its strengths and limitations. 1.1-4 How are the shortest-path and traveling-salesman problems given above similar? How are they different? 1.1-5 Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is “approximately” the best is good enough. 1.2 Algorithms as a technology Suppose computers were infinitely fast and computer memory was free. Would you have any reason to study algorithms? The answer is yes, if for no other reason than that you would still like to demonstrate that your solution method terminates and does so with the correct answer. If computers were infinitely fast, any correct method for solving a problem would do. You would probably want your implementation to be within the bounds of good software engineering practice (for example, your implementation should be well designed and documented), but you would most often use whichever method was the easiest to implement. Of course, computers may be fast, but they are not infinitely fast. And memory may be inexpensive, but it is not free. Computing time is therefore a bounded resource, and so is space in memory. You should use these resources wisely, and algorithms that are efficient in terms of time or space will help you do so
12 Chapter I The Role of Algorithms in Computing Efficiency Different algorithms devised to solve the same problem often differ dramatically in their efficiency.These differences can be much more significant than differences due to hardware and software. As an example,in Chapter 2,we will see two algorithms for sorting.The first, known as insertion sort,takes time roughly equal to cin2 to sort n items,where c is a constant that does not depend on n.That is,it takes time roughly proportional to n2.The second,merge sort,takes time roughly equal to can lgn,where Ign stands for log2n and c2 is another constant that also does not depend on n.Inser- tion sort typically has a smaller constant factor than merge sort,so that c<c2. We shall see that the constant factors can have far less of an impact on the running time than the dependence on the input size n.Let's write insertion sort's running time as cin.n and merge sort's running time as can.Ig n.Then we see that where insertion sort has a factor of n in its running time,merge sort has a factor of lgn, which is much smaller.(For example,when n=1000,Ig n is approximately 10, and when n equals one million,Ig n is approximately only 20.)Although insertion sort usually runs faster than merge sort for small input sizes,once the input size n becomes large enough,merge sort's advantage of lgn vs.n will more than com- pensate for the difference in constant factors.No matter how much smaller c is than c2,there will always be a crossover point beyond which merge sort is faster. For a concrete example,let us pit a faster computer (computer A)running inser- tion sort against a slower computer(computer B)running merge sort.They each must sort an array of 10 million numbers.(Although 10 million numbers might seem like a lot,if the numbers are eight-byte integers,then the input occupies about 80 megabytes,which fits in the memory of even an inexpensive laptop com- puter many times over.)Suppose that computer A executes 10 billion instructions per second (faster than any single sequential computer at the time of this writing) and computer B executes only 10 million instructions per second,so that com- puter A is 1000 times faster than computer B in raw computing power.To make the difference even more dramatic,suppose that the world's craftiest programmer codes insertion sort in machine language for computer A,and the resulting code requires 2n2 instructions to sort n numbers.Suppose further that just an average programmer implements merge sort,using a high-level language with an inefficient compiler,with the resulting code taking 50n lg n instructions.To sort 10 million numbers,computer A takes 2.(1)2instructions0.000 seconds (more than 5.5 hours). 1010 instructions/second while computer B takes
12 Chapter 1 The Role of Algorithms in Computing Efficiency Different algorithms devised to solve the same problem often differ dramatically in their efficiency. These differences can be much more significant than differences due to hardware and software. As an example, in Chapter 2, we will see two algorithms for sorting. The first, known as insertion sort, takes time roughly equal to c1n2 to sort n items, where c1 is a constant that does not depend on n. That is, it takes time roughly proportional to n2. The second, merge sort, takes time roughly equal to c2n lg n, where lg n stands for log2 n and c2 is another constant that also does not depend on n. Insertion sort typically has a smaller constant factor than merge sort, so that c1 < c2. We shall see that the constant factors can have far less of an impact on the running time than the dependence on the input size n. Let’s write insertion sort’s running time as c1n n and merge sort’s running time as c2n lg n. Then we see that where insertion sort has a factor of n in its running time, merge sort has a factor of lg n, which is much smaller. (For example, when n D 1000, lg n is approximately 10, and when n equals one million, lg n is approximately only 20.) Although insertion sort usually runs faster than merge sort for small input sizes, once the input size n becomes large enough, merge sort’s advantage of lg n vs. n will more than compensate for the difference in constant factors. No matter how much smaller c1 is than c2, there will always be a crossover point beyond which merge sort is faster. For a concrete example, let us pit a faster computer (computer A) running insertion sort against a slower computer (computer B) running merge sort. They each must sort an array of 10 million numbers. (Although 10 million numbers might seem like a lot, if the numbers are eight-byte integers, then the input occupies about 80 megabytes, which fits in the memory of even an inexpensive laptop computer many times over.) Suppose that computer A executes 10 billion instructions per second (faster than any single sequential computer at the time of this writing) and computer B executes only 10 million instructions per second, so that computer A is 1000 times faster than computer B in raw computing power. To make the difference even more dramatic, suppose that the world’s craftiest programmer codes insertion sort in machine language for computer A, and the resulting code requires 2n2 instructions to sort n numbers. Suppose further that just an average programmer implements merge sort, using a high-level language with an inefficient compiler, with the resulting code taking 50n lg n instructions. To sort 10 million numbers, computer A takes 2 .107/2 instructions 1010 instructions/second D 20,000 seconds (more than 5.5 hours) ; while computer B takes
1.2 Algorithms as a technology 13 50.1071g 107 instructions 1163 seconds (less than 20 minutes). 107 instructions/second By using an algorithm whose running time grows more slowly,even with a poor compiler,computer B runs more than 17 times faster than computer A!The advan- tage of merge sort is even more pronounced when we sort 100 million numbers: where insertion sort takes more than 23 days,merge sort takes under four hours. In general,as the problem size increases,so does the relative advantage of merge sort. Algorithms and other technologies The example above shows that we should consider algorithms,like computer hard- ware,as a technology.Total system performance depends on choosing efficient algorithms as much as on choosing fast hardware.Just as rapid advances are being made in other computer technologies,they are being made in algorithms as well. You might wonder whether algorithms are truly that important on contemporary computers in light of other advanced technologies,such as advanced computer architectures and fabrication technologies, easy-to-use,intuitive,graphical user interfaces (GUIs), object-oriented systems, integrated Web technologies,and fast networking,both wired and wireless. The answer is yes.Although some applications do not explicitly require algorith- mic content at the application level (such as some simple,Web-based applications), many do.For example,consider a Web-based service that determines how to travel from one location to another.Its implementation would rely on fast hardware,a graphical user interface,wide-area networking,and also possibly on object ori- entation.However,it would also require algorithms for certain operations,such as finding routes (probably using a shortest-path algorithm),rendering maps,and interpolating addresses. Moreover,even an application that does not require algorithmic content at the application level relies heavily upon algorithms.Does the application rely on fast hardware?The hardware design used algorithms.Does the application rely on graphical user interfaces?The design of any GUI relies on algorithms.Does the application rely on networking?Routing in networks relies heavily on algorithms. Was the application written in a language other than machine code?Then it was processed by a compiler,interpreter,or assembler,all of which make extensive use
1.2 Algorithms as a technology 13 50 107 lg 107 instructions 107 instructions/second 1163 seconds (less than 20 minutes) : By using an algorithm whose running time grows more slowly, even with a poor compiler, computer B runs more than 17 times faster than computer A! The advantage of merge sort is even more pronounced when we sort 100 million numbers: where insertion sort takes more than 23 days, merge sort takes under four hours. In general, as the problem size increases, so does the relative advantage of merge sort. Algorithms and other technologies The example above shows that we should consider algorithms, like computer hardware, as a technology. Total system performance depends on choosing efficient algorithms as much as on choosing fast hardware. Just as rapid advances are being made in other computer technologies, they are being made in algorithms as well. You might wonder whether algorithms are truly that important on contemporary computers in light of other advanced technologies, such as advanced computer architectures and fabrication technologies, easy-to-use, intuitive, graphical user interfaces (GUIs), object-oriented systems, integrated Web technologies, and fast networking, both wired and wireless. The answer is yes. Although some applications do not explicitly require algorithmic content at the application level (such as some simple, Web-based applications), many do. For example, consider a Web-based service that determines how to travel from one location to another. Its implementation would rely on fast hardware, a graphical user interface, wide-area networking, and also possibly on object orientation. However, it would also require algorithms for certain operations, such as finding routes (probably using a shortest-path algorithm), rendering maps, and interpolating addresses. Moreover, even an application that does not require algorithmic content at the application level relies heavily upon algorithms. Does the application rely on fast hardware? The hardware design used algorithms. Does the application rely on graphical user interfaces? The design of any GUI relies on algorithms. Does the application rely on networking? Routing in networks relies heavily on algorithms. Was the application written in a language other than machine code? Then it was processed by a compiler, interpreter, or assembler, all of which make extensive use
14 Chapter I The Role of Algorithms in Computing of algorithms.Algorithms are at the core of most technologies used in contempo- rary computers. Furthermore,with the ever-increasing capacities of computers,we use them to solve larger problems than ever before.As we saw in the above comparison be- tween insertion sort and merge sort,it is at larger problem sizes that the differences in efficiency between algorithms become particularly prominent. Having a solid base of algorithmic knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.With modern com- puting technology,you can accomplish some tasks without knowing much about algorithms,but with a good background in algorithms,you can do much,much more. Exercises 1.2-1 Give an example of an application that requires algorithmic content at the applica- tion level,and discuss the function of the algorithms involved. 1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine.For inputs of size n,insertion sort runs in 8n2 steps,while merge sort runs in 64n lg n steps.For which values of n does insertion sort beat merge sort? 1.2-3 What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2"on the same machine? Problems 1-1 Comparison of running times For each function f(n)and time t in the following table,determine the largest size n of a problem that can be solved in time t,assuming that the algorithm to solve the problem takes f(n)microseconds
14 Chapter 1 The Role of Algorithms in Computing of algorithms. Algorithms are at the core of most technologies used in contemporary computers. Furthermore, with the ever-increasing capacities of computers, we use them to solve larger problems than ever before. As we saw in the above comparison between insertion sort and merge sort, it is at larger problem sizes that the differences in efficiency between algorithms become particularly prominent. Having a solid base of algorithmic knowledge and technique is one characteristic that separates the truly skilled programmers from the novices. With modern computing technology, you can accomplish some tasks without knowing much about algorithms, but with a good background in algorithms, you can do much, much more. Exercises 1.2-1 Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved. 1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort? 1.2-3 What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine? Problems 1-1 Comparison of running times For each function f .n/ and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f .n/ microseconds
Notes for Chapter I 15 1 1 1 1 1 second minute hour day month year century Ign 沉 h nlgn n2 n3 2n n！ Chapter notes There are many excellent texts on the general topic of algorithms,including those by Aho,Hopcroft,and Ullman [5,6];Baase and Van Gelder [28];Brassard and Bratley [54];Dasgupta,Papadimitriou,and Vazirani [82];Goodrich and Tamassia [148];Hofri [175];Horowitz,Sahni,and Rajasekaran [181];Johnsonbaugh and Schaefer [193];Kingston [205];Kleinberg and Tardos [208];Knuth [209,210, 211];Kozen [220];Levitin [235];Manber [242];Mehlhorn [249,250,251];Pur- dom and Brown [287]:Reingold,Nievergelt,and Deo [293]:Sedgewick [306]; Sedgewick and Flajolet [307];Skiena [318];and Wilf [356].Some of the more practical aspects of algorithm design are discussed by Bentley [42,43]and Gonnet [145].Surveys of the field of algorithms can also be found in the Handbook of The- oretical Computer Science,Volume A [342]and the CRC Algorithms and Theory of Computation Handbook [25].Overviews of the algorithms used in computational biology can be found in textbooks by Gusfield [156],Pevzner [275],Setubal and Meidanis [310],and Waterman [350]
Notes for Chapter 1 15 1 1 1 1 1 1 1 second minute hour day month year century lg n pn n n lg n n2 n3 2n nŠ Chapter notes There are many excellent texts on the general topic of algorithms, including those by Aho, Hopcroft, and Ullman [5, 6]; Baase and Van Gelder [28]; Brassard and Bratley [54]; Dasgupta, Papadimitriou, and Vazirani [82]; Goodrich and Tamassia [148]; Hofri [175]; Horowitz, Sahni, and Rajasekaran [181]; Johnsonbaugh and Schaefer [193]; Kingston [205]; Kleinberg and Tardos [208]; Knuth [209, 210, 211]; Kozen [220]; Levitin [235]; Manber [242]; Mehlhorn [249, 250, 251]; Purdom and Brown [287]; Reingold, Nievergelt, and Deo [293]; Sedgewick [306]; Sedgewick and Flajolet [307]; Skiena [318]; and Wilf [356]. Some of the more practical aspects of algorithm design are discussed by Bentley [42, 43] and Gonnet [145]. Surveys of the field of algorithms can also be found in the Handbook of Theoretical Computer Science, Volume A [342] and the CRC Algorithms and Theory of Computation Handbook [25]. Overviews of the algorithms used in computational biology can be found in textbooks by Gusfield [156], Pevzner [275], Setubal and Meidanis [310], and Waterman [350]