Introduction to algorithms A creative approach

【实例简介】
Introduction to algorithms A creative approach udi manber 英文完整扫描版 1分吧。反正加个评论你的分就回来了。
INTRODUCTION TO ALGORITHMS a Creative approach UDI MANBER University of arizona ADDISON-WESLEY PUBLISHING COMPANY Reading, Massachusetts. Menlo Park, California. New York Don Mills, Ontario Wokingham, England. Amsterdam Bon· Sydney· Singapore· Tokyo· Madrid· San juan Library of Congress Cataloging-in-Publication Data Manber, Udi Introduction to algorithms. Includes bibliographies and index. 1. Data structures( Computer science) 2. Algorithms. I. Title. QA769D35M361989 0057388-2186 ISBN0201-12037-2 Reproduced by Addison-Wesley from camera-ready copy supplied by the author. The programs and applications presented in this book have been included for their instructional value. They have been tested with care, but are nof guaranteed for any purpose. The publisher does not offer any warranties or representation, nor does it accept any liabilities with respect to the programs or applications Reprinted with corrections October, 1989 Copyright o 1989 by Addison-Wesley Publishing Company Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical photocopying, recording, or otherwise, without prior written permission of the publisher Printed in the United States of America. Published simultaneously in Canada EFGHIJ-DO-943210 To my parents Eva and Meshulam 的的的的通 PREFACE This book grew out of my frustrations with not being able to explain algorithms clearly Like many other teachers, i discovered that not only is it hard for some students to solve (what seemed to me) simple problems by themselves, but it is aiso hard for them to understand the solutions that are given to them. i believe that these two parts m the creation and the explanation are related and should not be separated. It is essential to follow the steps leading to a solution in order to understand it fully. It is not sufficient to look at the finished product This book emphasizes the creative side of algorithm design. Its main purpose is to show the reader how to design a new algorithm. algorithms are not described in a sequence of"problem X, algorithm A, algorithm A, program P, program P, and so on Instead, the sequence usually (although not always) looks more like" problem X,the straightforward algorithm, its drawbacks, the difficulties overcoming these drawbacks. first attempts at a better algorithm (including possible wrong turns), improvements, analysis, relation to other methods and algorithms, and so on. The goal is to present a algorithm not in a way that makes it easier for a programmer to translate into a program, but rather in a way that makes it easier to understand the algorithms principles, The algorithms are thus explained through a creative process, rather than as finished products. Our goals in teaching algorithms are to show not only how to solve particular problems, but also how to solve new problems when they arise in the future, Teaching the thinking involved in designing an algorithm is as important as teaching the details of the solution To further help the thinking process involved in creating algorithms, an old-new"methodology for designing algorithms is used in this book. This methodology covers many known techniques for designing algorithms, and it also provides an elegant intuitive framework for explaining the design of algorithms in more depth. It does not, however, cover all possible ways of designing algorithms, and we do not use it exclusively, The heart of the methodology lies in an analogy between the intellectual process of proving mathematical theorems by induction and that of designing combinatorial algorithms. Although these two processes serve different purposes and achieve different types of results, they are more similar than they may appear to be. this analogy has been observed by many people. The novelty of this book is the degree to which this analogy is exploited. We show that the analogy encompasses many known algorithm-design techniques, and helps considerably in the process of algorithm creation The methodology is discussed briefly in Chapter I and is introduced more formally in Chapter 5 vi Preface Consider the following analogy. Suppose that you arrive at an unfamiliar city, rent a car, and want directions to get to your hotel. You would be quite impatient if you were told about the history of the city, its general layout, the traffic pattems, and so on. You would rather have directions of the form "go straight for two blocks, turn right, go traight for three miles, and so on. However, your outlook would change if you planned to live in that city for a long time. You could probably get around for a while with directions of the second form(if you find someone who gives you those directions), but eventually you will need to know more about the city. This book is not a source of easy directions. It does contain explanations of how to solve many particular problems, but the emphasis is on general principles and methods. As a result, the book is hallenging. It demands involvement and thinking. I believe that the extra effort is well worthwhile The design of efficient nonnumeric algorithms is becoming important in many diverse fields, including mathematics, statistics, molecular biology, and engineering. This book can serve as an introduction to algorithms and to nonnumeric computations in generaL. Many professionals, and even scientists not deeply involved with computers, believe that programming is nothing more than grungy nonintellectual work. It sometimes is. But such a belief may lead to straightforward, trivial, inefficient solutions where elegant, more efficient solutions exist. One goal of this book is to convince readers that algorithrm design is an elegant discipline, as well as an important one The book is self-contained The presentation is mostly intuitive, and technicalities are either kept to a minimum or are separated from the main discussion. In particular, implementation details are separated from the algorithm-design ideas as much as possible. There are many examples of algorithms that were designed especially to iLlustrate the principles emphasized in the book. The material in this book is not presented as something to be mastered and memorized. It is presented as a series of ideas, examples, counterexamples, modifications, improvements, and so on. Pseudo- codes for most algorithms are given following the descriptions, Numerous exercises and a discussion of further reading, with a relevant bibliography, folow each chapter. In most chapters, the exercises are divided into two classes drill exercises and creative exercises. Drill exercises are meant to test the reader's understanding of the specific examples and algorithms presented in that chapter. Creative exercises are meant to test the reader's ability to use the techniques developed in that chapter in addition to the particular algorithms, to solve new problems. Sketches of solutions to selected exercises those whose numbers are underlined) are given at the end of the book. The chapters also include a summary of the main ideas introduced The book is organized as follows. Chapters i through 4 present introductory material. Chapter 2 is an introduction to mathematical induction mathematical induction is, as we will see, very important to algorithm design. Experience with induction proofs is therefore very helpful. Unfortunately, few computer-science students get enough exposure to induction proofs. Chapter 2 may be quite difficult for some students. We suggest skipping the more difficult examples at first reading, and returning to them later. Chapter 3 is an introduction to the analysis of algorithms. It describes the process of analyzing algorithms, and gives the basic tools one needs to be able to perform ace simple analysis of the algorithms presented in the book. Chapter 4 is a brief introduction to data structures Readers who are familiar with basic data structures and who have a basic mathematical background can start directly from Chapter 5(it is always a good idea to read the introduction though). Chapter 5 presents the basic ideas behind the approach of designing algorithms through the analogy to induction proofs. It gives several examples of simple algorithms, and describes their creation. If you read only one chapter in this book, read Chapter 5 There are two basic ways to organize a book on algorithms, One way is to divide the book according to the subject of the algorithms, for example, graph algorithms, geometric algorithms. Another way is to divide the book according to design techniques Even though the emphasis of this book is on design techniques, I have chosen the former organization. Chapters 6 through 9 present algorithms in four areas: algorithms for sequences and sets (e.g, sorting, sequence comparisons, data compression, graph algorithms(e.g, spanning trees, shortest paths, matching), geometric algorithms(e.g convex hull, intersection problems), and numerical and algebraic algorithms(e. g, matrix multiplication, fast Fourier transform). I believe that this organization is clearer and easier to follow Chapter I0 is devoted to reductions. Although examples of reductions appear in earlier chapters, the subject is unique and important enough to warrant a chapter of its own. This chapter also serves as an opening act to Chapter 11, which deals with the subject of NP-completeness. This aspect of complexity theory has becorne an essential part of algorithm theory. Anyone who designs algorithms should know about NP completeness and the techniques for proving this property. Chapter 12 is an introduction to parallel algorithms. It contains several interesting algorithms under different models of parallel computation. The material in this book is more than can be covered in a one-semester course which leaves many choices for the instructor A first course in algorithm design should include parts of Chapters 3, 5, 6, 7, and 8 in some depth, although not necessarily all of them. The more advanced parts of these chapters, along with Chapters 9, 10, il, and 12, are optional for a first course, and can be used as a basis for a more advanced course. Acknowledgments First and foremost I thank my wife rachel for helping me in more ways than I can list here throughout this adventure. She was instrumental in the development of the methodology on which the book is based. She contributed suggestions, corrections, and more important than anything else- sound advice. I could not have done if without pecial thanks are due to Jan van Leeuwen for an excellent and thorough review of a large portion of this book. His detailed comments, numerous suggestions, and many corrections have improved the book enormously. I also thank Eric Bach, Darrah Chavey, Kirk Pruhs, and Sun Wu, who read parts of the manuscript and made many helpful comments, and the reviewers Guy T. Almes (Rice University ), Agnes H. Chan (Northeastern University), Dan Gusfield (University of California. Davis), David Harel (Weizmann Institute, Israel), Daniel Hirschberg (University of California, Irvine), 【实例截图】
【核心代码】