Algorithms specify the way computers process information and how they execute tasks. Many recent technological innovations and achievements rely on algorithmic ideas – they facilitate new applications in science, medicine, production, logistics, traffic, communi¬cation and entertainment. Efficient algorithms not only enable your personal computer to execute the newest generation of games with features unimaginable only a few years ago, they are also key to several recent scientific breakthroughs – for example, the sequencing of the human genome would not have been possible without the invention of new algorithmic ideas that speed up computations by several orders of magnitude. The greatest improvements in the area of algorithms rely on beautiful ideas for tackling computational tasks more efficiently. The problems solved are not restricted to arithmetic tasks in a narrow sense but often relate to exciting questions of nonmathematical flavor, such as: How can I find the exit out of a maze? How can I partition a treasure map so that the treasure can only be found if all parts of the map are recombined? How should I plan my trip to minimize cost? Solving these challenging problems requires logical reasoning, geometric and combinatorial imagination, and, last but not least, creativity – the skills needed for the design and analysis of algorithms. In this book we present some of the most beautiful algorithmic ideas in 41 articles written in colloquial, nontechnical language. Most of the articles arose out of an initiative among German-language universities to communicate the fascination of algorithms and computer science to high-school students. The book can be understood without any prior knowledge of algorithms and computing, and it will be an enlightening and fun read for students and interested adults.
Author(s): Berthold Vöcking et al. (Eds.)
Edition: 1
Publisher: Springer-Verlag
Year: 2011
Language: English
Pages: 406
City: Berlin Heidelberg
Front Matter....Pages I-X
Front Matter....Pages 1-4
Binary Search....Pages 5-11
Insertion Sort....Pages 13-16
Fast Sorting Algorithms....Pages 17-25
Parallel Sorting - The Need for Speed....Pages 27-37
Topological Sorting - How Should I Begin to Complete My To Do List?....Pages 39-45
Searching Texts - But Fast! The Boyer-Moore-Horspool Algorithm....Pages 47-56
Depth-First Search (Ariadne & Co.)....Pages 57-68
Pledge's Algorithm - How to Escape from a Dark Maze....Pages 69-75
Cycles in Graphs....Pages 77-88
PageRank - What Is Really Relevant in the World-Wide Web?....Pages 89-96
Front Matter....Pages 97-100
Multiplication of Long Integers - Faster than Long Multiplication....Pages 101-109
The Euclidean Algorithm....Pages 111-117
The Sieve of Eratosthenes - How Fast Can We Compute a Prime Number Table?....Pages 119-130
One-Way Functions - Mind the Trap - Escape Only for the Initiated....Pages 131-139
The One-Time Pad Algorithm - The Simplest and Most Secure Way to Keep Secrets....Pages 141-146
Public-Key Cryptography....Pages 147-158
How to Share a Secret....Pages 159-168
Playing Poker by Email....Pages 169-180
Fingerprinting....Pages 181-193
Hashing....Pages 195-201
Front Matter....Pages 97-100
Codes - Protecting Data Against Errors and Loss....Pages 203-217
Front Matter....Pages 219-222
Broadcasting - How Can I Quickly Disseminate Information?....Pages 223-229
Converting Numbers into English Words....Pages 231-237
Majority - Who Gets Elected Class Rep?....Pages 239-247
Random Numbers - How Can We Create Randomness in Computers?....Pages 249-258
Winning Strategies for a Matchstick Game....Pages 259-265
Scheduling of Tournaments or Sports Leagues....Pages 267-275
Eulerian Circuits....Pages 277-283
High-Speed Circles....Pages 285-293
Gauss-Seidel Iterative Method for the Computation of Physical Problems....Pages 295-304
Dynamic Programming - Evolutionary Distance....Pages 305-311
Front Matter....Pages 313-316
Shortest Paths....Pages 317-324
Minimum Spanning Trees - Sometimes Greed Pays Off....Pages 325-331
Maximum Flows - Towards the Stadium During Rush Hour....Pages 333-344
Marriage Broker....Pages 345-355
The Smallest Enclosing Circle - A Contribution to Democracy from Switzerland?....Pages 357-360
Online Algorithms - What Is It Worth to Know the Future?....Pages 361-366
Bin Packing - How Do I Get My Stuff into the Boxes....Pages 367-374
The Knapsack Problem....Pages 375-381
The Travelling Salesman Problem....Pages 383-391
Front Matter....Pages 313-316
Simulated Annealing....Pages 393-400
Back Matter....Pages 401-406
