Aditya Chatterjee's Blog, page 189

Algorithm to find Level of each node from root node

In this article we will be discussing on how to find the level of each node in a graph, the algorithm that we will be using to find the level of each node is breadth first search so if you are not familiar with breadth first search , I would suggest you to first go through this article:

Read about Breadth First Search (BFS)

then get back to this for better comprehension.

Level Of Each Node Using Breadth First Search

The above diagram summarises how breadth first search takes place in graph.

T...

How Email Systems Are Designed?

Through this article, you will get a good insight into "How Email Systems like GMail and Outlook Are Designed?". The key is to understand that email is a default way of communication on the web and is not same as a instant messaging platform.

As we know already, using email is a common way we communicate to other people usually for work, advertising, record of transaction, or some other purpose to communicate. Although there are lots of high-quality email providers out there such as Gmail, Outlo...

Counting subtrees where nodes sum to a specific value

We will learn about counting the subtrees in a binary tree whose nodes sum to a given value. We will be trying different methods to solve our problem We will solve it in O(N) time complexity and O(H) space complexity where N is number of nodes and H is the height of the tree.

Problem:

Let's say we need to find count of subtrees whose nodes sum to 11.In the example subtree,the whole left subtree's nodes sum up to 11 and the leaf itself is 11.So the total number of subtrees whose nodes added up t...

Algorithm to find all bridges in a Graph

In this article we'll be discussing on the algorithm to find all bridges in a Graph. Firstly we'll discuss on the Introduction to Bridges. Secondly, we'll understand the bridge concept with a graph example. At the end will write an algorithm & implementation for the same.

Following are the sections of this article:-

Introduction
Example for Bridges
Algorithm
Conclusion

1. Introduction

Consider a Graph(G) which is formed by Vertices(V) and Edges(E), an edge in a Graph(G) between vertice...

Algorithm to check if a linked list is sorted

A linked list is a linear data structure in which the elements are not stored at contiguous memory locations like arrays but they are stored in random locations in heap memory because the memory for each node of the linked list has to be dynamically allocated and these nodes are connected to each other by links or reference.

In this article, we have explored an algorithm to check if a given Linked List is sorted or not in linear time O(N). It takes constant space O(1).

Structure of a node of our...

Approximation Algorithm for Travelling Salesman Problem

In this article we will briefly discuss about the Metric Travelling Salesman Probelm and an approximation algorithm named 2 approximation algorithm, that uses Minimum Spanning Tree in order to obtain an approximate path.

What is the travelling salesman problem ?

Travelling Salesman Problem is based on a real life scenario, where a salesman from a company has to start from his own city and visit all the assigned cities exactly once and return to his home till the end of the day. The exact problem...

Concrete Problems in AI Safety

The problems of accidents in machine learning systems, that is defined as the unintended and harmful behaviour that emerge from poor design of real world AI systems.

These seem to come up in the following circumstances

When we specify wrong objective functions.
When we're not careful about the learning process.
When we commit machine learning related implementation errors.

In this article we shall explore a research paper titled “Concrete Problems in AI Safety” by Dario Amodei and others. This...

Word Break Problem

In this article we are going to talk about a very interesting problem which is frequently asked in coding interviews and programming competitions - the Word Break Problem.

We have solved the Word Break problem using:

Recursive approach
Dynamic Programming [O(N^2) time, O(N^2) space]

Problem Statement

In the problem we are given a string S and a dictionary of words,we have to determine whether S can be segmented into non-empty substrings of one or more dictionary words.(The words need not be un...

Check whether a Singly Linked List is Palindrome or not

A number is Palindrome if it reads same from front as well as back.For example,

2332 is palindrom number as its read same from both sides.

Linked List can also be palindrome if they have the same order when it traverse from forward as well as backward.

It can be done with using three different methods:

Using stack
Using string
By reversing the list

Using Stack:
Algorithm

Traverse the linked list and push the value in Stack.
Now, again traverse the linked list and while doing so pop the values...

Cycle in a graph using degree of nodes of the graph

There are different ways of detecting cycle in a graph. Let us understand how to detect cycles in an undirected graph using the degree of each vertex.

Introduction

Our objective is to check if a cycle exists in an undirected graph. What is a cycle ? A graph that has a number of vertices connected in a close chain, is said to contain a cycle or a loop.

Look at the graph below :

Fig. 1

There is a cycle formed by the nodes 0,3,1 and 5.

NOTE : Self loops are also considered as a cycle in the graph....