Algorithms Unplugged 1st edition by Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger 9783642153280 3642153283
Original price was: $50.00.$35.00Current price is: $35.00.
Authors:Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Christian Scheideler, Heribert Vollmer, Dorothea Wagner , Author sort:Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Christian Scheideler, Heribert Vollmer, Dorothea Wagner , Languages:Languages:eng
Algorithms Unplugged 1st edition by Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger- Ebook PDF Instant Download/Delivery.9783642153280, 3642153283
Full download Algorithms Unplugged 1st edition after payment
Product details:
ISBN 10: 3642153283
ISBN 13: 9783642153280
Author: Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Christian Scheideler, Heribert Vollmer
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 amaze? 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.
Algorithms Unplugged 1st Table of contents:
Part I Searching and Sorting
Overview
1 Binary Search
Sequential Search
Binary Search
Recursive Implementation
Number of Search Steps
Guessing Games
Further Reading
2 Insertion Sort
To Read on
3 Fast Sorting Algorithms
The Algorithms
Detailed Explanations About These Sorting Algorithms
Experimental Comparison of the Sorting Algorithms
Determining the Runtimes Theoretically
Implementation in Java
Further Reading and Experiments
4 Parallel Sorting – The Need for Speed
Sorting in Hardware: Comparators and Sorting Circuits
The Bitonic Sorting Circuit: Its Architecture
The Bitonic Sorting Circuit: Its Correctness and Running Time
Concluding Remarks
Further Reading
5 Topological Sorting – How Should I Begin to Complete My To Do List?
Further Applications
Additional Reading
6 Searching Texts – But Fast! The Boyer-Moore-Horspool Algorithm
The Naive Algorithm
The Boyer-Moore-Horspool Algorithm
Further Reading
7 Depth-First Search (Ariadne&Co.)
Algorithmic Idea and Implementation
Applications
Example: Web Search
Example: Labyrinth Creation
Example: Television Shows
Example: Traffic Planning
Breadth-First Search
Further Reading
Acknowledgement
8 Pledge’s Algorithm
Further Reading
Acknowledgement
9 Cycles in Graphs
Scenario 1
Scenario 2
Finding Cycles by Depth-First Search
Strongly Connected Components
Searching for Cycles with Breadth-First Search
Historical Notes
References
Acknowledgement
10 PageRank – What Is Really Relevant in the World-Wide Web?
Tourist Trails
Trails on the Web
Solutions
Conclusion
Further Reading
Part II Arithmetic and Encryption
Overview
11 Multiplication of Long Integers – Faster than Long Multiplication
The Addition of Long Numbers
Short Multiplication: A Number Times a Digit
The Analysis of Long Multiplication
Karatsuba’s Method
Karatsuba’s Method for 4-Digit Numbers
Karatsuba’s Method for Numbers of Any Length
Summary
Further Reading
Acknowledgements
12 The Euclidean Algorithm
The Greatest Common Divisor
An Observation That Speeds up the Algorithm
Analysis
An Example
Further Reading
Acknowledgement
13 The Sieve of Eratosthenes – How Fast Can We Compute a Prime Number Table?
From the Idea to a Method
A Simple Idea
How Fast Is the Computation?
How Does the Algorithm Spend Its Time?
Do We Need Every i Value?
Can We Get Even Faster?
What Can We Learn from This Example?
Further Considerations
Further Reading
14 One-Way Functions. Mind the Trap – Escape Only for the Initiated
The Mirror Image of Multiplication: Factorization
One-Way Functions
A Practical Problem: Searching a Telephone Book
Security and Googles
Further Reading
15 The One-Time Pad Algorithm – The Simplest and Most Secure Way to Keep Secrets
Encrypting Messages
The Algorithm
Breaking the Code
Further Reading
16 Public-Key Cryptography
Public Keys
A Limited Algebra
Construction of the Keys
Encryption
Decryption
The Eavesdropper
Without Limited Mathematics
ElGamal’s Method
Modular Multiplication and Modular Exponentiation
Description of ElGamal’s Cryptosystem
Further Methods
Security
Further Reading
17 How to Share a Secret
A Simple Method to Share a Secret
General Secret Sharing
Secret Sharing, Information Theory and Cryptography
Further Reading
18 Playing Poker by Email
Dealing Cards by Snail Mail
How to Shuffle and Distribute the Cards
How to Bid
How to Replace Cards
The Showdown
How to Verify That No One Has Cheated
Discussion
Dealing Cards by Email
Electronic Envelopes
How to Shuffle the Cards and Distribute Them to Bob
One-Way Functions
How to Replace Cards
A Mathematical Description
Distribution of Cards to Both Players
Commitment to the Selected Coding Tables
Putting Cards into Envelopes
Distributing Cards to Alice
Distributing Cards to Bob
Dropping Cards
Properties of the Electronic Envelopes
How to Check Whether the Opponent Has Cheated
Poker with More than Two Players
Further Reading
19 Fingerprinting
How to Compare Long Texts over the Telephone
Texts as Sequences of Numbers and Modular Arithmetic
Fingerprints
Fingerprints with Random Numbers
The Protocol
Summary
Remarks on the Fingerprinting Theorem
Further Reading
Acknowledgement
20 Hashing
Message Digest
Secure Hashing
Hashing for Dictionaries
Storing a Data Item z with Key x
Searching a Data Item Corresponding to Key x
External Links and References
21 Codes – Protecting Data Against Errors and Loss
Introduction
Where Are Codes Used?
Reed-Solomon Codes
New Coding Techniques: Low-Density Parity-Check Codes
Network Codes
Places to Start Looking for More Information
Acknowledgement
Part III Planning, Coordination and Simulation
Overview
22 Broadcasting – How Can I Quickly Disseminate Information?
References
23 Converting Numbers into English Words
Stepwise Development of an Algorithm
Splitting Numbers into Three-Digit Groups …
…and Generating the English Words
Function generateGroup
Function generateWeight
Lessons Learned
What to Read and Try out for Yourself
24 Majority – Who Gets Elected Class Rep?
Majority Algorithm
Correctness of the Majority Algorithm
How Many Comparisons Are Necessary?
Applications and Extensions
What Can We Learn from the Solutions to the Majority Problem?
Further Reading
25 Random Numbers – How Can We Create Randomness in Computers?
A Tactical Game: “Rock, Paper, Scissors”
Means for the Generation of Random Numbers: Modular Arithmetic
Examples for Modular Arithmetic
Illustration of Modular Arithmetic
An Algorithm for the Generation of Pseudorandom Numbers
Periodic Behavior
Simulation of True Random Number Generators
The Algorithm for Rock, Paper, Scissors
Monte Carlo Simulation: Determination of Areas Using “Random Rain”
Further Reading
26 Winning Strategies for a Matchstick Game
Learning from Small Examples
An Algorithm to Compute a Winning Strategy
The Running Time of the Algorithm
Extensions and Background
Further Reading
27 Scheduling of Tournaments or Sports Leagues
Generation of Schedules
Schedules with Home-Away Assignments
Further Reading
28 Eulerian Circuits
When Does an Eulerian Circuit Exist?
Finding Eulerian Circuits
The Algorithm
The House of Santa Claus
Of Postmen and Garbage Collectors
Further Reading
29 High-Speed Circles
Drawing Circles: Keep It Simple!
Bresenham’s Algorithm for Circles
A Racing Duel
Further Reading
30 Gauß-Seidel Iterative Method for the Computation of Physical Problems
Warmup: Soccer
Temperature Calculation in a Rod (1D)
Temperature Computation on a Plate (2D)
Further Reading
31 Dynamic Programming – Evolutionary Distance
Mathematical Modeling
Calculation of the Evolutionary Distance
The Algorithm
Conclusion
References
Part IV Optimization
Overview
32 Shortest Paths
Dijkstra’s Algorithm
FAQs and Further Reading
33 Minimum Spanning Trees (Sometimes Greed Pays Off …)
The Bridge Project of the Algos
Building Bridges After the Hurricane
The Algorithms of Prim and Kruskal
Further Reading
34 Maximum Flows – Towards the Stadium During Rush Hour
The Algorithm
Some Open Questions
Why Does It Work?
Epilogue
Solution
Further Reading
35 Marriage Broker
Problem
The Basic Principle of the Procedure
The Construction of a Maximum Matching
The Algorithm
The Marriage Theorem
Where Is the Marriage Theorem Needed by the Algorithm
Time Analysis
Further Reading
Acknowledgements
36 The Smallest Enclosing Circle – A Contribution to Democracy from Switzerland?
Why It Works
Further Reading
37 Online Algorithms – What Is It Worth to Know the Future?
The Ski Rental Problem
The Paging Problem
Further Reading
38 Bin Packing or “How Do I Get My Stuff into the Boxes?”
The Online Problem “Moving Inexpensively”
Analysis of the Algorithms
How Well Can Online Algorithms for Bin Packing Perform?
Further Reading
39 The Knapsack Problem
Pareto-Optimal Solutions
The Nemhauser-Ullmann Algorithm
Further Reading
40 The Travelling Salesman Problem
Introduction
The Brute-Force Method
Dynamic Programming
Approximative Solutions
MST Algorithm
Some Final Remarks
Further Reading
41 Simulated Annealing
What Is Simulated Annealing?
The Travelling Salesperson Problem
Further Applications
Further Reading
Author Details
People also search for Algorithms Unplugged 1st :
grokking algorithms algorithms unplugged
download algorithms unplugged
borrow algorithms unplugged
synopsis of algorithms unplugged
You may also like…
eBook PDF
LNCS 0558 Computational Discrete Mathematics 1st edition by Helmut Alt 3540427759 978-3540427759
eBook PDF
Color Atlas of Ultrasound Anatomy 1st Edition by Berthold Block ISBN 1588902811 9781588902818