Thomas H. Cormen
Format: PDF / Kindle (mobi) / ePub
Uploader's Note: Semi-Retail version.
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.
of inner-loop iterations forms an arithmetic series: 1C2C3C C .n 2/ C .n 1/ ; which, as we saw for selection sort, is ‚.n2 /. Since each inner-loop iteration takes constant time, the worst-case running time of insertion sort is ‚.n2 /. In the worst case, therefore, selection sort and insertion sort have running times that are asymptotically the same. Would it make sense to try to understand what happens on average with insertion sort? That depends on what an “average” input looks like. If the
two-letter word sr in the ciphertext and guess that the plaintext character corresponding to the ciphertext s must be one of b , h , m , or w , since the only two-letter words in English ending in e are be , he , me , and we . You could also determine that the plaintext a corresponds to the ciphertext h , because the only singleletter lowercase word in English is a . Of course, if you’re encrypting credit-card numbers, then you don’t have to worry too much about letter frequencies or letter
and sometimes based on an “indicator” sign. The manager or coach can give an arbitrarily long series of signs to indicate any particular play, where most of the signs in the series are meaningless. 4 The name comes from its inventors, Ronald Rivest, Adi Shamir, and Leonard Adelman. Chapter 8: Foundations of Cryptography 147 ular arithmetic is like clock arithmetic, but substituting 0 for 12 on the clock face. If you go to sleep at 11 and sleep for eight hours, you wake up at 7: .11 C 8/ mod
that I wrote did.) 150 Chapter 8: Foundations of Cryptography Here are the details I have to address in order to set up and use RSA: How do I work with numbers with hundreds of digits? Although testing whether a number is prime isn’t an obstacle, how do I know that I can find large prime numbers in a reasonable amount of time? How do I find e so that e and r are relatively prime? How do I compute d so that it’s the multiplicative inverse of e, modulo r? If d is large, how do I compute x d mod
that, as m approaches infinity, the number of prime numbers less than or equal Chapter 8: Foundations of Cryptography 151 to m approaches m= ln m, where ln m is the natural logarithm of m. If I just randomly select an integer m, there’s about a 1 in ln m chance that it’s prime. Probability theory tells us that, on average, I need to try only about ln m numbers near m before I find one that is prime. If I’m looking for prime numbers p and q with 1024 bits, then m is 21024 , and ln m is