An Online Algorithm to Check for Bipartite Graphs

Bipartite Graphs

A graph \(G(V, E)\) is called bipartite if its vertices can be divided into two groups \(X\) and \(Y\) such that every edge connects one vertex from \(X\) and one vertex from \(Y\). The graph drawn below is bipartite.

Given a graph, can you determine if it is bipartite? Continue reading An Online Algorithm to Check for Bipartite Graphs

How Game of Thrones Should Have Ended

This is a very unusual post for this blog. I hope my regular readers will bear with me.

I love Game of Thrones. I have read the books and the companion novels. I have been following the series for years. I am familiar with most of the fan theories too. Tonight the series finale aired. I didn’t like how the show ended. It felt rushed and very baffling. Continue reading How Game of Thrones Should Have Ended

A Blind Robot Beside an Infinite Wall

Let’s think about the following problem:

Consider a wall that stretches to infinitely in both directions. There is a robot at position \(0\) and a door at position \(p\in\mathbb Z\) along the wall \((p\neq 0)\). The robot would like to get to the door, but it knows neither \(p\), nor the direction to the door. Furthermore, the robot cannot sense or see the door unless it stands right next to it. Give a deterministic algorithm that minimizes the number of steps the robot needs to take to get to the door.

This problem quite famous Continue reading A Blind Robot Beside an Infinite Wall

Prime Counting Function and Chebyshev Bounds

The distribution of primes plays a central role in number theory. The famous mathematician Gauss had conjectured that the number of primes between \(1\) and \(n\) is roughly \(n/\log n\). This estimation gets more and more accurate as \(n\to \infty\). We use \(\pi(n)\) to denote the number of primes between \(1\) and \(n\). So, mathematically, Gauss’s conjecture is equivalent to the claim

\[\lim_{n\to\infty}\frac{\pi(n)}{n/\log n}=1\]

Continue reading Prime Counting Function and Chebyshev Bounds

Multiplying Two Polynomials with Fast Fourier Transform

Polynomial multiplication is one of the most important problems in mathematics and computer science. It can be formally defined as follows:

You are given two polynomials roughly of equal size\[A(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1}\]\[B(x)=b_0+b_1x+\dots+b_{n-1}x^{n-1}\]find a polynomial \[C(x)=c_0+c_1x+\dots+c_{2n-2}x^{2n-2}\] such that \(A(x)\cdot B(x)=C(x)\). At first, this may look like an easy problem, Continue reading Multiplying Two Polynomials with Fast Fourier Transform

No form of beauty is as flawless, as abstract, or as perennial as the mathematical beauty that derives from unassailable logical perfectness, for a mathematical proof is not earthly science, but a poetry written in logic.
[ –Adib Hasan 😛 ]

Generating All Subsets of Size k in Python

 

Suppose you are given a set \(S\) with \(n\) elements and you need to generate every subset of size \(k\) from it. For instance, if \(S=\{3,4,5\}\) and \(k=2\), then the answer would be \(\{3,4\}\), \(\{3,5\}\), \(\{4,5\}\). So, how would you do that in Python?

First of all, this is a really simple exercise. Stuff like this often comes up when someone writes a moderately large script. I wanna talk about this one in particular because it has a combinatorial solution. Continue reading Generating All Subsets of Size k in Python

Lie Detectors and the Story of Halting Turing Machines

 

Is it possible to design a machine that detects lies? Sure, people have already built devices called polygraphs that monitor blood pressure, respiration, pulse etc. to determine if a person is giving false information. However, that is not same as “detecting lies” because polygraphs merely measure physical effects of telling lies. On the top of that, they are hella inaccurate. I am talking about REAL lie detectors, ie. machines that can instantly validate the statements themselves. Can we actually make such machines? (*insert new startup idea*) Continue reading Lie Detectors and the Story of Halting Turing Machines

ভোরের কুয়াশাস্নাত রোদের আঁচল
লুকিয়ে রেখো আমার কিছু ব্যর্থতা।
অর্ধরাতের জন্য পুরোনো জৌলুশটুকু বড্ড প্রয়োজন।
আজ আমার মন ভাল নেই।