Photography!

Well, I have had a DSLR for quite a while and have captured some good shots (caution : Beauty lies in the eyes of beholder). I have generally been averse to usage of Social media in general, but I guess I will start building up insta profile, because it helps remind me how far I have come. If you want to follow me, you can find me here :

https://www.instagram.com/ankurkkhurana/

Have a good day!

Advertisements
Photography!

Looks can be deceptive

I recently started playing chess online. Had two back to back matches where I was trailing behind quite heavily in terms of score (-8, -9), but managed to win!.

 

In Game 1 I offered a piece which opened my file directly to White King and the other guy took it. Since this was blitz and hence huge time pressure, I was counting on that mistake to happen!Screen Shot 2017-08-11 at 2.02.30 AM.png

I was even more pleased with myself in this game (and other guy should be equally displeased) since here also, I offered a rook on a platter and the other guy took it. Originally knight was on E7, I moved Rook to E7 and then black decided to kill it with its Queen. I moved my Queen from D4 to G7 and it was game over!

Screen Shot 2017-08-11 at 2.01.58 AM

 

Always assuming that other guy made mistake is somewhat costly. Happy Checkmating!

Looks can be deceptive

Hona tha pyar!

Well, this is not a post about my personal life but rather it is about the song that goes by the same name . “Hona tha pyar” literal meaning is “Love was bound to happen”!
It is a beautiful song sung by Atif Aslam , just like his other songs. This song has been in my head for almost since I first heard it and that was almost 6 years back. I have decided that I will practive for next 4 weks and try to play that song on guitar because I was listening to this guy some days back and I was really happy after listening to that. Now, I just want to play that.
I am going to keep this blog post updated through my journey wrt to the above. I am going to post every day progress in this tread with sound clips. It’s a bit challenging, but challenges are fun. Let’s get started, shall we ?

Day 1 :
Where do I currently stand?
I have owned a guitar for quite some time. I have played it in bits, sure, but have not got around to playing it regularly. I am touching my guitar now after a year and a half gap. So, I can assume that I do not know anything about.

What is the first step?
First things first, get my guitar checked out and see if it is in a working condition and that task, my dear fried, I have successfully completed. I got it serviced some time back and it sounds as a new one (better infact!) .First task bites the dust.

Found this link to be okay to follow for Chords :
http://www.guitaretab.com/a/atif-aslam/281598.html
Today, I was just trying to get the strumming pattern right.
Today’s progress :

Current Status : Day 1/30

Hona tha pyar!

Merkle Trees

Hi,

In today’s blog post I am going to discuss the Merkle trees, how they work and where they are used.

What is a Merkle tree ?

The leaf nodes in this tree represent data nodes where as the the nodes above them represent the cryptographic hash of the child nodes. It looks like this :

Let me explain a little bit about the anatomy of the above the above tree. The lowest nodes, marked as D1, D2, D3 and D4 are data nodes and can contain any data of your choice. Now that data is hashed and every leaf node is stored in a node representing the hash of data. e.g. in this case, Node Hash 0-0 contains hash of data D1, Node hash 0-1 contains hash of data of node D2, etc. you get the idea. Now this pattern continues till the top. Value of each node in the tree ,except the leaf nodes, is actually the hash of values of it’s children nodes.

In case the trees are being used to deal with security concerns for the data, cryptographic hash functions are used to hash the data. Cryptographic hash functions are those which are practically impossible to invert. e.g. to gain the input by looking at the output of hash function. Simpler version : They are one way only. Ideal crypto functions are quick to compute, make it impossible to find same output with two different inputs.  otherwise it is perfectly fine to use simple checksums on the data.

 

Use of the above trees :

  1. IPFS and ZFS file systems
  2.  BitTorrent protocol
  3. Git distributed revision control system
  4. Bitcoin peer-to-peer network
  5. the Certificate Transparency framework

and many more. The inspiration to write about merkle trees originally came from this paper about certificate transparency which I was reading a while back.

Let us examine a practical use of this kind of tree and for that we will look into how how zfs uses it. Since, folks who edited the wikipedia article have done a good job in explaining what I am trying to imply, let me directly quote

For ZFS, data integrity is achieved by using a Fletcher-based checksum or a SHA-256 hash throughout the file system tree. Each block of data is checksummed and the checksum value is then saved in the pointer to that block—rather than at the actual block itself. Next, the block pointer is checksummed, with the value being saved at its pointer. This checksumming continues all the way up the file system’s data hierarchy to the root node, which is also checksummed, thus creating a Merkle tree.

I came across this data structure recently and I found it a very interesting use of a very simple binary tree structure. If you find it interesting, Try implementing it yourself 🙂

It is said that money grows on tree, quite true in case of bitcoins 🙂

Merkle Trees

Immutable Var vs Mutable Val

In general, Immutable objects are considered better than mutable objects, most of the times (read almost all the time).  This stack overflow link explains it pretty well in case you want to know more.

Today’s blog post is about a very similar topic and pertains to situation where you want a data structure where you can to add more data over the course of execution of the program. Now how can you do it ? Well, there are two standard and straightforward ways by which you can do this :

  1. Create a immutable reference but mutable data structure.
    e.g.
    val mutableMap = new MutableMap()
    and if you are gonna add a object, you would do,
    mutableMap.add(Key, Value)
  2. Other option is to create mutable reference but immutable data structure.
    e.g.
    var immutableMap = new ImmutableMap()
    If you want to add an object here, this is how you will do it :
    immutableMap = immutableMap ++ Map(Key -> Value)
    It will always change the reference, but at any point, the object pointed by the reference will not change the object contents.

Can you tell me which approach is better ?

Option 2.

Why, you ask ?
Well, for one thing, if you are passing the above map as an argument to a method, would you want the map to change in between while it is being processed by the method? You can probably manage it by incorporating some more required changes in your code but those kind of changes are very hard to reason about.
It is also bad for readability and cohesion if you are going through the code and makes for some nasty bug and also reduces unit testability.  Even if you know what you are doing and if it is possible to go with option 2 with the way you are designing you class, you should always go with Option 2.
Just my two cents.

Immutable Var vs Mutable Val

Suffix Arrays – A simple Tutorial

Suffix Arrays

It is the data structure to look out for when you are going for string Searching and want to reduce the time complexity greatly.  So, Let us examine and start from basics.

What are Suffix Arrays ?

As simple as it can get , suffix arrays represent the rank of all possible suffixes of a given string .For example ,

String  S = “ABDCASD”

Then the suffixes for the string S (with the numbers in front represent are ,

7 $ *

6 D

5 SD

4 ASD
3 CASD

2 DCASD

1 BDCASD

0 ABDCASD

*$, A null character can be called a suffix of every string as it does no addition to the string itself . We will later on see why we chose to add NULL character to our algorithm . For NULL character that we used, we assume have highest lexicographic priority .

Now,

What happens when we sort those suffixes lexicographically ?

We get the order

Rank

Index from which starting

String

1

7

$

2

0

ABDCASD

3

4

ASD

4

1

BDCASD

5

3

CASD

6

6

D

7

2

DCASD

8

5

SD

So, the Suffix Array in our case will be ,

Suffix Array Index Sorted Suffixes (index of suffixes when sorted in lexicographic order )
1 7
2 0
3 4
4 1
5 3
6 6
7 2
8 5

Now let us take a different example and we introduce the concept of Lowest Common Prefix .

S=”abaabba”

Let us construct the Suffix Array for the above string first

Rank

Index

String

LCP

1

8

$

2

7

a

3

3

aabba

4

1

abaabba

5

4

abba

6

6

ba

7

2

baabba

8

5

bba

Now you see a column of LCP (lowest common prefix ) , what is it ?

So , What is Longest Common Prefix ?

 

It is the length of prefix that is common between the two consecutive suffixes in an sorted suffix array. To simplify , see this way , we have created an suffix array and we have ordered suffixes . We need to find out the number of consecutive characters common in the two suffixes (from starting of suffix).

e.g.

LCP of a and aabba is 1 .

LCP of abaabba and abba is 2 .

We put LCP in first column as 0 , always .

So , we get the following table :

Rank

Index

String

LCP

1

8

$

0

2

7

a

0

3

3

aabba

1

4

1

abaabba

1

5

4

abba

2

6

6

ba

0

7

2

baabba

2

8

5

bba

1

Why would I want to use suffix array ?

 

Well , They are extremely useful string searching , where text is limited and substrings to be searched are not limited . This approach is in contrast to KMP algorithm where there was one substring and you were given continuous stream of characters to search from.

Following is one out of the many important usages of the Suffix Arrays :

Finding Total Number of distinct Substrings.

Well how do we do this ?

We see that , any string , let us say

ABC will give following distinct substring ,

A

B

C

AB

BC

ABC

Which is equivalent to choosing an end point and a start point in a string, and what is left is a simple matter of finding the number of ways  you can choose a start and end point . Which is  nC2 (where n is the string length ) .

Problem happens when we have repeated characters . What will you do then ? that is when suffix arrays come into play .

Now if I am given a string , axyz , and let us say , I ask you how many strings can you make with this string such that they start from the first letter. Then the answer will be 4 ( a , ax, axy, axyz ) .

So , I have a string of length 7 , then I have 7 suffixes (excluding NULL , I am not counting it because it’s length is 0 , does not contribute towards any distinct substring ) . So , going by the above logic , I will 7+6+5+4+3+2+1 distinct strings , which is equivalent to  n+1C2  which was also the result of above discussion .

Unfortunately for us , this result doesn’t hold for the strings with repeated characters.

Take this one

S= “aabaab”

Suffix    Possible strings such that they start from first letter of suffix

b             b

ab           a,ab

aab         a,aa,aab

baab      b,ba,baa,baab

abaab    a,ab,aba,abaa,abaab

aabaab a,aa,aab,aaba,aabaa,aabaab

Now as you see strings a,b,aab,etc  are repeated but we also know that if we sort the above suffixes , those strings which are common , there length is given in Lowest Common Prefix .

So , the total number of distinct Substrings from a given string is given by

n+1C2 – Sum of All LCP

And that is the answer, as simple as that.

Problems Based on the above concept :

http://www.spoj.pl/problems/SUBST1/

http://www.spoj.pl/problems/DISUBSTR/

We will see more about the Suffix array and LCP implementation in the next part.

Please feel free to leave suggestions. Question are encouraged. Do not forget to comment  🙂

Adios ,

Ankur Khurana

Suffix Arrays – A simple Tutorial

Namaste

I welcome you to my blog, hope the time you spent reading it is well spent. I named this blog Grease Palm because, At one point or another, you always feel like that you are losing something, in terms of thoughts or worldly things. It is just my attempt to not lose those.Feel free to leave any feedback/suggestions on my blog. Hopefully, i will be blogging pretty much regularly.

You can connect with me on LinkedIn .

Namaste