Ryuhei Uehara - First Course in Algorithms Through Puzzles

This Springer imprint is published by the registered company Springer Nature Singapore Pte Ltd.

The registered company address is: 152 Beach Road, #21-01/04 Gateway East, Singapore 189721, Singapore

This book is an introduction to algorithms . What is an algorithm ? In short, algorithm means a way of solving a problem. When people encounter a problem, the approach to solving it depends on who is solving it, and then the efficiency varies accordingly. Lately, mobile devices have become quite smarter, planning your route when you provide your destination, and running an application when you talk to it. Inside this tiny device, there exists a computer that is smarter than the old large-scale computers, and it runs some neat algorithms to solve your problems. Smart algorithms use clever tricks to reduce computational time and the amount of memory needed.

One may think that from the viewpoint of the progress of hardware devices, is an improvement such as this insignificant? However, you would be wrong. For example, take integer programming. Without going into details, it is a general framework to solve mathematical optimization programs, and many realistic problems can be solved using this model. The running time of programs for solving integer programming has been improved 10,000,000,000 times over the last two decades. Surprisingly, the contribution of hardware is 2000 times, and the contribution of software, that is, the algorithm, is 4,75,000 times. It is not easy to see, but the improvement of the way of solving has been much more effective than the development of hardware.

In this book, I introduce and explain the basic algorithms and their analytical methods for undergraduate students in the Faculty of Information Science. This book starts with the basic models, and no prerequisite knowledge is required. All algorithms and methods in this book are well known and frequently used in real computing. This book aims to be self-contained; thus, it is not only a textbook, but also allows you to learn by yourself, or use as a reference book for beginners. On the other hand, I provide some smart tips for non-beginner readers.

Exercise : Exercises appear in the text and are not collected at the end of sections. If you find an exercise when you read this book, I would like to ask you to take a break, tackle the exercise, and check the answer and comments. For every exercise, an answer and comments are given in this book.

Each exercise is marked with

marks, and those with many cups are more difficult than those with fewer ones. They say that a mathematician is a machine for turning coffee into theorems (this quotation is often attributed to Paul Erds; however, he ascribed it to Alfrd Rnyi). In this regard, I hope you will enjoy them with cups of coffee.

Exercises are provided in various ways in your textbooks and reference books. In this book, all solutions for exercises are given. This is rather rare. Actually, this is not that easy from the authors viewpoints. Some textbooks seem to be missing the answers because of the authors laziness. Even if the author considers a problem trivial, it is not necessarily the case for readers, and beginners tend to fail to follow in such small steps. Moreover, although it seems trivial at a glance, difficulties may start to appear when we try to solve some problems. For both readers and authors, it is tragic that beginners fail to learn because of authors prejudgments.

Even if it seems easy to solve a problem, solving it by yourself enables you to learn many more things than you expect. I am hoping you will try to tackle the exercises by yourselves. If you have no time to solve them, I strongly recommend to check their solutions carefully before proceeding to the next topic.

Analyses and Proofs : In this book, I provide details of the proofs and the analyses of algorithms. Some unfamiliar readers could find some of the mathematical descriptions difficult. However, they are not beyond the range of high school mathematics although some readers may hate mathematical induction, exponential functions, or logarithmic functions. Although I believe that ordinary high school students should be able to follow the main ideas of algorithms and the pleasure they bring, you may not lie down on your couch to follow the analyses and proofs. However, I want to emphasize that there exists beauty you cannot taste without such understanding. The reason why I do not omit these tough parts is that I would like to invite you to appreciate this deep beauty beyond the obstacles you will encounter. Each equation is described in detail, and it is not as hard once you indeed try to follow.

Algorithms are fun. Useful algorithms provide a pleasant feeling much the same as well-designed puzzles. In this book, I have included some famous real puzzles to describe the algorithms. They are quite suitable for explaining the basic techniques of algorithms, which also show us how to solve these puzzles. Through learning algorithms, I hope you will enjoy acquiring knowledge in such a pleasant way.