Tag Archives: computer science

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

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