The book is a senior course whose author has been teaching at the University of Pensylvania for large classes of computer scientists and mathematicians, including seniors and graduate students. The monograph is easily readable, even complicated themes are very carefully explained, sometimes maybe, too detailed. Many interesting exercises for students are given together with suggestions for writing a program. Bibliography is cited in each chapter.
The book consists of 5 chapters. After some motivation and explanation of basic concepts, in Chapter 1 mathematical background about the representation of numbers in different bases, operations with power series, linear recurrence relations with constant coefficients and basic concepts of graphs are formulated.
Chapter 2 deals with recursive algorithms and their analysis from the point of view of complexity. First, the quicksort is the object of study, then recursivity is explained by the maximum independent set of a graph and the popular four-color problem. The story of fast matrix multiplication is also mentioned. Direct and inverse fast Fourier transform is given in detail and its application for multiplication of polynomials and large-scale multiplication of two integers is shown.
Chapter 3 discusses a “beautiful theoretical subject with many important applications”, i.e., the network flow problem with V vertices and E edges. The development of algorithms is chronologically shown from O(E 2 V) to the \(O(E\cdot V\cdot \log(V^ 2/E))\) estimation and some of them are analyzed. The algorithm of Ford and Fulkerson is described in details. Some applications of this problem are also given.
Chapter 4 deals with some algorithms from the theory of numbers for which the connection between old ideas and modern research by computers is underlined. The algorithm for greatest common divisor and extended Euclidean algorithm is investigated. The testing of primality for which does not exist any polynomial algorithm is studied. The properties of the ring of integers modulo n are investigated and the Chinese remainder theorem is proved. Some probabilistical algorithms for pseudoprimality test are described and the proof of effectiveness of one of them is made. Further, factoring large integers and cryptography are studied. The RSA scheme is explained and the method of factoring large integers is also discussed.
Chapter 5 formulates a number of strongly connected important computational questions (until now hundredth of them are known), called NP-complete problems, for which there are until now no fast algorithms. NP-completeness and Cook’s theorem including the proof are explained and their role is mentioned by some examples. The method of backtracking for solving some NP-complete problems is described and some approximate algorithms for solution of hard problems are formulated.
I strongly recommend this book as introductory text for all those who need an understandable explanation of these interesting problems and their solution.