A cute and easy algorithmic riddle.

You have an array of N bit strings each of length M. You know that there is at least one element that appears more than N/8 times in the array. Using O(M+log(N)) memory and O(NM) time, find such an element.

An Easier Version

Well, its actually almost exactly the same, but solve the above riddle in case there is an element that appears more than N/2 times in the array. I managed to find 3 distinct solutions to this easier variation, but only one of which generalizes easily.

Thanks Nemo for giving me this riddle!

Dany Valevsky gave me this very cool riddle.

You are given a vector of size N, the elements of which are numbers in the range 1,…,N-1. I.e. there is at least one repeating element. Give an algorithm that finds a repeating element (it does not matter which one, in case there are several) with O(N) time complexity and O(1) memory complexity.

NOTE - the time and memory complexities are calculated in integers. I.e. the input is of size N, not N*logN.

(more…)

 In this post I will define turing machines and demonstrate a simple one in action.

(more…)

 I recently watched this interesting video by Shai Avidan and Ariel Shamir from MERL. They developed an extremely cool image resizing technique called seam carving. They explain all about it in this article.

One of the coolest things about their idea is that is it easy to implement. I implemented a semi-optimized version of their algorithm in a couple of hours of coding. All the images in this post were generated by my code.

(more…)

When I started yaniv.leviathanonline.com, I declared it to be a site about “Mathematics and Hacking”. As of now, most of its content is Mathematical. I thought it was time for a little change…

(more…)

 Hi everyone!

As you may have noticed, yaniv.leviathanonline.com has not been updated for a while (exactly one month, pour être précis). This was largely due to my intense exam period.

(more…)

This article is the first among a series of articles describing the subject of Secure Computing. The material was mainly taken from a Cryptography course by Amos Fiat.

(more…)

In 1998 (I can’t believe it was so long ago!) I was working at MATE (Media Access Technologies), an Israeli start-up at the time, specialising in face recognition and video searching. It was then that I came to know one of the coolest tricks in image recognition - the Hough Transform (pronounced “huf transform“).

(more…)

A few years ago a friend of mine asked me the following Perl riddle. Unfortunately, in order to solve it you must know Perl. As I like Python much better, I translated the riddle to Python. Attached are both versions.

I admit the Perl version is a bit more cryptic and if you know both Perl and Python you should try to solve the Perl version (but use Python for everything else in life ).

Oh, and try to solve the riddle without running it (run it only as a last resort).

perl -wle 'print "True" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number]

python -c "import sys, re; print None == re.match('^1?$|^(11+?)\\1+$','1'*int(sys.argv[1]))" [number]

To alleviate all doubt – [number] denotes a numeric command line argument (e.g. 17).