# A Week of Poetry: Day 1

I love poetry. Did I ever tell you that? Not really.

I also enjoy world-building, philosophy, travelling to new places, but I never write about any of my experiences. I don’t write about myself much.

Twenty years later, Continue reading A Week of Poetry: Day 1

# 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$

# 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.

# 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

āĻ­ā§āĻ°ā§āĻ° āĻā§ā§āĻžāĻļāĻžāĻ¸ā§āĻ¨āĻžāĻ¤ āĻ°ā§āĻĻā§āĻ° āĻāĻāĻāĻ˛
āĻ˛ā§āĻāĻŋā§ā§ āĻ°ā§āĻā§ āĻāĻŽāĻžāĻ° āĻāĻŋāĻā§ āĻŦā§āĻ¯āĻ°ā§āĻĨāĻ¤āĻžāĨ¤
āĻāĻ°ā§āĻ§āĻ°āĻžāĻ¤ā§āĻ° āĻāĻ¨ā§āĻ¯ āĻĒā§āĻ°ā§āĻ¨ā§ āĻā§āĻ˛ā§āĻļāĻā§āĻā§ āĻŦāĻĄā§āĻĄ āĻĒā§āĻ°ā§ā§āĻāĻ¨āĨ¤
āĻāĻ āĻāĻŽāĻžāĻ° āĻŽāĻ¨ āĻ­āĻžāĻ˛ āĻ¨ā§āĻāĨ¤