Aditya Chatterjee's Blog, page 188

Check if file exists in Python

In this article, we have explored different ways to check if a file exists in Python. We have explored 6 different methods to do so in Python:

try catch block
isfile()
isdir()
exists()
pathlib
os.listdir()

Files are used to store information.They have path which determine the location of the file.There are 2 types of paths

Absolute Path
Relative Path

Absolute Path:

It is the file path which determines the location of the file starting from the root folder of the file system.

Example:

Lets sa...

Understand Randomized Algorithms once and for all

Randomized algorithms use a certain amount of randomness as part of their logic. And counter-intuitively, the randomness can actually help us solve certain problems better than we could have otherwise! In this post, we discuss what randomized algorithms are, and have a look at the Solovay-Strassen Primality Tester to see what they are like.

Introduction

Randomized algorithms use a source of randomness to make their decisions. They are used to reduce usage of resources such as time, space or memo...

NP Complete Complexity

In this article, we have explored the idea of NP Complete Complexity intuitively along with problems like Clique problem, Travelling Salesman Problem and more. In simple terms, a problem is NP Complete if a non-deterministic algorithm that be designed for the problem to solve it in polynomial time O(N^K) and it is the closest thing in NP to P.

All problems cannot be solved in polynomial time complexity (like O(N^2)). For example, Alan Turing's famous halting problem cannot be solved by any compu...

Strategy to win Minesweeper

Many may think Minesweeper is a random game but it is infact a strategy game and you can win it everytime if you know the rules involved in building it and the proven strategies to play Minesweeper.

From a computational point of view, this is an NP-Complete problem that is it will take a Computer exponential number of steps to calculate the winning move in a Minesweeper of a given size. Note that it is possible to win always but it will take some time.

Minesweeper is a very popular single player...

C program to check whether brackets are Balanced in an Equation

This problem is one of the standard use case scenario when learning or practicing Stack as a Data Structure, if we are familiar with the basic operarions with stack like push() and pop(), this problem can be solved very easily. All we need to know is that for every opening bracket there needs to be a closed one.

Example:

Input: (a+b)(a-b)
Output : Balanced

Input : ((a+b)(a-b)
Output : Not Balnced

Solution Approach

The two main operations of a Stack Data Structure i.e Push() and Pop() are us...

Hospital Residents Problem

In this article, we introduce and discuss an algorithm used to match residency applicants to their most preferred programmes. This problem is called the 'Hospital Residents Problem'. The algorithm used is a slight variation of the Gale Shapley algorithm. You can also check this article on Stable roommmates problem

We have two groups: Applicants and Programmes.

Each member of the group will have a choice list. All the hospital programmes will release a choice list of the preferred applicants and...

Maximum cut problem

In this article we'll be discussing on the concept of Maximum cut problem. Firstly will understand its basic concept with Introduction. Secondly, with a graph example will deep-dive into the concept. Later we'll discuss an interesting way of finding solution with Algorithm. Lastly we'll conclude the article with application of the same.

Following are the sections of this article:-

Introduction
Example for Maximum Cut
Complexity Class
Algorithm
Conclusion

1. Introduction

Let us discus...

Find articulation point in Graph

In this article we'll be discussing on how to find articulation point in Graph. Firstly we'll discuss on the Introduction to Articulation Points. Secondly, we'll understand the Articulation Points concept with a graph example. At the end will write a Pseudo code & implementation for the same.

Following are the sections of this article:-

Introduction
Example for Articulation Points
Pseudo Code and Implementation
Time and Space Complexity
Conclusion

1. Introduction

Consider a Graph(G) ...

Number of substrings in a string divisible by 6

Given a string of integers, find the count of sub-strings of given string which are divisible by 6. This problem can be solved using Dynamic Programming in O(N) time complexity where N is the length of the string.

For example 1.

Input: "68412" Output: 6

Explanation: Since 6, 84, 12, 684, 8412, 68412 are the only substrings which are divisible by 6.

Example 2.

Input: "350648" Output: 6

Explanation : 0, 6, 48, 648, 5064, 35064 are the only substrings which are...

Algorithm to detect and remove loop in a Linked List

Problem Description: Given a Linked list, find out whether it contains a loop or not. If it does, then remove the loop and make the last node point to NULL.

In a linked list, a loop is encountered when the last node points to any node in the linked list instead of pointing to NULL.

For eg:

To solve this problem, we need to follow these 2 steps:

Detecting whether a loop is present or not.
Removing the loop.

Detecting a loop in Linked List :

The fastest method to detect a loop in a linked list ...