Ri NAL D Ee. Rene $7es Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Introduction to Algorithms The MIT Press Cambridge, Massachusetts London, England McGraw-Hill Book Company New York St. Louis San Francisco Montreal Toronto‘Twenty-fith printing, 2000, ‘This book is one of a series of texts writen by faculty of the Electrical Engineering and ‘Computer Science Department at the Massachusetis Institute of Technology, It was edited and produced by The MIT Press under a joint production-distribution agreement with the McGraw-Hill Book Company. Ordering Information North America ‘Text orders should be axidressed to the McGraw-Hill Book Company. All other orders should be addressed to The MIT Press, Outside North America Al orders should be addressed 10 The MIT Press or its local distributor. (©1990 by The Massachusetts Institute of Technology All rights reserved. No part of this book may be reproduced in any form or by any elec- tronic or mechanical means (including photocopying, recording. or information storage and retrieval) without permission in writing from the publisher, ‘This book was printed and bound in the United States of America Library of Congress Cataloging-in-Publication Data Conmen, Thomas H. Introduction to Algorithms / Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest P. cm—(The MIT electrical engineering and computer science series) Includes bibliographical references ISBN 0.262-03141-8 (MIT Press Hardcover) ISBN 0-262-53001-0 (MIT Press Paperback) ISBN 0.07-013143.0 (McGraw-Hill) 1, Electronic digital computers—Programming. 2. Algorithms. 1. Leiserson, Charles Eric, “M. Rivest. Ronald L. IL Tile. 1V. Series, QA76.6.C662_1989 005,1-e20 89-13027 crContents 1 Introduction 7 1.1 Algorithms 1 1.2. Analyzing alge 1.3 Designing algorithms 17 1.4 Summary 16 I Mathematical Foundations Introduction 27 2 Growth of Functions 23 2.1 Asymptotic notation 23 2.2. Standard notations and common functions 32 3 Summations 42 3.1 Summation formulas and properties 42 3.2 Bounding summations 46 4 Recurrences 53 4.1 The substitution method 54 4.2 The iteration method 58 4,3. The master method 6/ % 4.4 Proof of the master theorem 64 Sets, Ete. 77 SA Sets 77 5.2 Relations 81 5.3. Functions 84 5.4 Graphs 86 5.5 Trees 91" Contents 6 — Counting and Probability 99 6.1 Counting 99 6.2 Probability 104 6.3 Discrete random variables 111 6.4 The geometric and binomial distributions 1/5 * 6.5 The tails of the binomial distribution 121 6.6 Probabilistic analysis 126 II Sorting and Order Statistics Introduction 137 7 Heapsort 140 7.1 Heaps 140 7.2. Maintaining the heap property 142 7.3 Building aheap 145 7.4 The heapsort algorithm 147 7.5. Priority queues 149 8 Quicksort 153 8.1 Description of quicksort 153 8.2 Performance of quicksort 156 8.3 Randomized versions of quicksort 161 8.4 Analysis of quicksort 163 9 — Sorting in Linear Time 172 9.1 Lower bounds for sorting 172 9.2 Counting sort 175 9.3 Radix sort 178 9.4 Bucket sort 180 10 Medians and Order Statistics 185 10.1 Minimum and maximum 185 10.2 Selection in expected linear time 187 10.3 Selection in worst-case linear time 189Contents vii TI Data Structures 2 2B 4 15 Introduction 197 Elementary Data Structures 200 11.1 Stacks and queues 200 11.2 Linked lists 204 11.3 Implementing pointers and objects 209 11.4 Representing rooted trees 2/3 Hash Tables 219 12.1 Direct-address tables 219 12.2 Hash tables 227 12.3 Hash functions 226 12.4 Open addressing 232 Binary Search Trees 244 13.1 What is a binary search tree? 244 13.2 Querying a binary search tree 246 13.3 Insertion and deletion 250 13.4 Randomly built binary search trees 254 Red-Black Trees 263 14.1 Properties of red-black trees 263 14.2 Rotations 265 14.3 Insertion 268 144 Deletion 272 Augmenting Data Structures 287 15.1 Dynamic order statistics 287 15.2 How to augment a data structure 287 15.3 Interval trees 290 IV Advanced Design and Analysis Techniques 16 Introduction 299 Dynamic Programming 301 16.1 Matrix-chain multiplication 302 16.2 Elements of dynamic programming 309 16.3 Longest common subsequence 3/4 16.4 Optimal polygon triangulation 320wit Contents 17 Greedy Algorithms 329 17.1 An activity-selection problem 329 17.2 Elements of the greedy strategy 333 17.3 Huffman codes 337 * 17.4 Theoretical foundations for greedy methods 345, * — 17.5 A task-scheduling problem 350 18 Amortized Analysis 356 18.1 The aggregate method 357 18.2 The accounting method 360 18.3 The potential method 363 18.4 Dynamic tables 367 ——— V Advanced Data Structures Introduction 379 19 BeTrees 381 19.1 Definition of B-trees 384 19.2 Basic operations on B-trees 387 19.3 Deleting a key from a B-tree 395 20 Binomial Heaps 400 20.1 Binomial trees and binomial heaps 401 20.2 Operations on binomial heaps 406 21 Fibonacci Heaps 420 21.1 Structure of Fibonacci heaps 42/ 21.2 Mergeable-heap operations 423 21.3 Decreasing a key and deleting a node 431 21.4 Bounding the maximum degree 435, 22 Data Structures for Disjoint Sets 440 22.1 Disjoint-set operations 440 22.2 Linked-list representation of disjoint sets 443 22.3 Disjoint-set forests 446 * 22.4 Analysis of union by rank with path compression 450Contents ix VI Graph Algorithms 23 24 25 26 Introduction 463, Elementary Graph Algorithms 465 23.1 Representations of graphs 465 23.2 Breadth-first search 469 23.3 Depth-first search 477 23.4 Topological sort 485 23.5 Strongly connected components 488 Minimum Spanning Trees 498 24.1 Growing a minimum spanning tree 499 24.2 The algorithms of Kruskal and Prim 504 Single-Source Shortest Paths 514 25.1 Shortest paths and relaxation 5/8 25.2 Dijkstra’s algorithm 527 25.3 The Bellman-Ford algorithm 532 25.4 Single-source shortest paths in directed acyclic graphs 536 25.5 Difference constraints and shortest paths 539 All-Pairs Shortest Paths 550 26.1 Shortest paths and matrix multiplication 552 26.2 The Floyd-Warshall algorithm 558 26.3 Johnson’s algorithm for sparse graphs 565 26.4 A general framework for solving path problems in di- rected graphs 570 ‘Maximum Flow 579 27.1 Flow networks 580 27.2 The Ford-Fulkerson method 587 27.3 Maximum bipartite matching 600 27.4 Preflow-push algorithms 605 27.5 The lift-to-front algorithm 6/5VII Selected Topics 28 29 31 2 33 Contents Introduction 637 Sorting Networks 634 28.1 Comparison networks 634 28.2 The zero-one principle 639 28.3 A bitonic sorting network 642 28.4 A merging network 646 28.5 A sorting network 648 Arithmetic Circuits 654 29.1 Combinational circuits 655 29.2 Addition circuits 660 29.3 Multiplication circuits 671 29.4 Clocked circuits 678 Algorithms for Parallel Computers 688 30.1 Pointer jumping 692 30.2 CRCW algorithms versus EREW algorithms 70/ 30.3 Brent’s theorem and work efficiency 709 30.4 Work-efficient parallel prefix computation 714 30.5 Deterministic symmetry breaking 720 Matrix Operations 730 31.1 Properties of matrices 730 31.2 Strassen’s algorithm for matrix multiplication 739 31.3 Algebraic number systems and boolean matrix multipli- cation 745 31.4 Solving systems of linear equations 749 31.5 Inverting matrices 762 31.6 Symmetric positive-definite matrices and least-squares approximation 766 Polynomials and the FFT 776 32.1 Representation of polynomials 778 32.2 The DFT and FFT 783 32.3 Efficient FFT implementations 791 Number-Theoretic Algorithms 807 33.1 Elementary number-theoretic notions 802 33.2 Greatest common divisor 808 33.3 Modular arithmetic 814Contents xi 34 35 37 33.4 Solving modular linear equations 820 33.5 The Chinese remainder theorem 823 33.6 Powers of an element 827 33.7 The RSA public-key cryptosystem 837 33.8 Primality testing 837 33.9 Integer factorization 844 String Matching 853 34.1 The naive string-matching algorithm 855 34.2 The Rabin-Karp algorithm 857 34.3 String matching with finite automata 862 34.4 The Knuth-Morris-Pratt algorithm 869 34.5 The Boyer-Moore algorithm 876 Computational Geometry 886 35.1 Line-segment properties 887 35.2 Determining whether any pair of segments intersects 892 35.3 Finding the convex hull 898 35.4 Finding the closest pair of points 908 NP-Completeness 916 36.1 Polynomial time 917 36.2 Polynomial-time verification 924 36.3 NP-completeness and reducibility 929 36.4 NP-completeness proofs 939 36.5 NP-complete problems 946 Approximation Algorithms 964 37.1 The vertex-cover problem 966 37.2 The traveling-salesman problem 969 37.3 The set-covering problem 974 37.4 The subset-sum problem 978 Bibliography 987 Index 9971.1 Algorithms Introduction This chapter will familiarize you with the framework we shall use through- out the book to think about the design and analysis of algorithms. It is self-contained, but it does include several references to material that will be introduced in Part I We begin with a discussion of computational problems in general and of the algorithms needed to solve them, with the problem of sorting as our running example. We introduce a “pseudocode” that should be familiar to readers who have done computer programming to show how we shall specify our algorithms. Insertion sort, a simple sorting algorithm, serves as an initial example. We analyze the running time of insertion sort, intro- ducing a notation that focuses on how that time increases with the number of items to be sorted. We also introduce the divide-and-conquer approach to the design of algorithms and use it to develop an algorithm called merge sort, We end with a comparison of the two sorting algorithms. Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. We can also view an algorithm as a tool for solving a well-specified com- putational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship. We begin our study of algorithms with the problem of sorting a sequence of numbers into nondecreasing order. This problem arises frequently in practice and provides fertile ground for introducing many standard design techniques and analysis tools. Here is how we formally define the sorting problem:Chapter I Introduction Input: A sequence of 1 numbers (a1, @2,...,dn) Output: A permutation (reordering) (aj, 4,...,4,) of the input sequence such that aj Insert AL/] into the sorted sequence {1 ..j - 1]. 4 iej-l 5 while i > 0 and Ali] > key 6 do Afi + 1) — Ati) 7 iei-t 8 Ali + 1] = key Figure 1.2 shows how this algorithm works for 4 = (5,2,4,6,1,3). The index j indicates the “current card” being inserted into the hand. Array elements A[1..j — 1] constitute the currently sorted hand, and elements ALj + L..m] correspond to the pile of cards still on the table. The index j ‘moves left to right through the array. At each iteration of the “outer” for loop, the element A[j] is picked out of the array (line 2). Then, starting inChapter 1 Introduction 1203 4 5 6 done Figure 1.2 The operation of INsERTION-SorT on the array 4 = (5,2,4,6, 1,3). The position of index j is indicated by a circle. position j — 1, elements are successively moved one position to the right until the proper position for 4f/] is found (lines 4-7), at which point it is inserted (line 8). Pseudocode conventions ‘We use the following conventions in our pseudocode. 1. Indentation indicates block structure. For example, the body of the for loop that begins on line 1 consists of lines 2-8, and the body of the while loop that begins on line 5 contains lines 6-7 but not line 8, Our indentation style applies to if-then-else statements as well. Using indentation instead of conventional indicators of block structure, such as begin and end statements, greatly reduces clutter while preserving, or even enhancing, clarity.! 2. The looping constructs while, for, and repeat and the conditional con- structs if, then, and else have the the same interpretation as in Pascal. 3. The symbol “D-” indicates that the remainder of the line is a comment. 4. 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 5. Variables (such as i, j, and key) are local to the given procedure. We shall not use global variables without explicit indication, ‘In real programming languages, it is generally not advisable to use indentation alone 10 indicate block structure, since levels of indentation are hard to determine when code is spit across pages.LL Algorithms 5 6. Array elements are accessed by specifying the array name followed by the index in square brackets. For example, A[/] indicates the ith element of the array 4. The notation “..” is used to indicate a range of values within an array. Thus, A[1..j] indicates the subarray of A consisting of elements [1], A[2},.... ALi]. 7. Compound data are typically organized into objects, which are com- prised of attributes or flelds. A particular field is accessed using the field name followed by the name of its object in square brackets. For exam- ple, we treat an array as an object with the attribute /ength indicating how many elements it contains. To specify the number of elements in an array A, we write length{4]. Although we use square brackets for both array indexing and object attributes, it will usually be clear from the context which interpretation is intended. A variable representing an array or object is treated as a pointer to the data representing the array or object. For all fields f of an object x, setting y — x causes f[y] = f[x]. Moreover, if we now set f[x] — 3, then afterward not only is f[x] = 3, but f[y] = 3 as well. In other words, x and y point to (“are”) the same object after the assignment yor, Sometimes, a pointer will refer to no object at all. In this case, we give it the special value ni. 8, Parameters are passed 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 routine. When objects are passed, the pointer to the data representing the object is copied, but the object's fields are not. For example, if x 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] ~ 3, however, is visible. Exercises LLL Using Figure 1.2 as a model, illustrate the operation of INSERTION-SORT on the array 4 = (31,41, 59, 26,41, 58). 112 Rewrite the INsERTION-SoRT procedure to sort into nonincreasing instead of nondecreasing order. 11-3 Consider the searching problem: Input: A sequence of n numbers 4 = (a1,2,...,dx) and a value v. Output: An index i such that v = A[i] or the special value wi if v does not appear in A.6 Chapter 1 Introduction Write pseudocode for linear search, which scans through the sequence, looking for v. Ld-4 Consider the problem of adding two n-bit binary integers, stored in two n-clement arrays A and B. The sum of the two integers should be stored in binary form in an (n + 1)-element array C. State the problem formally and write pseudocode for adding the two integers. 1.2. Analyzing algorithms Analyzing an algorithm has come to mean predicting the resources that the algorithm requires. Occasionally, resources such as memory, communica- tion bandwidth, or logic gates are of primary concern, but most often it is computational time that we want to measure. Generally, by analyzing sev- eral candidate algorithms for a problem, a most efficient one can be easily identified. Such analysis may indicate more than one viable candidate, but several inferior algorithms are usually discarded in the process. Before we can analyze an algorithm, we must have a model of the imple- mentation technology that will be used, 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 computa- tion as our implementation technology and understand that our algorithms will be implemented as computer programs. In the RAM model, instruc- tions are executed one after another, with no concurrent operations. In later chapters, however, we shall have occasion to investigate models for parallel computers and digital hardware. Analyzing even a simple algorithm can be a challenge, The mathematical tools required may include discrete combinatorics, elementary probability theory, algebraic dexterity, and the ability to identity 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. One immediate goal is to find a means of expression 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 inpt sorting a thousand numbers takes longer than sorting three numbers. More- over, INSERTION-SoRT can take different amounts of time to sort two input1.2. Analyzing algorithms 7 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. ‘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 c), where ¢; 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 state- ment costs ¢; to a much simpler notation that is more concise and more easily manipulated. This simpler notation will also make it easy to deter- mine 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 ex- ecuted. For each j = 2,3,....n, where m = length A}, we let t) be the number of times the while loop test in line 5 is executed for that value of j. We assume that comments are not executable statements, and so they take no time, 2 There 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 cals 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.Chapter 1 Introduction INSERTION-SORT( 4) cost times 1 for j — 2 to lengch{ A] aon 2 do key = AU] n= 3 > Insert ALj] into the sorted Db sequence A{1..j—1},0 9 =I 4 inj-l onal 5 while i>Oand Ali]>key cs Dat 6 do Ali+ 1] — Ali] & (=) 7 Gein cr (G1) 8 Ali+ I] — key % The running time of the algorithm is the sum of running times for each statement executed; a statement that takes ¢; steps to execute and is exe- cuted 1 times will contribute ¢\n to the total running time.3 To compute T(n), the running time of INSERTION-SoRT, we sum the products of the cost and times columns, obtaining Tin) = cin tern—1) bean 1) tes oy Heeb - DD +07 Dt = 1) + x(t = 1) ms Even for inputs of a given size, an algorithm’s running time may depend on which input of that size is given, For example, in INSERTION-SoRT, the best case occurs if the array is already sorted. For cach j = 2,3,...,7, we then find that A{i] < key in line 5 when i has its initial value of j — 1 Thus ¢; = 1 for j= 2,3,...,m, and the best-case running time is Tin) = en bex(n= 1) + eal = 1) + es(n = 1) + ca( - 1) = (Ca + Cyt CS + C4) — (C2 +04 +05 +04) « This running time can be expressed as an +b for constants a and b that depend on the statement costs cy; it is thus a linear function of n. If the array is in reverse sorted order—that is, in decreasing order—the worst case results. We must compare each element 4[j] with each element in the entire sorted subarray A[I..j ~ 1], and so t; = j for j = 2,3,...,n. Noting that n(n +1) This characteristic does not necessarily hold for a resource such as memory. A statement that references m words of memory and is executed # times does not necessarily consume ‘mn words of memory in total1.2. Analyzing algorithms 9 (we shall review these summations in Chapter 3), we find that in the worst case, the running time of INSERTION-SoRT is Tn) = cintexn~1) +ea(n~1) +65 ‘ca ) 25 (EB) 0 (MED) ven 64,0) 2 tgs 9 (G+ $+G)rs(atatat+G-F-Fre)n — (cr + C4 + C5 +03) This worst-case running time can be expressed as an? +bn-+c for constants 4, b, and c that again depend on the statement costs c;; itis thus a quadratic function of n. Typically, as in insertion sort, the running time of an algorithm is fixed for a given input, although in later chapters we shall see some interesting “randomized” algorithms whose behavior can vary even for a fixed input. Worst-case and average-case analysis In our analysis of insertion sort, we looked at both the best case, in which the input array was already sorted, and the worst case, in which the input array was reverse sorted. For the remainder of this book, though, we shall usually concentrate on finding only the worst-case running time, that is, the ongest running time for any input of size n. We give three reasons for this orientation. + The worst-case running time of an algorithm is an upper bound on the running time for any input. Knowing it gives us a guarantee that the algorithm will never take any longer. We need not make some educated ‘guess about the running time and hope that it never gets much worse. + For some algorithms, the worst case occurs fairly often. For example, in searching a database for a particular piece of information, the searching algorithm’s worst case will often occur when the information is not present in the database. In some searching applications, searches for absent information may be frequent. + The “average case” is often roughly as bad as the worst case. Suppose that we randomly choose n numbers and apply insertion sort. How long does it take to determine where in subarray A[1 .. j-1] to insert element ALT? On average, half the elements in A[I..j ~ 1] are less than AU], and half the elements are greater. On average, therefore, we check half of the subarray A[I..j— 1], $0 t) = j/2. If we work out the resulting average-case running time, it turns out to be a quadratic function of the input size, just like the worst-case running time.10 Chapter 1 Introduction In some particular cases, we shall be interested in the average-case ot expected running time of an algorithm. One problem with performing an average-case analysis, however, is that it may not be apparent what constitutes an “average” input for a particular problem, Often, we shall assume that all inputs of a given size are equally likely. In practice, this assumption may be violated, but a randomized algorithm can sometimes force it to hold. Order of growth, We have used some simplifying abstractions to ease our analysis of the INSERTION-SorT procedure. First, we ignored the actual cost of each state- ment, using the constants c; to represent these costs. Then, we observed that even these constants give us more detail than we really need: the worst-case running time is an? + bn +c for some constants a, b, and ¢ that depend on the statement costs c;. We thus ignored not only the actual statement costs, but also the abstract costs ci We shall now make one more simplifying abstraction. It is the rate of growth, or order of growth, of the running time that really interests us. We therefore consider only the leading term of a formula (e.g., an*), since the lower-order terms are relatively insignificant for large n. We also ignore the leading term’s constant coefficient, since constant factors are less significant than the rate of growth in determining computational efficiency for large inputs, Thus, we write that insertion sort, for example, has a worst-case running time of @(n?) (pronounced “theta of n-squared”). We shall use @-notation informally in this chapter; it will be defined precisely in Chapter 2. ‘We usually consider one algorithm to be more efficient than another if its worst-case running time has a lower order of growth. This evaluation may be in error for small inputs, but for large enough inputs a O(n?) algorithm, for example, will run more quickly in the worst case than a (n°) algorithm. Exercises 12d Consider sorting m numbers stored in array A by first finding the smallest element of A and putting it in the first entry of another array B. Then find the second smallest element of A and put it in the second entry of B. Continue in this manner for the elements of 4. Write pseudocode for this algorithm, which is known as selection sort. Give the best-case and worst-case running times of selection sort in @-notation.1.3 Designing algorithms u 12-2 Consider linear search again (see Exercise 1.1-3). How many elements of, the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in @-notation? Justify your answers. 12-3 Consider the problem of determining whether an arbitrary sequence (x1, 2¥2,..-5%n) of numbers contains repeated occurrences of some number. Show that this can be done in @(71gn) time, where Ign stands for log, n. 12-4 Consider the problem of evaluating a polynomial at a point. Given 1 coefficients do,d),...,d,-; and a real number x, we wish to compute 29 aix!. Describe a straightforward @(n?)-time algorithm for this prob- lem. Describe a ©(n)-time algorithm that uses the following method (called Horner's rule) for rewriting the polynomial: Vax! = (+ (dni + dy—a)x +21 + ay)x +a, rf 12-5 Express the function n3/1000— 100n? — 100n + 3 in terms of @-notation, 12-6 How can we modify almost any algorithm to have a good best-case running time? 1,3 Designing algorithms There are many ways to design algorithms. Insertion sort uses an incremen- tal approach: having sorted the subarray [I .. j - 1], we insert the single element A[/] into its proper place, yielding the sorted subarray A[1...j]. In this section, we examine an alternative design approach, known as “divide-and-conquer.” We shall use divide-and-conquer to design a sorting algorithm whose worst-case running time is much less than that of insertion sort. One advantage of divide-and-conquer algorithms is that their running times are often easily determined using techniques that will be introduced in Chapter 4.2 Chapter I Introduction 1.3.1, The divide-and-conquer approach Many useful algorithms are recursive in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely re- lated subproblems. These algorithms typically follow a divide-and-conquer approach: they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recur- sively, and then combine these solutions to create a solution to the original problem. The divide-and-conquer paradigm involves three steps at each level of the recursion: Divide the problem into a number of subproblems, ‘Conquer the subproblems by solving them recursively. If the subprob- lem sizes are small enough, however, just solve the subproblems in a straightforward manner. Combine the solutions to the subproblems into the solution for the original problem. The merge sort algorithm closely follows the divide-and-conquer para- digm. Intuitively, it operates as follows, Divide: Divide the n-element sequence to be sorted into two subsequences of 1/2 elements each. ‘Conquer: Sort the two subsequences recursively using merge sort. Merge the two sorted subsequences to produce the sorted an- ‘We note that the recursion “bottoms out” when the sequence to be sorted hhas length 1, in which case there is no work to be done, since every se- quence of length 1 is already in sorted order. The key operation of the merge sort algorithm is the merging of two sorted sequences in the “combine” step. To perform the merging, we use an auxiliary procedure MeRGE(4,p,q.r), where 4 is an array and p,q, and r are indices numbering elements of the array such that p r, the subarray has at most one element and is therefore already sorted. Otherwise, the divide step simply computes an index q that partitions A[p..r] into two subarrays: A[p..q], containing [n/2] elements, and Afq + 1..r], containing (n/2] elements.* Merce-Sort(4,p,7) 1 ifp I elements, we break down the running time as follows. Divide: The divide step just computes the middle of the subarray, which takes constant time. Thus, D(n) = @(1) Conquer: We recursively solve two subproblems, each of size n/2, which contributes 27(n/2) to the running time. Combine: We have already noted that the MERGE procedure on an n- element subarray takes time @(71), 50 C(n) = (7).1.3. Designing algorithms Is When we add the functions D(n) and C(n) for the merge sort analysis, we are adding a function that is @(n) and a function that is @(1). This sum isa linear function of n, that is, @(n). Adding it to the 27(n/2) term from the “conquer” step gives the recurrence for the worst-case running time T(n) of merge sort U1) ifn=1, Tin)= {Hey +O(n) ifn>t In Chapter 4, we shall show that T(n) is O(n lgn), where Ign stands for log, n. For large enough inputs, merge sort, with its @(7# lg) running time, outperforms insertion sort, whose running time is (7), in the worst case. Exercises 13-1 Using Figure 1.3 as a model, illustrate the operation of merge sort on the array A= (3,41, 52,26, 38, 57,9,49). Write pseudocode for ManoE(A, 0.4.7) 13-3 Use mathematical induction to show that the solution of the recurrence T(n) = Gren) +n the Wk>t is T(n) =nign. 13-4 Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1...1}, we recursively sort A[1..n— 1] and then insert [7] into the sorted array [1.1]. Write a recurrence for the running time of this recursive version of insertion sort. 13-5 Referring back to the searching problem (see Exercise 1.1-3), observe that if the sequence is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. Binary search is an algorithm that repeats this procedure, halving the si of the remaining portion of the sequence each time, Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is @(Ig 7). 13-6 ‘Observe that the while loop of lines 5-7 of the INsERTION-SoRT procedure in Section 1.1 uses a linear search to sean (backward) through the sorted subarray A[1..j — 1]. Can we use a binary search (see Exercise 1.3-5)16 14 Summary Chapter I Introduction instead to improve the overall worst-case running time of insertion sort to Olnign)? 13-7 & Describe a ©(11Ign)-time algorithm that, given a set S of n real numbers and another real number x, determines whether or not there exist two elements in $ whose sum is exactly x. A good algorithm is like a sharp knife—it does exactly what it is supposed to do with a minimum amount of applied effort. Using the wrong algo- rithm to solve a problem is like trying to cut a steak with a screwdriver: you may eventually get a digestible result, but you will expend consider- ably more effort than necessary, and the result is unlikely to be aesthetically pleasing. Algorithms devised to solve the same problem often differ dramatically in their efficiency. These differences can be much more significant than the difference between a personal computer and a supercomputer. As an example, let us pit a supercomputer running insertion sort against a small personal computer running merge sort. They each must sort an array of one million numbers. Suppose the supercomputer executes 100 million instructions per second, while the personal computer executes only one million instructions per second. To make the difference even more dra- matic, suppose that the world’s craftiest programmer codes insertion sort in machine language for the supercomputer, and the resulting code re- quires 2n? supercomputer instructions to sort n numbers. Merge sort, on the other hand, is programmed for the personal computer by an average programmer using a high-level language with an inefficient compiler, with the resulting code taking 50” 1gn personal computer instructions. To sort million numbers, the supercomputer takes 2+ (10°)? instructions TOF instructions/second = 20.000 seconds ~ 5.56 hours , while the personal computer takes 50 10° lg 10° instructions 10* instructions/second ~ 1,000 seconds = 16.67 minutes By using an algorithm whose running time has a lower order of growth, even with a poor compiler, the personal computer runs 20 times faster than the supercomputer! This example shows that algorithms, like computer hardware, are a tech- nology. Total system performance depends on choosing efficient algorithms ‘as much as on choosing fast hardware. Just as rapid advances are beingProblems Problems for Chapter 1 "7 made in other computer technologies, they are being made in algorithms as well, Exercises 14-1 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size m, insertion sort runs in 8n? steps, while merge sort runs in 64” 1gn steps. For which values of 1 does insertion sort beat merge sort? How might one rewrite the merge sort pseudocode to make it even faster on small inputs? 14-2 What is the smallest value of ” such that an algorithm whose running time is 100n? runs faster than an algorithm whose running time is 2" on the same machine? 1-1 Comparison of running times For each function f(n) and time 1 in the following table, determine the largest size m of a problem that can be solved in time ¢, assuming that the algorithm to solve the problem takes f(n) microseconds. 1 1 1 1 1 1 1 second | minute | hour _| day | month | year_| century Ign 1-2 Insertion sort on small arrays in merge sort Although merge sort runs in @(7t1g7) worst-case time and insertion sort runs in @(n2) worst-case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using inser18 Chapter 1 Introduction sort and then merged using the standard merging mechanism, where k is a value to be determined. 4. Show that the n/k sublists, each of length k, can be sorted by insertion sort in @(mk) worst-case time. 4. Show that the sublists can be merged in @(nlg(n/k)) worst-case time. ¢. Given that the modified algorithm runs in @(nk + mlg(n/k)) worst-case time, what is the largest asymptotic (@-notation) value of k asa function of m for which the modified algorithm has the same asymptotic running time as standard merge sort? 4, How should k be chosen in practice? 1-3 Inversions Let A[1..2] be an array of n distinct numbers. If i ALi), then the pair (i, j) is called an inversion of A. 4@, List the five inversions of the array (2,3,8, 6,1) 4, What array with elements from the set {1, sions? How many does it have? +7} has the most inver- ¢. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer. Give an algorithm that determines the number of inversions in any permutation on n elements in @(71 Ign) worst-case time. (Hint: Modify merge sort.) Chapter notes There are many excellent texts on the general topic of algorithms, including those by Aho, Hopcroft, and Uliman [4, 5], Baase (14], Brassard and Brat- ley [33], Horowitz and Sahni [105], Knuth (121, 122, 123], Manber [142], Mehlhorn (144, 145, 146], Purdom and Brown [164], Reingold, Nievergelt, and Deo [167], Sedgewick [175], and Wilf (201]. Some of the more prac- tical aspects of algorithm design are discussed by Bentley [24, 25} and Gonnet [90]. In 1968, Knuth published the first of three volumes with the general title The Art of Computer Programming (121, 122, 123]. The first vol- ume ushered in the modern study of computer algorithms with a focus on the analysis of running time, and the full series remains an engaging and worthwhile reference for many of the topics presented here. According to Knuth, the word “algorithm” is derived from the name “al-Khowarizmi, a ninth-century Persian mathematician.