FUNDAMENTALS OF COMPUTER ALGORITHMS COMPUTER SCIENCE PRESS FUNDAMENTALS OF COMPUTER ALGORITHMS COMPUTER SOFTWARE ENGINEERING SERIES ELLIS HOROWITZ, EDITOR University of Southern California WAYNE AMSBURY Structured BASIC and Beyond JEAN-LOUP BAER Computer Systems Architecture PETER CALINGAERT Assemblers, Compilers, and Program Translation M. S. CARBERRY, H. M. KHALIL, J. F. LEATHRUM, J. S. LEVY Foundations of Computer Science SHIMON EVEN Graph Algorithms W. FINDLAY and D. A. WATT Pascal: An Introduction to Methodical Programming, Second Edition ELLIS HOROWITZ and SARTA J SAHNI Fundamentals of Computer Algorithms ELLIS HOROWITZ and SARTAJ SAHNI Fundamentals of Data Structures ELLIS HOROWITZ and SARTAJ SAHNI Fundamentals of Data Structures in Pascal ELLIS HOROWITZ Fundamentals of Programming Languages, Second Edition ELLIS HOROWITZ, EDITOR Programming Languages: A Grand Tour TOM LOGSDON Computers and Social Controversy IRA POHL and ALAN SHAW The Nature of Computation: An Introduction to Computer Science DONALD D. SPENCER Computers in Number Theory JEFFREY D. ULLMAN Principles of Database Systems, Second Edition ~ ~-------- FUNDAMENTALS OF COMPUTER ALGORITHMS ELLIS HOROWITZ University of Southern California SARTAJ SAHNI University of Minnesota COMPUTER SCIENCE PRESS Copyright © 1978 Computer Science Press, Inc. Printed in the United States of America All rights reserved. No part of this work may be reproduced, transmitted, or stored in any form or by any means, without the prior written consent of the Publisher. Computer Science Press 1803 Research Blvd. Rockville, Maryland 20850 IO 11 12 Printing Year 89 88 87 86 This book represents a joint effort of both authors who fully col· laborated on all chapters. The names of the authors of this text have been listed in alphabetical order. This does not imply any senior-junior relationship. Dr. Sartaj Sahni was the primary author of Chapters 4, 5, 6, 8, 11, and 12 and Dr. Ellis Horowitz was the primary author of Chapters 1, 2, 9, and JO. Library of Congress Cataloging in Publication Data Horowitz, Ellis. Fundamentals of computer algorithms. (Computer software engineering series) Includes index. 1. Electronic digital computers- -Programming. 2. Algorithms I. Sahni, Sartaj, joint author. II. Title. QA76.6.H67 519.4 78·14735 ISBN 0-914894-22-6 dedicated to our wives Neeta Sahni Maryanne Horowitz PREFACE If we try to identify those contributions of computer science which will be long lasting, surely one of these will be the refinement of the concept called algorithm. Ever since man invented the idea of a machine which could per form basic mathematical operations, the study of what can be computed and how it can be done well was launched. This study, inspired by the computer, has led to the discovery of many important and clever algorithms. The discipline called computer science has embraced the study of algo rithms as its own. It is the purpose of this book to organize what is known about them in a coherent fashion so that students and practitioners can learn to devise and analyze new algorithms for themselves. But a book which contains every algorithm ever invented would be ex ceedingly large, and traditionally algorithms books have proceeded by ex amining only a small number of problem areas in depth. For each specific problem the most efficient algorithm for its solution is usually presented and analyzed. Having taught courses in this way for several years we were well aware that this approach has one major flaw. Though the student sees many fast algorithms and may master the tools of analysis, he remains un confident about how to devise good algorithms in the first place. The missing ingredient is a lack of emphasis on design techniques. A knowledge of design will certainly help one to create good algorithms, yet without the tools of analysis there is no way to determine the quality of the result. This observation that design should be taught on a par with analysis led us to a more promising line of approach: namely to organize our courses, and subsequently this book, around some fundamental strat egies of algorithm design. The number of basic design strategies is reason ably small. Moreover all of the algorithms one would typically wish to study can easily be fit into these categories; for example, mergesort and quick sort are perfect examples of the divide-and-conquer strategy while Kruskal's minimum spanning tree algorithm and Dijkstra's single source shortest path algorithm are straightforward examples of the greedy strategy. An understanding of these strategies is an essential first step towards acquiring the skills of design. vii viii Preface Though we both strongly feel that the emphasis on design as well as analysis is the appropriate way to organize the study of algorithms, a cau tionary remark is in order. First, we have not included every known design principle. One example is linear programming which is one of the most successful techniques, but is often discussed in a course of its own. Secondly, the student should be inhibited from taking a cookbook approach to algo rithm design by assuming that each algorithm must derive from only a single technique. This is not so. A major portion of this book, chapters 3 through 9, deal with the dif ferent design strategies. First each strategy is described in general terms. Typically a "program abstraction" is given which outlines the form that the computation will take if this strategy can be applied. Following this there are a succession of examples which reveal the intricacies and varieties of the general strategy. The examples are somewhat loosely ordered in terms of increasing complexity. The type of complexity may arise in several ways. Usually we begin with a problem which is very simple to understand and requires no data structures other than a one-dimensional array. For this problem it is usually obvious that the given design strategy yields a correct solution. Later examples may require a proof that an algorithm based on this design technique does work. Or, the later algorithms may require more sophisticated data structures (e.g. trees or graphs) and their analyses may be more complex. The major goal of this organization is to emphasize the arts of synthesis and analysis of algorithms. Auxiliary goals are to expose the student to good program structure and to proofs of algorithm correct ness. One of the most energetic areas of computer science research today is called computational complexity. That name denotes the study of what makes functions intrinsically difficult to compute. Two products of com putational complexity have been the development of algorithms with the lowest asymptotic computing time and facts concerning the minimum num ber of operations required to compute a given function. Many of these re sults can be found here. However our decision in writing this book was to emphasize algorithms which were not only of theoretical interest but which are practical to use. Unfortunately many of the "best" algorithms, from an asymptotic point of view, are quite hard to program and require such a great amount of overhead that their practical value is limited. We have avoided lengthy presentations of such algorithms and contented ourselves with pointing to the available literature. The algorithms presented here are written in SP ARKS, the name we have given to our ALGOL/PASCAL-like language which we first introduced in Fundamentals of Data Structures. The syntax of some statements has Preface ix been improved, but the changes are such that the meanings of all state ments is still immediately discernible. Chapter one presents the precise semantics of each statement via flowcharts and gives some drill in the art of program structuring. We hope that by studying well-written programs the student will apply these same principles to his or her own program composition. Another important aspect of this book is program testing. Though computer science still lacks an adequate formal treatment of this subject, for some algorithms we show how to devise a range of data sets which can be used for debugging and performance measurement. Also we have felt obliged to provide programs which are essentially complete in all details. Though this may complicate the presentation of the algorithms, it has as its virtue the fact that each algorithm can be quickly programmed and executed. Of course, subroutines are used to improve clarity. The material in this book does not correspond to any existing course within ACM's recommended Curriculum '68. However it does seem likely that the IEEE Computer Society will include an algorithms course within its new recommendations. As the course structure of many computer science programs is now firmly established, it has become harder to introduce new courses. Nevertheless we are confident that these subjects are of sufficient merit that many computer science educators will attempt to cover this ma terial. Thus we offer the arguments we used to get our own departments to adopt a course on The Design and Analysis of Algorithms. First and foremost, we argued that "algorithm" is a fundamental concept of com puter science and hence there should be a course devoted to its study. Sec ondly the skills of algorithm synthesis and analysis will improve both the students basic knowledge and his or her ability to comprehend more sophis ticated algorithms in later courses. Finally there now exists some important theoretical results (e.g. NP-Completeness which is discussed in Chapter 11) which deserve to be covered. We view the material presented here as ideal for a one semester or two quarter course given to juniors, seniors or graduate students. It does re quire prior experience with programming in a higher level language but everything else is self-contained. Practically speaking, it seems that a course on data structures is helpful, if only for the fact that the students have greater programming maturity. For a school on the quarter system, the first quarter might cover the basic design techniques as given in chapters 3 through 8: divide-and-conquer, the greedy method, dynamic programming, search and traversal, backtracking, and branch-and-bound. The second quarter would cover the more theoretical subjects of chapters 10 through 12: lower bound theory, NP-Completeness and approximation methods. For a semester schedule where the student has already encountered data x Preface structures and 0-notation, chapters 3 through 11 is about the right amount of material. This includes the major design strategies as mentioned above plus the fast Fourier transform, lower bound theory, and the chapter on NP-Complete problems. A slower pace more typical of undergraduates would cover chapters 1 through 7 and 11, allowing more time for an in troduction to the idea of algorithm analysis coupled with a review of the important data structuring techniques. One question we are often asked is what do you do in class. Typically we devote each period to a discussion of one, or at most two problems. For each problem we try to emphasize how the solution can be arrived at by considering a design principle and showing that it applies. Perhaps alternative strategies are investigated and discarded. A clean separation is made between how the computation will proceed and decisions about data representation when that is possible. The best case and the worst case data of the resultant algorithm is made clear. Then an analysis of the time and space requirements is done. This scenario is a bit idealized, but on the whole it is accurate. For homework there are numerous exercises at the end of each chapter. The most popular and instructive homework assignment we have found is one which requires the student to execute and time two programs using the same data sets. Since most of the algorithms in this book provide all of the implementation details they can easily be programmed in a variety of languages. The problem then reduces to devising suitable data sets and writing a main program which outputs the timing results. The timing re sults should agree with the asymptotic analysis that was done for the algo rithm. This is a nontrivial task which can be both educational and fun. Most importantly it emphasizes an aspect of this field that is often neglected, that there is an experimental side to the practice of computer science. Acknowledgments We gratefully acknowledge the help of Arnold Rosenthal who carefully read the entire manuscript. In addition, Gary Bloom and our many algo rithms students had many useful suggestions. Administrative credit goes to Martha Eul and typing assistance to Donald Aoki, Terrie Christian, Kathy Boyer and Sybil Wright. Also we thank the USC Information Sciences Institute for their computer resources and the inspiration of their program verification group including Ralph London, David Musser and Susan Gerhart.