Algorithms Unlocked

by Thomas H. Cormen

Overview

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.

Product Details

ISBN-13:	9780262518802
Publisher:	MIT Press
Publication date:	03/01/2013
Series:	The MIT Press
Edition description:	New Edition
Pages:	236
Product dimensions:	5.90(w) x 8.90(h) x 0.70(d)
Age Range:	18 Years

About the Author

Thomas H. Cormen is Professor of Computer Science and former Director of the Institute for Writing and Rhetoric at Dartmouth College. He is the coauthor (with Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein) of the leading textbook on computer algorithms, Introduction to Algorithms (third edition, MIT Press, 2009).

Table of 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

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

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

What People are Saying About This

Frank Dehne

Algorithms are at the center of computer science. This is a unique book in its attempt to open the field of algorithms to a wider audience. It provides an easy-to-read introduction to an abstract topic, without sacrificing depth. This is an important contribution and there is nobody more qualified than Thomas Cormen to bridge the knowledge gap between algorithms experts and the general public.

Phil Klein

Thomas Cormen has written an engaging and readable survey of basic algorithms. The enterprising reader with some exposure to elementary computer programming will discover insights into the key algorithmic techniques that underlie efficient computation.

G. Ayorkor Korsah

Thomas Cormen helps readers to achieve a broad understanding of the key algorithms underlying much of computer science. For computer science students and practitioners, it is a great review of key algorithms that every computer scientist must understand. For non-practitioners, it truly unlocks the world of algorithms at the heart of the tools we use every day.

Endorsement

Thomas Cormen helps readers to achieve a broad understanding of the key algorithms underlying much of computer science. For computer science students and practitioners, it is a great review of key algorithms that every computer scientist must understand. For non-practitioners, it truly unlocks the world of algorithms at the heart of the tools we use every day.

—G. Ayorkor Korsah, Computer Science Department, Ashesi University College

From the Publisher

Algorithms are at the center of computer science. This is a unique book in its attempt to open the field of algorithms to a wider audience. It provides an easy-to-read introduction to an abstract topic, without sacrificing depth. This is an important contribution and there is nobody more qualified than Thomas Cormen to bridge the knowledge gap between algorithms experts and the general public.

—Frank Dehne, Chancellor's Professor of Computer Science, Carleton University

Thomas Cormen has written an engaging and readable survey of basic algorithms. The enterprising reader with some exposure to elementary computer programming will discover insights into the key algorithmic techniques that underlie efficient computation.

—Phil Klein, Professor, Department of Computer Science, Brown University

Thomas Cormen helps readers to achieve a broad understanding of the key algorithms underlying much of computer science. For computer science students and practitioners, it is a great review of key algorithms that every computer scientist must understand. For non-practitioners, it truly unlocks the world of algorithms at the heart of the tools we use every day.

—G. Ayorkor Korsah, Computer Science Department, Ashesi University College