Hands-On Data Structures and Algorithms with JavaScript

Kashyap Mukkamala

• Publisher: Packt Publishing
• Year: 2018
• ISBN:
  9781788397544
• Edition: 1
• Topic: Computer Science
• Subtopic: Web Development
• Index: Computer Science

Increase your productivity by implementing complex data structures and algorithms using JavaScriptAbout This Book• A step by step guide, which will provide you with a thorough discussion on the analysis and design of fundamental JavaScript data structures• Get a better understanding of advanced concepts such as space and time complexity to optimize your code• Focus more on solving the business problem and less on the technical challenges involvedWho This Book Is ForIf you are a JavaScript developer looking for practical examples to implement data structures and algorithms in your web applications, then this book is for you. Familiarity with data structures and algorithms will be helpful to get the most out of this book.What You Will Learn• Build custom Back buttons embedded within your application• Build part of a basic JavaScript syntax parser and evaluator for an online IDE• Build a custom activity user tracker for your application• Generate accurate recommendations for credit card approval using Decision Trees• Simplify complex problems using a graphs• Increase the performance of an application using micro-optimizationsIn DetailData structures and algorithms are the fundamental building blocks of computer programming. They are critical to any problem, provide a complete solution, and act like reusable code. Using appropriate data structures and having a good understanding of algorithm analysis are key in JavaScript to solving crises and ensuring your application is less prone to errors.Do you want to build applications that are high-performing and fast? Are you looking for complete solutions to implement complex data structures and algorithms in a practical way? If either of these questions rings a bell, then this book is for you!You'll start by building stacks and understanding performance and memory implications. You will learn how to pick the right type of queue for the application. You will then use sets, maps, trees, and graphs to simplify complex applications. You will learn to implement different types of sorting algorithm before gradually calculating and analyzing space and time complexity. Finally, you'll increase the performance of your application using micro optimizations and memory management.By the end of the book you will have gained the skills and expertise necessary to create and employ various data structures in a way that is demanded by your project or use case.Style and approachStep-by-step topics will help you get started with solutions for implementing classic data structures and algorithms. Learn by doing with hands-on code snippets that give you practical experience of the subject.

Exploring Types of Algorithms

An algorithm in the computer science world is a set of instructions that takes finite space and time to execute. It starts at an initial state of the application and then performs a set of instructions step by step to achieve the end result.

Algorithms come in all shape and sizes, and all of them will fit the bill when you compare it with the overly generic definition of what an algorithm is. The big question is to decide which algorithm to use in which case and to make modifications to enhance its functionality based on the application's needs.

As I have shown in the use cases in previous chapters, most of the times, the algorithms that exist out there do not directly apply to the problems at hand. This is when a thorough understanding of the algorithm comes in handy. That is exactly what we will be doing in this chapter; we will take a look at a series of algorithms and then try to understand them better with the help of some examples.

In this chapter, we will discuss the following algorithms with some examples:

• Recursion
• Dijkstra
• Breadth First Search (BFS)
• Dynamic Programming
• Greedy Algorithm
• Branch And Bound

Let's set up a bare-bones Node.js project before we start looking at the use cases.

Creating a Node.js application

For this chapter, we will use a very simple and light Node.js application, which will be holding our example scripts. The main goal here is to be able to run each of the use cases individually and not have an entire web (client or server) application for each of them. This helps us to have a uniform base project.

1. The first step is to create your application's project folder. From the Terminal, run the following command:

mkdir <project-name>

2. Then, to initialize a Node.js project, run the init command in the root folder of the project. This will prompt a series of questions to generate the package.json file. You can fill out the answers you wish or just click on return to accept default values for the prompts:

cd <project-name>
npm init

3. Let's also install our beloved lodash to help us out with some of the trivial array and object manipulations and utilities:

npm install --save lodash

Use cases

Once your project is ready to go, we can now add the necessary scripts in the project's root and then run them independently.

Using recursion to serialize data

Recursion is a very popular programming paradigm in which a problem statement can be broken down into several smaller problems, which can be defined in terms of itself. Recursion is usually confused with divide and concur, in which the problem statement is broken into non-overlapping sub-problems which can be solved simultaneously.

In the following section, we will take a simple tree in which we have a root element followed by some child elements. We will be serializing this tree data, which can then be easily sent to the UI or persisted in the database.

Let's first create a folder called recursion within our project, which we created based on the preceding section. Then, we can create our serializer.js file within this folder, which will contain the class for serializing tree data.

Pseudocode

Let's formulate our algorithm in pseudo code before implementing the recursive serializer:

INITIALIZE response

FOR each node

 extract child nodes

 add current node info to serialized string

 IF childNodes exist

 repeat process for child nodes

 ELSE

 add ^...