Название: Computer Algorithms: Correctness Proofs and Performance AnalysesАвтор: Shashank K. Mehta
Издательство: PHI Learning Private Limited
Год: 2023
Страниц: 473
Язык: английский
Формат: pdf (true)
Размер: 34.4 MB
The book is self-contained and includes the desired mathematical background. The book covers most of the data structures and classical graphs algorithms, string algorithms, matroid algorithms, linear algebra algorithms, flow and circulation algorithms, linear programming solvers, and integer algorithms. It covers several topics which are rarely covered in the existing textbooks. Pseudocode is provided for every algorithm. Proof of correctness and the complexity analysis is given for every algorithm. Examples are also provided to help explain several algorithms. The book is designed for an introductory as well as an advance course in the design and analysis of algorithms. It is intended for undergraduate as well as postgraduate students of computer science and engineering. Some of the topics covered in the book are as follows. i) String homomorphism and isomorphism ii) Detailed proof of graph matching algorithm including augmenting path computation iii) Gallai Edmonds decomposition algorithm iv) Matroid Intersection algorithm Klein.
There are excellent textbooks1 available for an undergraduate course on algorithms. However, the same cannot be said for graduate level books on the subject. A graduate level book requires rigorous treatment of two issues for each algorithm: the correctness proof and the time/space complexity analysis.
The motive behind writing this book was to develop a textbook covering most of the traditional topics but with complete proof of correctness and complexity analysis. A lecturer cannot cover all the correctness proofs if the course has to be completed in a single semester. There are multiple lecture notes covering these proofs on Internet but often these notes are not carefully screened for errors. This book is an attempt to remedy this situation.
The book is not only for a graduate student but also for an advance undergraduate student as well. It is self contained so that an undergraduate student can follow the subject without having to study other books. Some standard definitions may not be given here as those are readily accessible on the Internet.
The book covers several topics which are rarely covered in the textbooks available in the market. Here is the list of such topics. In Chapter 4 the problem of string matching is discussed. The problem has been generalized to homomorphism and isomorphism of strings and Knuth-Morris-Pratt algorithm is generalized for string isomorphism problem. In Chapter 6 computation of augmenting path for maximum matching has been discussed. Also Gallai-Edmonds Decomposition algorithm has been discussed in the same chapter. The Edmond’s Matroid Intersection algorithm is presented in Chapter 7. In Chapter 8 Klein’s cycle cancellation algorithm and Goldberg-Karp’s algorithm for minimum cost circulation are introduced.
In Chapter 9, I have explained lower-triangular upper-triangular decomposition using Gaussian Elimination as well as using the divide-and-conquer technique. Chapter 11 is devoted to Interior-Point Method for linear programming. In this chapter a complete solution based on Primal-Dual technique has been presented. In Chapter 12, the readers will get more information on Primal-Dual technique. This time they will be able to apply this technique to compute the minimum weight perfect matching in general graphs. Theoretical background and algorithms are developed for integral computations in Chapters 13, 14, and 15. Finally, in Chapter 16, I have introduced Schonhage-Strassen’s algorithm for integer multiplication and Agarwal-Kayal-Saxena’s algorithm for primality testing.
Скачать Computer Algorithms: Correctness Proofs and Performance Analyses