Hromkovič J. Algorithmic Adventures. From Knowledge to Magic

Springer, 2009, -367 p.The public image of computer science does not reflect its true nature. The general public and especially high school students identify computer science with a computer driving license. They think that studying computer science is not a challenge, and that anybody can learn it. Computer science is not considered a scientific discipline but a collection of computer usage skills.
This is a consequence of the misconception that teaching computer science is important because almost everybody possesses a computer. The software industry also behaved in a short-sighted manner, by
putting too much pressure on training people in the use of their
specific software products,
Searching for a way out, ETH Zurich offered a public lecture series called The Open Class — Seven Wonders of Informatics in the fall of 2005. The lecture notes of this first Open Class were published in German by Teubner in 2006. Ten lectures of this Open Class form the basis of Algorithmic Adventures.
The first and foremost goal of this lecture series was to show the beauty, depth and usefulness of the key ideas in computer science. While working on the lecture notes, we came to understand that one can recognize the true spirit of a scientific discipline only by viewing its contributions in the framework of science as a whole. We present computer science here as a fundamental science that, interacting with other scientific disciplines, changed and changes our view on the world, that contributes to our understanding of the fundamental concepts of science and that sheds new light on and brings new meaning to several of these concepts. We show that computer science is a discipline that discovers spectacular, unexpected facts, that finds ways out in seemingly unsolvable situations, and that can do true wonders. The message of this book is that computer science is a fascinating research area with a big impact on the real world, full of spectacular ideas and great challenges. It is an integral part of science and engineering with an above-average dynamic over the last 30 years and a high degree of interdisciplinarity.
The goal of this book is not typical for popular science writing, which often restricts itself to outlining the importance of a research area. Whenever possible we strive to bring full understanding of the concepts and results presented. We take the readers on a voyage where they discover fundamental computer science concepts, and we help them to walk parts of this voyage on their own and to experience the great enthusiasm of the original explorers. To achieve this, it does not suffice to provide transparent and simple explanations of complex matters. It is necessary to lure the reader from her or his passive role and to ask her or him frequently to do some work by solving appropriate exercises. In this way we deepen the understanding of the ideas presented and enable readers to solve research problems on their own.
All selected topics mark milestones in the development of computer science. They show unexpected turns in searching for solutions, spectacular facts and depth in studying the fundamental concepts of science, such as determinism, causality, nondeterminism, randomness, algorithms, information, computational complexity and automation.A Short Story About the Development of Computer Science or Why Computer Science Is Not a Computer Driving Licence
Algorithmics, or What Have Programming and Baking in Common?
Infinity Is Not Equal to Infinity, or Why Infinity Is Infinitely Important in Computer Science
Limits of Computability or Why Do There Exist Tasks That Cannot Be Solved Automatically by Computers
Complexity Theory or What to Do When the Energy of the Universe Doesn’t Suffice for Performing a Computation?
Randomness in Nature and as a Source of Efficiency in Algorithmics
Cryptography, or How to Transform Drawbacks into Advantages
Computing with DNA Molecules, or Biological Computer Technology on the Horizon
Quantum Computers, or Computing in the Wonderland of Particles
How to Make Good Decisions for an Unknown Future or How to Foil an Adversary