Algorithms Unplugged (eBook)

Preface 4
Contents 6
Part I Searching and Sorting 10
Overview 11
1 Binary Search 13
Sequential Search 14
Binary Search 14
Recursive Implementation 15
Number of Search Steps 16
Guessing Games 17
Further Reading 19
2 Insertion Sort 20
To Read on 23
3 Fast Sorting Algorithms 24
The Algorithms 25
Detailed Explanations About These Sorting Algorithms 26
Experimental Comparison of the Sorting Algorithms 27
Determining the Runtimes Theoretically 28
Implementation in Java 30
Further Reading and Experiments 32
4 Parallel Sorting - The Need for Speed 33
Sorting in Hardware: Comparators and Sorting Circuits 34
The Bitonic Sorting Circuit: Its Architecture 35
The Bitonic Sorting Circuit: Its Correctness and Running Time 37
Concluding Remarks 42
Further Reading 42
5 Topological Sorting - How Should I Begin to Complete My To Do List? 44
Further Applications 50
Additional Reading 50
6 Searching Texts - But Fast! The Boyer-Moore-Horspool Algorithm 51
The Naive Algorithm 51
The Boyer-Moore-Horspool Algorithm 55
Further Reading 59
7 Depth-First Search (Ariadne& Co.)
Algorithmic Idea and Implementation 61
Applications 64
Example: Web Search 65
Example: Labyrinth Creation 67
Example: Television Shows 67
Example: Traffic Planning 69
Breadth-First Search 70
Further Reading 72
Acknowledgement 72
8 Pledge's Algorithm 73
Further Reading 78
Acknowledgement 79
9 Cycles in Graphs 80
Scenario 1 80
Scenario 2 81
Finding Cycles by Depth-First Search 82
Strongly Connected Components 85
Searching for Cycles with Breadth-First Search 88
Historical Notes 90
References 91
Acknowledgement 91
10 PageRank - What Is Really Relevant in the World-Wide Web? 92
Tourist Trails 93
Trails on the Web 94
Solutions 96
Conclusion 98
Further Reading 99
Part II Arithmetic and Encryption 100
Overview 101
11 Multiplication of Long Integers - Faster than Long Multiplication 103
The Addition of Long Numbers 104
Short Multiplication: A Number Times a Digit 104
The Analysis of Long Multiplication 105
Karatsuba's Method 106
Karatsuba's Method for 4-Digit Numbers 108
Karatsuba's Method for Numbers of Any Length 109
Summary 110
Further Reading 111
Acknowledgements 111
12 The Euclidean Algorithm 112
The Greatest Common Divisor 114
An Observation That Speeds up the Algorithm 115
Analysis 116
An Example 117
Further Reading 117
Acknowledgement 118
13 The Sieve of Eratosthenes - How Fast Can We Compute a Prime Number Table? 119
From the Idea to a Method 120
A Simple Idea 120
How Fast Is the Computation? 121
How Does the Algorithm Spend Its Time? 122
Do We Need Every i Value? 123
Can We Get Even Faster? 125
What Can We Learn from This Example? 127
Further Considerations 127
Further Reading 129
14 One-Way Functions. Mind the Trap - Escape Only for the Initiated 131
The Mirror Image of Multiplication: Factorization 131
One-Way Functions 133
A Practical Problem: Searching a Telephone Book 135
Security and Googles 138
Further Reading 138
15 The One-Time Pad Algorithm - The Simplest and Most Secure Way to Keep Secrets 140
Encrypting Messages 141
The Algorithm 143
Breaking the Code 144
Further Reading 145
16 Public-Key Cryptography 146
Public Keys 147
A Limited Algebra 148
Construction of the Keys 148
Encryption 149
Decryption 151
The Eavesdropper 151
Without Limited Mathematics 152
ElGamal's Method 152
Modular Multiplication and Modular Exponentiation 153
Description of ElGamal's Cryptosystem 155
Further Methods 156
Security 156
Further Reading 157
17 How to Share a Secret 158
A Simple Method to Share a Secret 159
General Secret Sharing 163
Secret Sharing, Information Theory and Cryptography 164
Further Reading 166
18 Playing Poker by Email 168
Dealing Cards by Snail Mail 168
How to Shuffle and Distribute the Cards 168
How to Bid 170
How to Replace Cards 170
The Showdown 171
How to Verify That No One Has Cheated 172
Discussion 172
Dealing Cards by Email 172
Electronic Envelopes 172
How to Shuffle the Cards and Distribute Them to Bob 173
One-Way Functions 173
How to Replace Cards 174
A Mathematical Description 175
Distribution of Cards to Both Players 175
Commitment to the Selected Coding Tables 176
Putting Cards into Envelopes 176
Distributing Cards to Alice 177
Distributing Cards to Bob 177
Dropping Cards 177
Properties of the Electronic Envelopes 177
How to Check Whether the Opponent Has Cheated 178
Poker with More than Two Players 178
Further Reading 178
19 Fingerprinting 180
How to Compare Long Texts over the Telephone 180
Texts as Sequences of Numbers and Modular Arithmetic 181
Fingerprints 183
Fingerprints with Random Numbers 185
The Protocol 188
Summary 190
Remarks on the Fingerprinting Theorem 190
Further Reading 192
Acknowledgement 192
20 Hashing 193
Message Digest 194
Secure Hashing 195
Hashing for Dictionaries 196
Storing a Data Item z with Key x 197
Searching a Data Item Corresponding to Key x 198
External Links and References 199
21 Codes - Protecting Data Against Errors and Loss 200
Introduction 200
Where Are Codes Used? 202
Reed-Solomon Codes 203
New Coding Techniques: Low-Density Parity-Check Codes 208
Network Codes 210
Places to Start Looking for More Information 213
Acknowledgement 214
Part III Planning, Coordination and Simulation 215
Overview 216
22 Broadcasting - How Can I Quickly Disseminate Information? 218
References 224
23 Converting Numbers into English Words 225
Stepwise Development of an Algorithm 226
Splitting Numbers into Three-Digit Groups … 226
…and Generating the English Words 227
Function generateGroup 227
Function generateWeight 229
Lessons Learned 229
What to Read and Try out for Yourself 230
24 Majority - Who Gets Elected Class Rep? 232
Majority Algorithm 233
Correctness of the Majority Algorithm 236
How Many Comparisons Are Necessary? 236
Applications and Extensions 239
What Can We Learn from the Solutions to the Majority Problem? 240
Further Reading 240
25 Random Numbers - How Can We Create Randomness in Computers? 241
A Tactical Game: "Rock, Paper, Scissors" 242
Means for the Generation of Random Numbers: Modular Arithmetic 242
Examples for Modular Arithmetic 243
Illustration of Modular Arithmetic 243
An Algorithm for the Generation of Pseudorandom Numbers 244
Periodic Behavior 245
Simulation of True Random Number Generators 245
The Algorithm for Rock, Paper, Scissors 245
Monte Carlo Simulation: Determination of Areas Using "Random Rain" 248
Further Reading 250
26 Winning Strategies for a Matchstick Game 251
Learning from Small Examples 252
An Algorithm to Compute a Winning Strategy 253
The Running Time of the Algorithm 255
Extensions and Background 256
Further Reading 257
27 Scheduling of Tournaments or Sports Leagues 258
Generation of Schedules 259
Schedules with Home-Away Assignments 263
Further Reading 265
28 Eulerian Circuits 267
When Does an Eulerian Circuit Exist? 268
Finding Eulerian Circuits 269
The Algorithm 270
The House of Santa Claus 271
Of Postmen and Garbage Collectors 272
Further Reading 272
29 High-Speed Circles 274
Drawing Circles: Keep It Simple! 275
Bresenham's Algorithm for Circles 277
A Racing Duel 281
Further Reading 282
30 Gauß-Seidel Iterative Method for the Computation of Physical Problems 283
Warmup: Soccer 283
Temperature Calculation in a Rod (1D) 285
Temperature Computation on a Plate (2D) 287
Further Reading 291
31 Dynamic Programming - Evolutionary Distance 293
Mathematical Modeling 293
Calculation of the Evolutionary Distance 295
The Algorithm 296
Conclusion 298
References 299
Part IV Optimization 300
Overview 301
32 Shortest Paths 303
Dijkstra's Algorithm 305
FAQs and Further Reading 308
33 Minimum Spanning Trees (Sometimes Greed Pays Off …) 311
The Bridge Project of the Algos 312
Building Bridges After the Hurricane 313
The Algorithms of Prim and Kruskal 315
Further Reading 316
34 Maximum Flows - Towards the Stadium During Rush Hour 318
The Algorithm 320
Some Open Questions 327
Why Does It Work? 327
Epilogue 328
Solution 328
Further Reading 328
35 Marriage Broker 330
Problem 330
The Basic Principle of the Procedure 331
The Construction of a Maximum Matching 332
The Algorithm 336
The Marriage Theorem 337
Where Is the Marriage Theorem Needed by the Algorithm 338
Time Analysis 339
Further Reading 339
Acknowledgements 340
36 The Smallest Enclosing Circle - A Contribution to Democracy from Switzerland? 341
Why It Works 344
Further Reading 344
37 Online Algorithms - What Is It Worth to Know the Future? 345
The Ski Rental Problem 345
The Paging Problem 348
Further Reading 350
38 Bin Packing or "How Do I Get My Stuff into the Boxes?" 351
The Online Problem "Moving Inexpensively" 352
Analysis of the Algorithms 353
How Well Can Online Algorithms for Bin Packing Perform? 356
Further Reading 358
39 The Knapsack Problem 359
Pareto-Optimal Solutions 361
The Nemhauser-Ullmann Algorithm 363
Further Reading 365
40 The Travelling Salesman Problem 366
Introduction 366
The Brute-Force Method 367
Dynamic Programming 368
Approximative Solutions 370
MST Algorithm 371
Some Final Remarks 373
Further Reading 374
41 Simulated Annealing 375
What Is Simulated Annealing? 376
The Travelling Salesperson Problem 379
Further Applications 380
Further Reading 382
Author Details 383