Search and Find

Book Title

Author/Publisher

Table of Contents

Show eBooks for my device only:

 

Algorithms Unplugged

Algorithms Unplugged

of: Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Christian Scheideler, Heriber

Springer-Verlag, 2010

ISBN: 9783642153280 , 406 Pages

Format: PDF

Copy protection: DRM

Windows PC,Mac OSX Apple iPad, Android Tablet PC's

Price: 55,92 EUR



More of the content

Algorithms Unplugged


 

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

61

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