Recursion theory. Bratley, Paul. B73 51 I'. Cover design: Lundgren Graphics, Ltd. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher. What Is an Algorithm?
|Published (Last):||10 September 2009|
|PDF File Size:||10.27 Mb|
|ePub File Size:||5.4 Mb|
|Price:||Free* [*Free Regsitration Required]|
Gilles Brassard and Paul Bratley. Dopartementd'informatiqueet d e r e c h e r c h e o p g r a t i o n e l l e UniversitW de Montreal. Library of Congress Cataloging-in-PublicationData. Includes bibliographical references and index. Bratley, Paul.
Englewood Cliffs, New Jersey. The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the theories and formulas to determine their effectiveness. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these formulas.
All rights reserved. No part of this book may be reproduced, in any form or by any means, with- out permission in writing from the publisher. Printed in the United States of America. A nos parents. Mathematical induction. Problems References and further reading. Introduction Problems and instances The efficiency of algorithms Average and worst-case analyses What is an elementary operation?
Why look for efficiency? Some examples. When is an algorithm specified? References and further reading Minimizing time in the system. Scheduling with deadlines. Sorting by merging. Acyclic graphs: Topological sorting. The eight queens problem revisited Probabilistic selection and sorting Universal hashing Factorizing large integers Connected components.
Parallel evaluation of expressions. Parallel sorting networks. The zero-one principle. Parallel sorting. Distributed computation.
Introduction: A simple example. Information-theoretic a r g u m e n t s. Adversary arguments. Linear reductions. Introduction to LMP- completeness. A menagerie of complexity classes. The travelling salesperson. Bin packing revisited The knapsack problem 6. As soon as an Analytical Engine exists, it will necessarilyguide the future course of the science. Whenever any result is sought by its aid, the question will then arise-By what course ofcalculationcan these results be arrived at by the machine in the shortest time?
In August , Scientific American challenged its readers to decipher a secret mes- sage and win one hundred dollars. This sounded safe: it was estimated at the time that the fastest existing computer using the most efficient known algorithm could not earn the award until it had run without interruption for millions of times the age of the Universe. Nevertheless, eight months of computation started sixteen years later sufficed for the task.
What happened? The increase in raw computing power during those years cannot be discounted, but far more significant was the discov- ery of better algorithms to solve the problem-see Sections 7.
Additional examples of how the development of efficient algorithms have extended the frontiers of feasible computation are given in Section 2. The importance of efficient algorithms was realized well before the era of elec-. The best-known. Many mathematicians -Gauss for example-have investigated efficient algorithms for a variety of tasks throughout history.
Perhaps none was more prophetic than Charles Babbage, whose 19th century analytical engine would have been the first mechanical computer had he only succeeded in building it. His strikingly modern thought, quoted at. Our book is not a programming manual. Still less is it a "cookbook" containing. On the contrary, it deals with algorithmics: the systematic study of the design and analysis of algorithms. The aim of our book is to give readers some basic tools needed to develop their own algorithms, in whatever field of application they may be required.
We concentrate on the fundamental techniques used to design and analyse efficient algorithms. These techniques include greedy algorithms, divide-and-. Each technique is first presented in full generality. We pay. Although our approach is rigorous, we do not neglect the needs of practitioners: besides illustrating the design techniques employed, most of the algorithms presented also have real-life applications.
To profit fully from this book, you should have some previous programming experience. However, we use no particular programming language, nor are the.
This and the general, fundamental treatment. On the other hand, you should not expect to be able to use directly the algorithms we give: you will always be obliged to make the necessary effort to transcribe them into some appropriate programming language.
The use of Pascal or a similarly structured language will help reduce this effort to the minimum necessary. Our book is intended as a textbook for an undergraduate course in algorithmics. Some problems are provided to help the teacher find homework assignments. The first chapter includes most of the required mathematical preliminaries. In par-. From time to time. Our book can also be used for independent study: anyone who needs to write better, more efficient algorithms can benefit from it.
To capture the students' attention from the outset, it is particularly effective to begin the first lecture with a discussion of several algorithms for a familiar task such as integer multiplication.
James A. Foster, who used preliminary versions of this book at the University of Idaho, described his experience in the following terms:.
This led to what constitutes the size of the input, and to an analysis of the classical algorithm. I then showed multiplication a la russe, with which they were soon. We then discussed the divide-and-conquer algorithm Section 7. All of this was done informally, but at the end of the class a single lecture, mind you they.
In making a choice of subjects, the teacher should bear in mind that the first chapter can probably be assigned as independent reading, with Section 1. Most of Chapter 2 can be assigned as independent reading as well, although a one or two hour summary in class would be useful to cover notions such as problems versus instances and average versus worst-case analysis, and to motivate the importance of efficient algorithms.
Chap- ter 3, on asymptotic notation, is short but crucial; its first three sections must be understood if any benefit is to be gained from this book, and the original material on conditional asymptotic notation from Section 3.
We avoid "one-sided equalities" by using a more logical set notation. The first five s e c t i o n s o f Chapter 4, which give the basic ideas behind the analysis of algorithms, are impor- tant but rather straightforward. Section 4. Chapter 5 ends the preliminary material; it describes basic data structures essential for the design of efficient algorithms.
The first five sections cover notions such as arrays, lists and graphs: this material should be well-known already, and it can probably be assigned as independent reading. The remainder of Chapter 5 describes more sophisticated data structures such as associative ta- bles hashing , ordinary and binomial heaps, and disjoint set structures.
Ordinary heaps Section 5. The other chapters are to a great extent independent of one another.
Fundamentals of Algorithmics - Brassard, Bratley
Download instructor resources. Additional order info. For departments of computer science offering Sophomore through Junior-level courses in Algorithms or Design and Analysis of Algorithms. This is an introductory-level algorithm text. It includes worked-out examples and detailed proofs. Presents Algorithms by type rather than application.
Brassard & Bratley, Fundamentals of Algorithmics ( PDFDrive com )