Share E-Book

Algorithms Unlocked (Thomas H. Cormen)(Z-Library)

Author

Rating 4.0 AI initial rating

Log in to rate

Data Structures and Algorithms
Language English

For anyone who has ever wondered how computers solve problems, an engagingly written guide for nonexperts to the basics of computer algorithms. Have you ever wondered how your GPS can find the fastest way to your destination, selecting one route from seemingly countless possibilities in mere seconds? How your credit card account number is protected when you make a purchase over the Internet? The answer is algorithms. And how do these mathematical formulations translate themselves into your GPS, your laptop, or your smart phone? This book offers an engagingly written guide to the basics of computer algorithms. In Algorithms Unlocked, Thomas Cormen—coauthor of the leading college textbook on the subject—provides a general explanation, with limited mathematics, of how algorithms enable computers to solve problems. Readers will learn what computer algorithms are, how to describe them, and how to evaluate them. They will discover simple ways to search for information in a computer; methods for rearranging information in a computer into a prescribed order (“sorting”); how to solve basic problems that can be modeled in a computer with a mathematical structure called a “graph” (useful for modeling road networks, dependencies among tasks, and financial relationships); how to solve problems that ask questions about strings of characters such as DNA structures; the basic principles behind cryptography; fundamentals of data compression; and even that there are some problems that no one has figured out how to solve on a computer in a reasonable amount of time.

Format PDF
Size 2.5 MB
(First 20 pages)

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

Page 1
(This page has no text content)
Page 2
Algorithms Unlocked
Page 3
(This page has no text content)
Page 4
Algorithms Unlocked Thomas H. Cormen The MIT Press Cambridge, Massachusetts London, England
Page 5
c 2013 Massachusetts Institute of Technology All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher. MIT Press books may be purchased at special quantity discounts for business or sales promotional use. For information, please email special sales@mitpress.mit.edu or write to Special Sales Department, The MIT Press, 55 Hayward Street, Cambridge, MA 02142. This book was set in Times Roman and Mathtime Pro 2 by the author and was printed and bound in the United States of America. Library of Congress Cataloging-in-Publication Data Cormen, Thomas H. Algorithms Unlocked / Thomas H. Cormen. p. cm Includes bibliographical references and index. ISBN 978-0-262-51880-2 (pbk. : alk. paper) 1. Computer algorithms. I. Title. QA76.9.A43C685 2013 005.1—dc23 2012036810 10 9 8 7 6 5 4 3 2 1
Page 6
Contents Preface ix 1 What Are Algorithms and Why Should You Care? 1 Correctness 2 Resource usage 4 Computer algorithms for non-computer people 6 Computer algorithms for computer people 6 Further reading 8 2 How to Describe and Evaluate Computer Algorithms 10 How to describe computer algorithms 10 How to characterize running times 17 Loop invariants 21 Recursion 22 Further reading 24 3 Algorithms for Sorting and Searching 25 Binary search 28 Selection sort 32 Insertion sort 35 Merge sort 40 Quicksort 49 Recap 57 Further reading 59 4 A Lower Bound for Sorting and How to Beat It 60 Rules for sorting 60 The lower bound on comparison sorting 61 Beating the lower bound with counting sort 62 Radix sort 68 Further reading 70
Page 7
vi Contents 5 Directed Acyclic Graphs 71 Directed acyclic graphs 74 Topological sorting 75 How to represent a directed graph 78 Running time of topological sorting 80 Critical path in a PERT chart 80 Shortest path in a directed acyclic graph 85 Further reading 89 6 Shortest Paths 90 Dijkstra’s algorithm 92 The Bellman-Ford algorithm 101 The Floyd-Warshall algorithm 106 Further reading 114 7 Algorithms on Strings 115 Longest common subsequence 115 Transforming one string to another 121 String matching 129 Further reading 136 8 Foundations of Cryptography 138 Simple substitution ciphers 139 Symmetric-key cryptography 140 Public-key cryptography 144 The RSA cryptosystem 146 Hybrid cryptosystems 155 Computing random numbers 156 Further reading 157 9 Data Compression 158 Huffman codes 160 Fax machines 167 LZW compression 168 Further reading 178
Page 8
Contents vii 10 Hard? Problems 179 Brown trucks 179 The classes P and NP and NP-completeness 183 Decision problems and reductions 185 A Mother Problem 188 A sampler of NP-complete problems 190 General strategies 205 Perspective 208 Undecidable problems 210 Wrap-up 211 Further reading 212 Bibliography 213 Index 215
Page 9
In loving memory of my mother, Renee Cormen.
Page 10
Preface How do computers solve problems? How can your little GPS find, out of the gazillions of possible routes, the fastest way to your destination, and do so in mere seconds? When you purchase something on the Internet, how is your credit-card number protected from someone who intercepts it? The answer to these, and a ton of other questions, is algorithms. I wrote this book to unlock the mystery of algorithms for you. I coauthored the textbook Introduction to Algorithms. It’s a wonder- ful book (of course, I’m biased), but it gets pretty technical in spots. This book is not Introduction to Algorithms. It’s not even a textbook. It goes neither broadly nor deeply into the field of computer algorithms, it doesn’t prescriptively teach techniques for designing computer algo- rithms, and it contains nary a problem or exercise for the reader to solve. So just what is this book? It’s a place for you to start, if you’re interested in how computers solve problems, you want to know how to evaluate the quality of these solutions, you’d like to see how problems in computing and approaches to solv- ing them relate to the non-computer world, you can handle a little mathematics, and you have not necessarily ever written a computer program (though it doesn’t hurt to have programmed). Some books about computer algorithms are conceptual, with little technical detail. Some are chock full of technical precision. Some are in between. Each type of book has its place. I’d place this book in the in-between category. Yes, it has some math, and it gets rather precise in some places, but I’ve avoided getting deep into details (except perhaps toward the end of the book, where I just couldn’t control myself). I think of this book as a bit like an antipasto. Suppose you go to an Italian restaurant and order an antipasto, holding off on deciding whether to order the rest of the meal until you’ve had the antipasto. It arrives, and you eat it. Maybe you don’t like the antipasto, and you decide to not order anything else. Maybe you like it, but it fills you up,
Page 11
x Preface so that you don’t need to order anything else. Or maybe you like the antipasto, it does not fill you up, and you’re looking forward to the rest of the meal. Thinking of this book as the antipasto, I’m hoping for one of the latter two outcomes: either you read this book, you’re satisfied, and you feel no need to delve deeper into the world of algorithms; or you like what you read here so much that you want to learn more. Each chapter ends with a section titled “Further reading,” which will guide you to books and articles that go deeper into the topics. What will you learn from this book? I can’t tell you what you will learn from this book. Here’s what I intend for you to learn from this book: What computer algorithms are, one way to describe them, and how to evaluate them. Simple ways to search for information in a computer. Methods to rearrange information in a computer so that it’s in a pre- scribed order. (We call this task “sorting.”) How to solve basic problems that we can model in a computer with a mathematical structure known as a “graph.” Among many applica- tions, graphs are great for modeling road networks (which intersec- tions have direct roads to which other intersections, and how long are these roads?), dependencies among tasks (which task must precede which other tasks?), financial relationships (what are the exchange rates among all world currencies?), or interactions among people (who knows whom? who hates whom? which actor appeared in a movie with which other actor?). How to solve problems that ask questions about strings of textual characters. Some of these problems have applications in areas such as biology, where the characters represent base molecules and the strings of characters represent DNA structure. The basic principles behind cryptography. Even if you have never encrypted a message yourself, your computer probably has (such as when you purchase goods online). Fundamental ideas of data compression, going well beyond “f u cn rd ths u cn gt a gd jb n gd pay.”
Page 12
Preface xi That some problems are hard to solve on a computer in any reason- able amount of time, or at least that nobody has ever figured out how to do so. What do you already need to know to understand the material in this book? As I said earlier, there’s some math in this book. If math scares you, then you can try skipping over it, or you can try a less technical book. But I’ve done my best to make the math accessible. I don’t assume that you’ve ever written or even read a computer pro- gram. If you can follow instructions in outline format, you should be able to understand how I express the steps that, together, form an al- gorithm. If you get the following joke, you’re already part of the way there: Did you hear about the computer scientist who got stuck in the shower? He1 was washing his hair and following the instructions on the shampoo bottle. They read “Lather. Rinse. Repeat.” I’ve used a fairly informal writing style in this book, hoping that a personal approach will help make the material accessible. Some chap- ters depend on material in previous chapters, but such dependencies are few. Some chapters start off in a nontechnical manner and become pro- gressively more technical. Even if you find that you’re getting in over your head in one chapter, you can probably benefit from reading at least the beginning of the next chapter. Reporting errors If you find an error in this book, please let me know about it by sending email to unlocked@mit.edu. Acknowledgments Much of the material in this book draws from Introduction to Algo- rithms, and so I owe a great deal to my coauthors on that book, Charles Leiserson, Ron Rivest, and Cliff Stein. You’ll find that throughout this 1Or she. Given the unfortunate gender ratio in computer science, chances are it was he.
Page 13
xii Preface book, I shamelessly refer to (read: plug) Introduction to Algorithms, known far and wide by the initials CLRS of the four authors. Writing this book on my own makes me realize how much I miss collaborat- ing with Charles, Ron, and Cliff. I also transitively thank everyone we thanked in the preface of CLRS. I also drew on material from courses that I’ve taught at Dartmouth, especially Computer Science 1, 5, and 25. Thanks to my students for letting me know, by their insightful questions, which pedagogical ap- proaches worked and, by their stony silence, which did not. This book came to be at the suggestion of Ada Brunstein, who was our editor at the MIT Press when we prepared the third edition of CLRS. Ada has since moved on, and Jim DeWolf took her place. Originally, this book was slated to be part of the MIT Press “Essential Knowledge” series, but the MIT Press deemed it too technical for the series. (Imagine that—I wrote a book too technical for MIT!) Jim handled this poten- tially awkward situation smoothly, allowing me to write the book that I wanted to write rather than the book that the MIT Press originally thought I was writing. I also appreciate the support of Ellen Faran and Gita Devi Manaktala of the MIT Press. Julie Sussman, P.P.A., was our technical copyeditor for the second and third editions of CLRS, and I am once again thrilled to have her copyedit this book. Best. Technical. Copyeditor. Ever. She let me get away with nothing. Here’s evidence, in the form of part of an email that Julie sent me about an early draft of Chapter 5: Dear Mr. Cormen, Authorities have apprehended an escaped chapter, which has been found hiding in your book. We are unable to determine what book it has escaped from, but we cannot imagine how it could have been lodging in your book for these many months without your knowledge, so we have no option but to hold you responsible. We hope that you will take on the task of reforming this chapter and will give it an opportunity to become a produc- tive citizen of your book. A report from the arresting officer, Julie Sussman, is appended. In case you’re wondering what “P.P.A.” stands for, the first two letters are for “Professional Pain.” You can probably guess what the “A” stands for, but I want to point out that Julie takes pride in this title, and rightly so. Thanks a googol, Julie!
Page 14
Preface xiii I am no cryptographer, and the chapter on principles of cryptogra- phy benefited tremendously from comments and suggestions by Ron Rivest, Sean Smith, Rachel Miller, and Huijia Rachel Lin. That chapter has a footnote on baseball signs, and I thank Bob Whalen, the base- ball coach at Dartmouth, for patiently explaining to me some of the signing systems in baseball. Ilana Arbisser verified that computational biologists align DNA sequences in the way that I explain in Chapter 7. Jim DeWolf and I went through several iterations of titles for this book, but it was an undergraduate student at Dartmouth, Chander Ramesh, who came up with Algorithms Unlocked. The Dartmouth College Department of Computer Science is an awe- some place to work. My colleagues are brilliant and collegial, and our professional staff is second to none. If you’re looking for a computer science program at the undergraduate or graduate level, or if you seek a faculty position in computer science, I encourage you to apply to Dart- mouth. Finally, I thank my wife, Nicole Cormen; my parents, Renee and Perry Cormen; my sister, Jane Maslin; and Nicole’s parents, Colette and Paul Sage, for their love and support. My father is sure that the figure on page 2 is a 5, not an S. TOM CORMEN Hanover, New Hampshire November 2012
Page 15
(This page has no text content)
Page 16
1 What Are Algorithms and Why Should You Care? Let’s start with the question that I’m often asked: “What is an algo- rithm?”1 A broad answer would be “a set of steps to accomplish a task.” You have algorithms that you run in your everyday life. You have an al- gorithm to brush your teeth: open the toothpaste tube, pick up your toothbrush, squeeze toothpaste onto the brush until you have applied enough to the brush, close the tube, put the brush into one quadrant of your mouth, move the brush up and down for N seconds, etc. If you have to commute to a job, you have an algorithm for your commute. And so on. But this book is about algorithms that run on computers or, more generally, computational devices. Just as algorithms that you run af- fect your everyday life, so do algorithms that run on computers. Do you use your GPS to find a route to travel? It runs what we call a “shortest-path” algorithm to find the route. Do you buy products on the Internet? Then you use (or should be using) a secure website that runs an encryption algorithm. When you buy products on the Internet, are they delivered by a private delivery service? It uses algorithms to assign packages to individual trucks and then to determine the order in which each driver should deliver packages. Algorithms run on comput- ers all over the place—on your laptop, on servers, on your smartphone, on embedded systems (such as in your car, your microwave oven, or climate-control systems)—everywhere! What distinguishes an algorithm that runs on a computer from an algorithm that you run? You might be able to tolerate it when an algo- rithm is imprecisely described, but a computer cannot. For example, if you drive to work, your drive-to-work algorithm might say “if traffic is bad, take an alternate route.” Although you might know what you mean by “bad traffic,” a computer does not. So a computer algorithm is a set of steps to accomplish a task that is described precisely enough that a computer can run it. If you have 1Or, as a fellow with whom I used to play hockey would ask, “What’s a nalgorithm?”
Page 17
2 Chapter 1: What Are Algorithms and Why Should You Care? done even a little computer programming in Java, C, C++, Python, For- tran, Matlab, or the like, then you have some idea of what that level of precision means. If you have never written a computer program, then perhaps you will get a feel for that level of precision from seeing how I describe algorithms in this book. Let’s go to the next question: “What do we want from a computer algo- rithm?” Computer algorithms solve computational problems. We want two things from a computer algorithm: given an input to a problem, it should always produce a correct solution to the problem, and it should use com- putational resources efficiently while doing so. Let’s examine these two desiderata in turn. Correctness What does it mean to produce a correct solution to a problem? We can usually specify precisely what a correct solution would entail. For ex- ample, if your GPS produces a correct solution to finding the best route to travel, it might be the route, out of all possible routes from where you are to your desired destination, that will get you there soonest. Or perhaps the route that has the shortest possible distance. Or the route that will get you there soonest but also avoids tolls. Of course, the in- formation that your GPS uses to determine a route might not match re- ality. Unless your GPS can access real-time traffic information, it might assume that the time to traverse a road equals the road’s distance di- vided by the road’s speed limit. If the road is congested, however, the GPS might give you bad advice if you’re looking for the fastest route. We can still say that the routing algorithm that the GPS runs is correct, however, even if the input to the algorithm is not; for the input given to the routing algorithm, the algorithm produces the fastest route. Now, for some problems, it might be difficult or even impossible to say whether an algorithm produces a correct solution. Take optical char- acter recognition for example. Is this 11 6 pixel image a 5 or an S? Some people might call it a 5, whereas others might call it an S, so how could we declare that a computer’s decision is either correct or incor-
Page 18
Chapter 1: What Are Algorithms and Why Should You Care? 3 rect? We won’t. In this book, we will focus on computer algorithms that have knowable solutions. Sometimes, however, we can accept that a computer algorithm might produce an incorrect answer, as long as we can control how often it does so. Encryption provides a good example. The commonly used RSA cryptosystem relies on determining whether large num- bers—really large, as in hundreds of digits long—are prime. If you have ever written a computer program, you could probably write one that determines whether a number n is prime. It would test all candidate divisors from 2 through n 1, and if any of these candidates is indeed a divisor of n, then n is composite. If no number between 2 and n 1 is a divisor of n, then n is prime. But if n is hundreds of digits long, that’s a lot of candidate divisors, more than even a really fast computer could check in any reasonable amount of time. Of course, you could make some optimizations, such as eliminating all even candidates once you find that 2 is not a divisor, or stopping once you get to p n (since if d is greater than p n and d is a divisor of n, then n=d is less than p n and is also a divisor of n; therefore, if n has a divisor, you will find it by the time you get to p n). If n is hundreds of digits long, then although p n has only about half as many digits as n does, it’s still a really large number. The good news is that we know of an algorithm that tests quickly whether a number is prime. The bad news is that it can make errors. In particular, if it declares that n is composite, then n is definitely composite, but if it declares that n is prime, then there’s a chance that n is actually composite. But the bad news is not all that bad: we can control the error rate to be really low, such as one error in every 250 times. That’s rare enough—one error in about every million billion times—for most of us to be comfortable with using this method to determine whether a number is prime for RSA. Correctness is a tricky issue with another class of algorithms, called approximation algorithms. Approximation algorithms apply to opti- mization problems, in which we want to find the best solution according to some quantitative measure. Finding the fastest route, as a GPS does, is one example, where the quantitative measure is travel time. For some problems, we have no algorithm that finds an optimal solution in any reasonable amount of time, but we know of an approximation algorithm that, in a reasonable amount of time, can find a solution that is almost optimal. By “almost optimal,” we typically mean that the quantitative measure of the solution found by the approximation algorithm is within
Page 19
4 Chapter 1: What Are Algorithms and Why Should You Care? some known factor of the optimal solution’s quantitative measure. As long as we specify what the desired factor is, we can say that a correct solution from an approximation algorithm is any solution that is within that factor of the optimal solution. Resource usage What does it mean for an algorithm to use computational resources ef- ficiently? We alluded to one measure of efficiency in the discussion of approximation algorithms: time. An algorithm that gives a correct solution but takes a long time to produce that correct solution might be of little or no value. If your GPS took an hour to determine which driving route it recommends, would you even bother to turn it on? In- deed, time is the primary measure of efficiency that we use to evalu- ate an algorithm, once we have shown that the algorithm gives a cor- rect solution. But it is not the only measure. We might be concerned with how much computer memory the algorithm requires (its “memory footprint”), since an algorithm has to run within the available memory. Other possible resources that an algorithm might use: network commu- nication, random bits (because algorithms that make random choices need a source of random numbers), or disk operations (for algorithms that are designed to work with disk-resident data). In this book, as in most of the algorithms literature, we will focus on just one resource: time. How do we judge the time required by an algorithm? Unlike correctness, which does not depend on the particular computer that the algorithm runs on, the actual running time of an al- gorithm depends on several factors extrinsic to the algorithm itself: the speed of the computer, the programming language in which the algo- rithm is implemented, the compiler or interpreter that translates the pro- gram into code that runs on the computer, the skill of the programmer who writes the program, and other activity taking place on the computer concurrently with the running program. And that all assumes that the algorithm runs on just one computer with all its data in memory. If we were to evaluate the speed of an algorithm by implementing it in a real programming language, running it on a particular computer with a given input, and measuring the time the algorithm takes, we would know nothing about how fast the algorithm ran on an input of a different size, or possibly even on a different input of the same size. And if we wanted to compare the relative speed of the algorithm with some other algorithm for the same problem, we would have to implement them both
Page 20
Chapter 1: What Are Algorithms and Why Should You Care? 5 and run both of them on various inputs of various sizes. How, then, can we evaluate an algorithm’s speed? The answer is that we do so by a combination of two ideas. First, we determine how long the algorithm takes as a function of the size of its input. In our route-finding example, the input would be some representation of a roadmap, and its size would depend on the number of intersections and the number of roads connecting intersections in the map. (The physical size of the road network would not matter, since we can characterize all distances by numbers and all numbers occupy the same size in the input; the length of a road has no bearing on the input size.) In a simpler example, searching a given list of items to determine whether a particular item is present in the list, the size of the input would be the number of items in the list. Second, we focus on how fast the function that characterizes the run- ning time grows with the input size—the rate of growth of the running time. In Chapter 2, we’ll see the notations that we use to characterize an algorithm’s running time, but what’s most interesting about our ap- proach is that we look at only the dominant term in the running time, and we don’t consider coefficients. That is, we focus on the order of growth of the running time. For example, suppose we could determine that a specific implementation of a particular algorithm to search a list of n items takes 50n C 125 machine cycles. The 50n term dominates the 125 term once n gets large enough, starting at n 3 and increas- ing in dominance for even larger list sizes. Thus, we don’t consider the low-order term 125 when we describe the running time of this hy- pothetical algorithm. What might surprise you is that we also drop the coefficient 50, thereby characterizing the running time as growing lin- early with the input size n. As another example, if an algorithm took 20n3 C 100n2 C 300n C 200 machine cycles, we would say that its running time grows as n3. Again, the low-order terms—100n2, 300n, and 200—become less and less significant as the input size n increases. In practice, the coefficients that we ignore do matter. But they de- pend so heavily on the extrinsic factors that it’s entirely possible that if we were comparing two algorithms, A and B, that have the same order of growth and are run on the same input, then A might run faster than B with a particular combination of machine, programming language, com- piler/interpreter, and programmer, while B runs faster than A with some other combination. Of course, if algorithms A and B both produce cor- rect solutions and A always runs twice as fast as B, then, all other things
The above is a preview of the first 20 pages. Register to read the complete e-book.

Recommended for You

Loading recommended books...
Failed to load, please try again later

Tip the Site

Scan the WeChat Pay or Alipay code to tip. No login required.

WeChat Pay
Alipay
← Back to List