Review on Book -Data Structures and Algorithms by Aditya Y. Bhargava

This is the first ever book which I have gone through for learning Data Structures and Algorithms .Otherwise learning difficult and dry concepts like these cannot be done by reading from books. They need a good teacher to understand well .Don’t you agree?

Well, this was a very different kind of book which I enjoyed reading and learning from. The first thought that came to me when I chose to go through this book was “What a peculiar title it has !” .The first thing I did was to lookup for the meaning of the fancy word “Grokking” in the title, which meant “learning something intuitively” .This means that we are going to learn algorithms without even knowing that we are , and so was the experience. Otherwise, books on these topics have some serious names like ‘Analysis of Algorithms’, or just simply ‘Algorithms’ etc. But this title was interesting, and you know first impression is the best impression.

About the Author:

Aditya Bhargava is a software engineer at Etsy, an online market place for handmade goods. He has a master’s degree in computer science from the University of Chicago. He also runs a popular illustrated tech blog at adit.io and I must say, he is a very good teacher too.

Now we will go through a brief tour on the various aspects covered in the book. Let’s start with Data Structures, but before that what are data structures? Simply, the Structures (or) objects that carry (or) contain data and can be used as and when required.

Data Structures covered:

· Arrays: These are the fundamental data structures used everywhere. They have the advantage of random access through indexing but come with the drawback of contiguous memory allocation when inserting elements.

· Linked lists: It is a collection of nodes where each node consists of a data field and reference (link) to the next node in the list. It overcomes the problem of contiguous memory allocation of arrays and are faster at insertion and deletion.

· Hash maps: It is a combination of a hash function and an array, where keys are mapped to values via hash function. It gives best of both the worlds(i.e., of arrays and linked lists) giving both random access and easier insertions and deletions

· Stacks: These are one-way arrays where all operations occur at the same end called top, following the FILO (First In Last Out) principle.

· Queues: This are also a type of array where addition of elements occur at one end and deletions occur at other end. It follows FIFO(First In First Out) principle.

· Graphs: It is a data structure which is a collection of nodes and connecting edges. They are of two types: undirected and directed graphs depending on whether the relationship between the nodes is bidirectional or unidirectional.

So, these were the data structures that the author covered in the book. He then used them for implementing the Algorithms (- a step by step procedure to solve a particular problem) given below

Algorithms Explained:

· Binary Search: A basic searching algorithm which works on a sorted array/list to search for a given item, usually called the key.

· Selection Sort: A basic but costlier sorting technique which reads an array and outputs another array in sorted order.

· Quick Sort: Another, but quick (as the name suggests), sorting algorithm which works on the divide and conquer principle.

· Breadth First Search: An optimizing algorithm that works on unweighted Directed Graphs to find the shortest path between two nodes.

· Dijsktra’s Algorithm: Another optimizing algorithm to give the shortest path between two nodes but this time it works on positively weighted Directed Graphs. It fails to operate on negatively weighted graphs, for which Bellman Ford Algorithm comes to rescue.

· Approximation Algorithm: These algorithms are used for problems that do not have any fast algorithmic solution, and their complexity increases with increase in size called NP Complete problems. We used the greedy technique to solve famous set covering and class scheduling problem. Greedy Algorithms are easy to write ,fast to run and optimize locally hoping to end up with global optimum

· KNN Algorithms: This is an introductory-level algorithm in machine learning which operates on two basic concepts of classification and regression. A successful k-nearest neighbor algorithm totally depends on features selected to describe an object that directly correlate and are not biased with each other.

Now let us look at various programming techniques and concepts used by the author to design the algorithms above.

Programming Techniques Used:

· Recursion: It is a choice against using loops for iteration where the iteration is achieved by repeated function calls to itself until a base case (when the iteration is terminated) is reached. Someone stated that:

Loops may achieve performance gain for program while

Recursion may achieve performance gain for programmers.

Recursion has a low performance over loops because of their own call stack

· Divide and Conquer: It is a strategy where a large and complex problem is divided into smaller-sub problems that are solved independently and combined at the end to achieve the solution. It is used in algorithms like Quick sort, Merge sort etc.

· Dynamic Programming: It is an algorithmic technique for solving a problem by breaking it down into simpler subproblems and utilizing the fact that solution to overall problem depends on solution to its sub problems. It is useful when you are trying to optimize something given some constraint.

· Classification: It is the process of categorizing things into groups based on some common features.

· Regression: It allows us to predict values for one or multiple variables(dependent variables) based on defined values of the other variables(independent variables).

Finally, we are done with covering most of the topics the book presents .In addition, there is one last chapter which lists other 10 algorithms which were not part of the book but still are very important to learn. They are:

1. Trees :Binary search tree where every node can have at most two children and value of left node is always less than the root node and value of right node is always greater than root node.

2. Inverted index: It is used in search engines ,and is a hash map that maps words to places they occur.

3. Fourier Transform: It processes a digital signal and breaks it down into its individual components.

4. Parallel Algorithms :Algorithms that can run on multiple cores to make it run faster.

5. MapReduce: It is a distributed Algorithm that can be run on several machines and can be accessed using the open source tool Apache Hadoop.

6. Bloom filters: It is a replacement for hash map which gives you accurate answers occupying less space than hash map

7. Hyper Log Log:It is also a probabilistic data structure which approximates the number of unique elements in the set.

8. SHA: Security Hash Algorithm is a one-way hash function that generates a unique hash for any string used for encryption. It is locally insensitive(i.e. even similar words have totally different hashes) . Simhash is another hash function which is locally sensitive.

9. Diffie Hellman Key exchange: It makes encryption stronger by using the concept of two keys called the public key and the private key.

10. Linear programming: It uses Simplex algorithm for optimizing a linear objective function based on some constraints. All graph problems can be solved using LP.

Now that we are done with discussing the concepts, I would like to mention few points why this book should be a must read

Things I liked about the book:

· Visuals: I think you are attracted to read more when a book has pictures in it rather than simply lines and lines of words. This book has plenty of interesting sketches that will keep you hooked while reading.

· Reader Friendly language: The language used for explanation is easy to understand and also has some interactivity in it. It also has some humor here and there to keep the reader engaged. It is like sitting before someone who is trying to explain something in the best possible way .

· Real life examples: The author gives you relatable examples for any concept for e.g., contiguous memory allocation for Arrays is described using the situation of few friends wanting to sit together during a movie when new friends unexpectedly join in.

· Exercises: There a couple of mind exercises that pop up in between the course which gives you time to think and you can find the solutions to them at the end of the book. Personally, I don’t like books which do have exercises but don’t have answers to them, leaving you nowhere to check whether you are right or wrong, which is I think of no use.

· Completeness: Now I will let you know the procedure used for explanation. Firstly, the problem is stated using contemporary examples for better understanding. Then a solution is proposed which is explained using sketches and examples. Not only this, the book also gives you the implementation of the algorithm in your favourite language Python ,explains what every line of code does, and then the performance of the code is specified in terms of big Oh notation.

Don’t you think it’s amazing having everything for a concept all at one place!

· Size: One last point I want to mention is the size of the book .It’s only 200 pages long, which is not a big number and having all these benefits it would be easy for any programmer to take advantage of the book.

Conclusion:

§ I would suggest this great book to beginners and intermediaries(and obviously other curious people as the title suggests) interested in learning basic Data Structures And Algorithms effectively.

§ I want you all to recommend the next book on this concept that could be a perfect sequel tothe current book.

-By Nema Jaleel

3rd year, Computer Science student at

Muffakham Jah College of Engineering and

Technology