In my last post, I said my next post will be about one of my papers on directed minors. But that paper is taking more time to write than I expected. Meanwhile, here is my review of two algorithms textbooks: Algorithms Unplugged and The Power of Algorithms, to appear in the SIGACT book review column soon.
Merry Christmas and Happy New Year to everybody !!
——————————————————————————————————–
Introduction
Algorithms play an integral part in our daily lives. They are everywhere. They help us travel efficiently, retrieve relevant information from huge data sets, secure money transactions, recommend movies, books, videos, predict stock market etc. Algorithms are essentially simple extensions of our daily rational thinking process. It is very tough to think about a daily task that does not benefit from efficient algorithms. Often the algorithms to solve our daily tasks are very simple, yet their impact is tremendous.
Most of the common books on algorithms start with sorting, searching, graph algorithms and conclude with NP-completeness and perhaps some approximation and online algorithms. The breadth of algorithms cannot be covered by a single book. Algorithms Unplugged and The Power of Algorithms take different approach compared to standard Algorithms textbooks. They are aimed at explaining several basics algorithms (written by multiple authors) in an intuitive manner with real-life examples, without compromising the details. This is how algorithms should be taught.
Algorithms Unplugged
This book is divided into four major parts. Each part has several chapters. Here is an overview of these parts and chapters.
Part I: The first part is about sorting and systematic search i.e., finding things quickly. Chapter 1 introduces binary search, one of the most basic search strategies. A recursive implementation of binary search is explained using an intuitive example to find a CD is a sorted sequence of CD’s. Chapter 2 explains insertion sort, one of the most intuitive comparison-based sorting algorithms and Chapter 3 explains merge sort and quick sort, two sorting algorithms based on the divide and conquer paradigm. Chapter 4 explains bitonic sorting circuit to implement a parallel sorting algorithm. Chapter 5 describes topological sorting and explains how to schedule jobs without violating any dependencies between jobs. Chapter 6 considers string searching problem and explains the Boyer-Moore-Horspool algorithm. Chapter 7 considers the search problem in several real-world applications and explains the depth first search algorithm. Chapter 8 explains how to escape from a dark labyrinth using Pledge’s algorithm. Chapter 9 defines strongly-connected components in directed graphs and explains how to efficiently find directed cycles. Chapter 10 introduces basic principles of search engines, introduces PageRank and explains how to find relevant pages in the World-Wide Web.
Part II: The second part deals with arithmetic problems, number theoretic, cryptographic, compression and coding algorithms. Chapter 11 presents Karatsuba’s method of multiplying long integers that is much more efficient than the basic grade school method. Chapter 12 explains how to compute the greatest common divisor of two numbers using the centuries old Euclidean algorithm. Chapter 13 explains the Sieve of Eratosthenes, a practical algorithm to compute the table of prime numbers. Chapter 14 introduces the basics of one-way functions which play a crucial role in the following chapters. Chapter 15 presents One-Time-Pad, a basic symmetric cryptographic algorithm. Chapter 16 explains Public-Key Cryptography, an asymmetric cryptographic method using different keys for encryption and decryption. Chapter 17 explains how to share a secret in such a way that all participants must meet to decode the secret. Chapter 18 presents a method to play poker by email using cryptographic methods. Chapter 19 and 20 presents fingerprinting and hashing techniques to compress large data sets so that they can be compared using only a few bits. Chapter 21 introduces the basics of coding algorithms to protect data against errors and loss.
Part III: The third part deals with strategic thinking and planning. Chapter 22 discusses broadcasting algorithms to disseminate information quickly. Chapter 23 presents algorithms to convert numbers into english words. Chapter 24 explains majority algorithms with applications and extensions. Chapter 25 explains how to generate random numbers. Chapter 26 discusses winning strategies for a matchstick game. Chapter 27 discusses algorithms to schedule sports leagues. Chapter 28 characterizes eulerian circuits and presents algorithms to find them. Chapter 29 details how to approximately draw circles on a pixelated screen. Chapter 30 explains Gauss-Seidel iterative method. Chapter 31 presents a dynamic programming algorithm to compute distance between two DNA sequences.
Part IV: The final part is about optimization problems. Chapter 32, 33 and 34 describes shortest path, minimum spanning tree and maximum-flow algorithms, three basic optimization problems. Chapter 35 discusses stable marriage problem and presents an algorithm to find a stable matching in a bipartite graph. Chapter 36 explains an algorithm to find the smallest enclosing cycle of a given set of points. Chapter 37 presents online algorithms for the Ski-Rental and Paging problems. Chapter 38 and 39 discusses the Bin-Packing and the Knapsack problems. Chapter 40 discusses the Traveling Salesman Problem, one of the most important optimization problems that challenged mathematicians and computer scientists for decades. Chapter 41 introduces Simulated Annealing method to solve a basic tiling problem and the Traveling Salesman Problem.
At the end of every chapter there are references for further reading. Readers are highly encouraged to go through these references to get better understanding of the corresponding concepts.
The Power of Algorithms
This book is divided into two major parts. Each part has several chapters. Here is an overview of these parts and chapters.
Part I: The first part is divided into three chapters. Chapter 1 gives a historical perspective of algorithms, origin of the word {\em algorithm}, recreational algorithms and reasoning with computers. Chapter 2 aims at explaining how to design algorithms by introducing the basics of graph theory and two algorithms techniques: the backtracking technique and the greedy technique. Chapter 3 quickly introduces the complexity classes P and NP and the million dollar P vs NP problem.
Part II: The second part is aimed at explaining several algorithms of daily life. Chapter 4 explains the Shortest Path problems, one of the basic optimization problems. Chapter 5 discusses the basics of Internet and Web Graphs and explains several related algorithms to Crawl, Index and Search the Internet. Chapter 6 discusses the basics of cryptographic algorithms such as RSA and digital signatures. Chapter 7 discusses biological algorithms. Chapter 8 explains networks algorithms with transmission delays. Chapter 9 discusses algorithms for auctions and games. It presents Prisoner’s dilemma, Coordination games, Randomized strategies, Zero-sum games, Nash’s Theorem, Spurners Lemma, Vickery-Clarke-Groves auctions and competitive equilibria. Chapter 10 explains the power of randomness and its role in complexity theory.
At the end of every chapter there are Bibliographic Notes with several pointers for further reading.
Opinion
Overall I found these two books very interesting and well-written. There is a nice balance between informal introductions and formal algorithms. It was a joy for me to read these books and I recommend them to anyone (including beginners) who is curios to learn some of the basic algorithms that we use in our daily lives in a rigorous way. I strongly encourage you to read these two books even if you have already read a bunch of algorithms books.
There is no prerequisite to follow these books, except for a reasonable mathematical maturity and perhaps some familiarity with basic constructs of at least one programming language. They can be used as a self-study text by undergraduate and advanced high-school students. In terms of being used in a course, some of the topics in these books can be used in an undergraduate algorithms course. I would definitely suggest that you get them for yourself or your university/department library.
——————————————————————————————————–
My Brain is Open 