# 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

# 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