Donald E. Knuth - The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd Edition)

ePUB is an open, industry-standard format for eBooks. However, support of ePUB and its many features varies across reading devices and applications. Use your device or app settings to customize the presentation to your liking. Settings that you can customize often include font, font size, single or double column, landscape or portrait mode, and figures that you can click or tap to enlarge. For additional information about the settings and features on your reading device or app, visit the device manufacturers Web site.

Many titles include programming code or configuration examples. To optimize the presentation of these elements, view the eBook in single-column, landscape mode and adjust the font size to the smallest setting. In addition to presenting code and configurations in the reflowable text format, we have included images of the code that mimic the presentation found in the print book; therefore, where the reflowable format may compromise the presentation of the code listing, you will see a Click here to view code image link. Click the link to view the print-fidelity code image. To return to the previous page viewed, click the Back button on your device or app.

In this eBook, the limitations of the ePUB format have caused us to render some equations as text and others as images, depending on the complexity of the equation. This can result in an odd juxtaposition in cases where the same variables appear as part of both a text presentation and an image presentation. However, the authors intent is clear and in both cases the equations are legible.

Volume 1 / Fundamental Algorithms

THIRD EDITION

DONALD E. KNUTH Stanford University

ADDISONWESLEY

Upper Saddle River, NJ Boston Indianapolis San Francisco
New York Toronto Montral London Munich Paris Madrid
Capetown Sydney Tokyo Singapore Mexico City

TeX is a trademark of the American Mathematical Society

METAFONT is a trademark of AddisonWesley

The author and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein.

The publisher offers excellent discounts on this book when ordered in quantity for bulk purposes or special sales, which may include electronic versions and/or custom covers and content particular to your business, training goals, marketing focus, and branding interests. For more information, please contact:

U.S. Corporate and Government Sales (800) 3823419

For sales outside the U.S., please contact:

International Sales

Visit us on the Web: informit.com/aw

Library of Congress Cataloging-in-Publication Data

Knuth, Donald Ervin, 1938
The art of computer programming / Donald Ervin Knuth.
xx,652 p. 24 cm.
Includes bibliographical references and index.
Contents: v. 1. Fundamental algorithms. -- v. 2. Seminumerical
algorithms. -- v. 3. Sorting and searching. -- v. 4a. Combinatorial
algorithms, part 1.
Contents: v. 1. Fundamental algorithms. -- 3rd ed.
ISBN 978-0-201-89683-1 (v. 1, 3rd ed.)
ISBN 978-0-201-89684-8 (v. 2, 3rd ed.)
ISBN 978-0-201-89685-5 (v. 3, 2nd ed.)
ISBN 978-0-201-03804-0 (v. 4a)
1. Electronic digital computers--Programming. 2. Computer
algorithms. I. Title.
QA76.6.K64 1997
005.1--DC21 97-2147

Internet page http://www-cs-faculty.stanford.edu/~knuth/taocp.html contains current information about this book and related books.

Electronic version by Mathematical Sciences Publishers (MSP), http://msp.org

Copyright 1997 by AddisonWesley

All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. For information regarding permissions, write to:

Pearson Education, Inc.
Rights and Contracts Department
501 Boylston Street, Suite 900
Boston, MA 02116 Fax: (617) 671-3447

ISBN-13 978-0-201-89683-1
ISBN-10 0-201-89683-4

First digital release, December 2013

This series of books is affectionately dedicated to the Type 650 computer once installed at Case Institute of Technology, in remembrance of many pleasant evenings.

Here is your book, the one your thousands of letters have asked us
to publish. It has taken us years to do, checking and rechecking countless
recipes to bring you only the best, only the interesting, only the perfect.
Now we can say, without a shadow of a doubt, that every single one of them,
if you follow the directions to the letter, will work for you exactly as well
as it did for us, even if you have never cooked before.

McCalls Cookbook (1963)

The process of preparing programs for a digital computer is especially attractive, not only because it can be economically and scientifically rewarding, but also because it can be an aesthetic experience much like composing poetry or music. This book is the first volume of a multi-volume set of books that has been designed to train the reader in various skills that go into a programmers craft.

The following chapters are not meant to serve as an introduction to computer programming; the reader is supposed to have had some previous experience. The prerequisites are actually very simple, but a beginner requires time and practice in order to understand the concept of a digital computer. The reader should possess:

a) Some idea of how a stored-program digital computer works; not necessarily the electronics, rather the manner in which instructions can be kept in the machines memory and successively executed.

b) An ability to put the solutions to problems into such explicit terms that a computer can understand them. (These machines have no common sense; they do exactly as they are told, no more and no less. This fact is the hardest concept to grasp when one first tries to use a computer.)

c) Some knowledge of the most elementary computer techniques, such as looping (performing a set of instructions repeatedly), the use of subroutines, and the use of indexed variables.

d) A little knowledge of common computer jargon memory, registers, bits, floating point, overflow, software. Most words not defined in the text are given brief definitions in the index at the close of each volume.

These four prerequisites can perhaps be summed up into the single requirement that the reader should have already written and tested at least, say, four programs for at least one computer.

I have tried to write this set of books in such a way that it will fill several needs. In the first place, these books are reference works that summarize the knowledge that has been acquired in several important fields. In the second place, they can be used as textbooks for self-study or for college courses in the computer and information sciences. To meet both of these objectives, I have incorporated a large number of exercises into the text and have furnished answers for most of them. I have also made an effort to fill the pages with facts rather than with vague, general commentary.

This set of books is intended for people who will be more than just casually interested in computers, yet it is by no means only for the computer specialist. Indeed, one of my main goals has been to make these programming techniques more accessible to the many people working in other fields who can make fruitful use of computers, yet who cannot afford the time to locate all of the necessary information that is buried in technical journals.