Thomas H. Cormen [Cormen - Algorithms Unlocked

Algorithms UnlockedAlgorithms UnlockedThomas H. Cormen The MIT Press Cambridge, Massachusetts London, England 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. : alk. paper) 1. paper) 1.

Computer algorithms. I. Title. QA76.9.A43C685 2013 005.1dc23 2012036810 10 9 8 7 6 5 4 3 2 1 Contents Correctness 2 Resource usage 4 Computer algorithms for non-computer people 6 Computer algorithms for computer people 6 Further reading 8 How to describe computer algorithms 10 How to characterize running times 17 Loop invariants 21 Recursion 22 Further reading 24 Binary search 28 Selection sort 32 Insertion sort 35 Merge sort 40 Quicksort 49 Recap 57 Further reading 59 Rules for sorting 60 The lower bound on comparison sorting 61 Beating the lower bound with counting sort 62 Radix sort 68 Further reading 70viContents 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 Dijkstras algorithm 92 The Bellman-Ford algorithm 101 The Floyd-Warshall algorithm 106 Further reading 114 Longest common subsequence 115 Transforming one string to another 121 String matching 129 Further reading 136 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 Huffman codes 160 Fax machines 167 LZW compression 168 Further reading 178Contentsvii 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 In loving memory of my mother, Renee Cormen. 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. Its a wonder ful book (of course, Im biased), but it gets pretty technical in spots. This book is not Introduction to Algorithms. Its not even a textbook. It goes neither broadly nor deeply into the field of computer algorithms, it doesnt 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? Its a place for you to start, if youre interested in how computers solve problems, you want to know how to evaluate the quality of these solutions, youd 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 doesnt 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. Id place this book in the in-between category. Yes, it has some math, and it gets rather precise in some places, but Ive avoided getting deep into details (except perhaps toward the end of the book, where I just couldnt 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 youve had the antipasto. It arrives, and you eat it. Maybe you dont like the antipasto, and you decide to not order anything else. Maybe you like it, but it fills you up, xPreface so that you dont need to order anything else. Or maybe you like the antipasto, it does not fill you up, and youre looking forward to the rest of the meal.

Thinking of this book as the antipasto, Im hoping for one of the latter two outcomes: either you read this book, youre 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 cant tell you what you will learn from this book. Heres 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. (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. (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). Prefacexi 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.