Algorithms Unlocked

by Cormen

ISBN: 9780262313230 | Copyright 2013

Tabs

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.

Expand/Collapse All
Contents (pg. v)
Preface (pg. ix)
1 What Are Algorithms and Why Should You Care? (pg. 1)
Correctness (pg. 2)
Resource usage (pg. 4)
Computer algorithms for non-computer people (pg. 6)
Computer algorithms for computer people (pg. 6)
Further reading (pg. 8)
2 How to Describe and Evaluate Computer Algorithms (pg. 10)
How to describe computer algorithms (pg. 10)
How to characterize running times (pg. 17)
Loop invariants (pg. 21)
Recursion (pg. 22)
Further reading (pg. 24)
3 Algorithms for Sorting and Searching (pg. 25)
Binary search (pg. 28)
Selection sort (pg. 32)
Insertion sort (pg. 35)
Merge sort (pg. 40)
Quicksort (pg. 49)
Recap (pg. 57)
Further reading (pg. 59)
4 A Lower Bound for Sorting and How to Beat It (pg. 60)
Rules for sorting (pg. 60)
The lower bound on comparison sorting (pg. 61)
Beating the lower bound with counting sort (pg. 62)
Radix sort (pg. 68)
Further reading (pg. 70)
5 Directed Acyclic Graphs (pg. 71)
Directed acyclic graphs (pg. 74)
Topological sorting (pg. 75)
How to represent a directed graph (pg. 78)
Running time of topological sorting (pg. 80)
Critical path in a PERT chart (pg. 80)
Shortest path in a directed acyclic graph (pg. 85)
Further reading (pg. 89)
6 Shortest Paths (pg. 90)
Dijkstra’s algorithm (pg. 92)
The Bellman-Ford algorithm (pg. 101)
The Floyd-Warshall algorithm (pg. 106)
Further reading (pg. 114)
7 Algorithms on Strings (pg. 115)
Longest common subsequence (pg. 115)
Transforming one string to another (pg. 121)
String matching (pg. 129)
Further reading (pg. 136)
8 Foundations of Cryptography (pg. 138)
Simple substitution ciphers (pg. 139)
Symmetric-key cryptography (pg. 140)
Public-key cryptography (pg. 144)
The RSA cryptosystem (pg. 146)
Hybrid cryptosystems (pg. 155)
Computing random numbers (pg. 156)
Further reading (pg. 157)
9 Data Compression (pg. 158)
Huffman codes (pg. 160)
Fax machines (pg. 167)
LZW compression (pg. 168)
Further reading (pg. 178)
10 Hard? Problems (pg. 179)
Brown trucks (pg. 179)
The classes P and NP and NP-completeness (pg. 183)
Decision problems and reductions (pg. 185)
A Mother Problem (pg. 188)
A sampler of NP-complete problems (pg. 190)
General strategies (pg. 205)
Perspective (pg. 208)
Undecidable problems (pg. 210)
Wrap-up (pg. 211)
Further reading (pg. 212)
Bibliography (pg. 213)
Index (pg. 215)

Thomas H. Cormen

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).