Textbook in PDF format This textbook introduces basic algorithms and explains their analytical methods. All algorithms and methods introduced in this book are well known and frequently used in real programs. Intended to be self-contained, the contents start with the basic models, and no prerequisite knowledge is required. This book is appropriate for undergraduate students in computer science, mathematics, and engineering as a textbook, and is also appropriate for self-study by beginners who are interested in the fascinating field of algorithms. More than 40 exercises are distributed throughout the text, and their difficulty levels are indicated. Solutions and comments for all the exercises are provided in the last chapter. These detailed solutions will enable readers to follow the author’s steps to solve problems and to gain a better understanding of the contents. 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. 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. 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. 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. Preface Preliminaries Recursive Call Algorithms for Searching and Sorting Searching on Graphs Backtracking Randomized Algorithms Game Tree and Its Application∗ References Answers to Exercises