My class notes on Algorithmic Complexity, now a refresher for craving teachers and knowledge greedy students: A must primer for GATE(India), Adv. GRE appearing students.

by N.B. Venkateswarlu

Some of the important points of this book are summarised My main objective of bringing this book is to make faculty who teach “algorithms” courses not to skip the concepts related to “computational complexity” because of its hard mathematical dealing. I don’t want to claim this as a normal book, instead I consider it as more like a questions and answers book like a workbook. In fact, my zeal for algorithms started in the 1980s and it has flourished a lot during my doctoral work in the early 1990s on pattern recognition (an old incarnation of today’s buzzword machine learning or deep learning) and image processing (PRIP) algorithms of both serial and parallel. All my doctoral work is related to exploring increasing the experimental speed-ups of PRIP algorithms. Since then I have been gathering tricky questions related to algorithms and in this book I am dealing with the ones which are related to “Algorithmic Complexity”. In fact, I have seen the syllabus of “Algorithmics” courses in some American Universities. I was also exploring the title “A primer on Algorithmics” as what I covered in this book is taught in those American Universities.. Certainly a teacher plays a major role in making one course as interesting or intimidating to students. Many computer science faculty around me feel one intimidating course in the four year Computer Science curriculum is “Design and analysis of Algorithms”. Moreover, the first chapter “Algorithmic Complexity” is more terrifying and usually overlooked or skipped by the teachers. Of course, students may also keep quiet as they rarely get questions from that chapter in their examinations!. Please do understand that I am sharing my observations on the education system that is around me. However, in examinations such as GATE(India), placement tests etc., student’s knowledge of “Algorithmic Complexity” is very crucial for their success. Usually the first chapter(s) of any standard books related to algorithms are related to “Algorithmic Complexity”. Whereas this I want to make this as a book on “Algorithmic Complexity”. Wow. Chapter to a book!!. I find it very terribly difficult to identify the possible themes to be made as chapters in my book. I want this workbook to be useful for beginners, especially high school students who are preparing for the Informatics Olympiad (IOI), Univ. of Waterloo Mathematics related competitions and admission tests, etc. like competitions. . I have included an exclusive chapter on logarithms and included many real life problems where logarithms are used. Also, many games involving logarithms are introduced in this chapter. A chapter on induction and another on recurrences are included to build the skill set needed to solve time complexity of recursive algorithms. One chapter is included to introduce the essence of the word “computational complexity” and its need. A chapter is included that introduces all the aspects of Big-O, Big-Omega, Big-Theta, Little-O, Little-Theta, Master’s theorem. In fact, this chapter is the heart of this book. Many questions are solved and many assignments are included which can be solved by anyone. One chapter is included to introduce “average case complexity” of algorithms.
Space complexity is introduced in a chapter.

456 pages, Paperback

Published August 20, 2021