Where have I been in the last one month? Yes. Same stuff, submission (just 1 this time though) and viva. But I think the buggy-ness quotient of this one submission was really high as compared to the other submissions that we have had. And yes of course my project report submission. Jeez… Documentation is a herculean task and by no means should be done at eleventh hour. But I never had documented any stuff and so creating the report really took the breath out of me. ‘Digging a well only when thirsty’ is definitely not a right way to quench your thirst. 🙂

As usual everything is done and I think was done well. But this week has been completely packed with some really important stuff for me. First on Tuesday we had Graduation day at the Akanksha center I volunteer for. This is a day when kids graduate from one level to next and demonstrate what they have learned in the present term. The kids were so enthusiastic about what they were presenting. It was fun attending it but at the same time it reminded me that I won’t be seeing them anymore as the center will be closed for summer holidays. I am sure gonna miss them 😦.

Second (n really important) was today I cast my first vote. I am really so happy and proud about this🙂. Thanks to my roomies (Trups, Shitu, Appulocks) for letting me know that we could register for voting in Pune even though we aren’t permanently residing here. Also special thanks to “Jaago Re! One Billion Votes”, the non-partisan national campaign launched by Janaagraha Centre for Citizenship and Democracy and Tata Tea for making it so simple to register for voting. So,

“Here we stand with a dot,

Proud that we added our tot 🙂

Us after voting

Us after voting

And finally now I think I will retire to studying something as the last important (??) thing this week is my end semester exam on Saturday. It’s high time and I should better start digging now 🙂

Advertisements

In our final year of engineering we are given the liberty to choose from a set of subjects as to be our “elective”. Now elective is a choice… It’s a choice you make based on what your interests are and you are “expected” to be interested in something which the college offers you. It is an altogether different issue that college always offers something boring and students are always never sure of what they are interested in and hence usually prefer to take a course wherein teachers don’t turn up.

Entering into my final semester of engineering I was sure of what my interests are but I was also sure college authorities wouldn’t have anything to offer that would interest me. But scrolling through the list put up at department notice board, I found a new offering. “Computational Biology”. The syllabus seemed interesting (it had algorithms). Most importantly it was going to be taught by people from the industry. I really appreciate people from industry who volunteer for teaching assignments. Taking time out of their busy schedule to interact with students is indeed commendable. Besides I have always being in favor of continuous interaction between academia and industry. Producers and consumers should always be in sync with each other. So I signed in for the course.

And so in my final semester of engineering I was admitted to a school.I experienced things which I last saw/felt in high school.

  • All the course instructors always come on time

  • Basically they never miss any of their allotted slots i.e. lectures take place as per schedule.

  • They are so enthusiastic about giving assignments and making us scratch our brains.

  • They actually read our answer sheets (they did. Believe me)

Of the many algorithms that we studied the ones which I found really interesting were pair-wise sequence alignment algorithms. One of the basic units in biology is DNA which is a sequence of 4 letters A, C, T, G. DNA defines us. It contains the code which makes us what we are. Now comparing DNA sequences from two different organisms is really helpful in deciding the relationship between organisms. It helps biologists conclude about any common ancestry amongst them to name just one.

Pair-wise sequence alignment can basically be of two types. The ones aiming at global alignment and ones aiming at local alignment. Calculating a global alignment is a form of global optimization that forces the alignment to span the entire length of all query sequences. An example of this is Needleman–Wunsch algorithm. By contrast to global alignments, local alignments identify regions of similarity within long sequences that are often widely divergent overall. Let’s consider Smith- Waterman algorithm which aims to align two sequences with emphasis on local alignment. Here are the basic steps in the algorithm along with an example.

Consider two DNA sequences: 1: ACTGAAGG

2: AATGGACTT

1) Decide upon match, mismatch scores (similarity measure, s (a, b)) and gap penalty.

Let us assume the match score to be 1. What we mean by this is,

s (A, A) = s (C, C) = s (G, G) = s (T, T) = 1, where s is similarity measure.

Let mismatch score to be – (1/3). What we mean by this is s (A, C) = – (1/3).

And gap penalty = 1 + k/3, where k = extent of gap. So for gap length =1, penalty = 1.3, for gap length = 2, penalty = 1.7 and so on.

Here I have decided these scores randomly. But these scores are usually decided keeping biological aspects into consideration. What we are technically doing by deciding these scores is deciding what our distance matrix is. In this example my distance matrix is:

A

T

C

G

A

1

-0.3

-0.3

-0.3

T

-0.3

1

-0.3

-0.3

C

-0.3

-0.3

1

-0.3

G

-0.3

-0.3

-0.3

1

2) Construct matrix.

Now in sequence alignment algorithms we create a matrix using the distance matrix. We write one sequence along one axes and other sequence along other axes. The rule in SW algorithm to fill up the matrix is as follows:

Set Hi, 0 = H0, j = 0 for 1 ≤ i n and 1 ≤ j m, where n and m are lengths of the two sequences under consideration. Then,

Hi, j = max { { Hi-1, j-1 + s( ai , bj )} , max1 ≤ k ≤ i {Hi-k, j – Wk}, max1 ≤ k ≤ j {Hi, j-k – Wk}, 0}. Here W is the gap penalty and the k is the extent of gap. Initially the matrix looks like (i.e. putting 0 in row 0 and column 0):

A

C

T

G

A

A

G

G

0

0

0

0

0

0

0

0

0

A

0

?

A

0

T

0

G

0

G

0

A

0

C

0

T

0

T

0

Now let’s fill up the matrix one element at the time from top left hand corner to bottom right hand corner (always moving from left to right) using the equation given above. Consider the cell containing ‘?’. The corresponding letter from sequence 1 is ‘A’ and that from sequence 2 is ‘A’. Hence substituting values in our equation we have,

H = max {{0 + s (A, A)}, {0-1.3}, {0-1.3}, 0} = max {1, -1.3, -1.3, 0} = 1.

Similarly we can fill up other positions in matrix. Here’s one more example: Consider row 4 and column 6. The letter in sequence1 is ‘A’ and that in sequence2 is ‘G’. So we have,

H4, 6 = max { {H3, 5 + s(A, G)}, max { (H4, 5 – 1.3) , (H4,4 – 1.7), (H4,3 ­ – 2)}, max {(H3, 6 – 1.3), (H2,6 – 1.7), (H1,6) – 2}, 0 }

= max {-0.3, max {0.1, 1,-1.6}, max {-0.6, 0.3, -1}, 0} = max {-0.3, 1, 0.3} = 1

Thus our final matrix is:

A

C

T

G

A

A

G

G

0

0

0

0

0

0

0

0

0

A

0

1

0

0

0

1

1

0

0

A

0

1

0.7

0

0

1

2

0.7

0.3

T

0

0

0.7

1.7

0.4

0

0.7

1.7

0.4

G

0

0

0

0.4

2.7

1.4

1

1.7

2.7

G

0

0

0

0

1.4

2.4

1.1

2

2.7

A

0

1

0

0

1

2.4

3.4

2.1

1.7

C

0

0

2

0.7

0.3

1.1

2.1

3.1

1.8

T

0

0

0.7

3

1.7

0.4

1.7

1.8

2.8

T

0

0

0.3

1.7

2.7

1.4

0.4

1.4

1.5

3) Trace- back

The next step is to trace a path in this matrix which will give us the optimal local alignment. The steps here are:

a) Locate the maximum element and start the trace from that cell.

b) Now check the diagonal (i-1, j-1), immediate left (i , j-1) and immediate top(i-1, j). Move to the maximum of these 3 and choose diagonal element in case of a tie.

c) Stop the trace when you reach a stage where a diagonal element is 0.

The trace path in the matrix is shown with bold numbers.

A

C

T

G

A

A

G

G

0

0

0

0

0

0

0

0

0

A

0

1

0

0

0

1

1

0

0

A

0

1

0.7

0

0

1

2

0.7

0.3

T

0

0

0.7

1.7

0.4

0

0.7

1.7

0.4

G

0

0

0

0.4

2.7

1.4

1

1.7

2.7

G

0

0

0

0

1.4

2.4

1.1

2

2.7

A

0

1

0

0

1

2.4

3.4

2.1

1.7

C

0

0

2

0.7

0.3

1.1

2.1

3.1

1.8

T

0

0

0.7

3

1.7

0.4

1.7

1.8

2.8

T

0

0

0.3

1.7

2.7

1.4

0.4

1.4

1.5

4) Alignment

This is the last step. Using the trace- back we have our maximum similar segment as:

–ACTGAA–

–AATGGA–

Our alignment has 4 matches, 2 mismatches and no gaps.

So this was about Smith – Waterman Algorithm. Thanks to my faculty and Swati (we usually end up fighting trying to figure out how things work before happily coming to a consensus) I hope I have got things right. Also here’s the link to the original paper by Smith which is very well written (and I don’t say that about every paper I go through) : http://www-hto.usc.edu/papers/msw_papers/msw-040.pdf.

I referred this paper and it has NW algorithm explained as well.


Its being almost a month since I last blogged. This being my first one since the beginning of 2009. The one thing which I dont understand about education system is why do academic year and calendar year dont start and end at the same time. Its new year and I am still in BTECH IT at COEP as was I last year. So many things in your life just don’t seem to change though there are people out there celebrating an entire new year!! I spend my new year eve with Anju, my childhood friend and her family at her home. She is one of my best buddies and its always a treat to spend time with her.They have been a family to me ever since I moved to Pune and it is thanks to them that I never feel I am alone in this city.

My BE project cum internship at NVIDIA keeps me busy enough that many a times I end up being in office sometimes even at weekends inspite of spending my weekdays almost entirely there. I had vowed that I will never spent weekends in office. Trups (my roomie since the first day at hostel) who was the sole witness to my “resolution” has gone at length to suggest that I rent a room near office to avoid commuting. Not that she cares about me hitting someone while being “activated” (which I actually did a few days ago) but more that she likes to remind me that I am a workaholic in a very tactful way.  And trust me as far as  “hitting” (pun intended) goes, it can be mutual as is certainly always in my case 🙂 .

But what better to start your new year than to be part of an amazing event which took place at my college auditorium.Each year we Microsoft Student Partners from Pune organise Developers Conference (DEVCON) , a day filled with technical sessions and fun for colleges in Pune. This year we had organised DEVCON on 18th Jan and the response was huge. More than 1000 students turned up from in and around the entire city. We organisers were indeed overwhelmed!!

The entire team had worked hard to make this event successful and we all were really happy with the turnout. Here are some pics:

Students lined up at COEP auditorium

Students lined up at COEP auditoriu

Packed Auditorium @ COEP

Packed Auditorium @ COEP

Quiz @ DEVCON

Quiz @ DEVCON

And yes finally here are we the MSP’s, the ultimate ROCKERS!!

Microsoft Student Partners, Pune

Microsoft Student Partners, Pune

( left to right)  Prachi, Manish, Ravikant, Shristi,Anuja, Dev, Awadesh, Piyusha, Abin,Dhaval , Sonali , Me,

( right to left) Rashi, Pradyna, Nikhil, Mayur, Aniket,Anand, Rahul, Ritesh.

There is no denying the important role education plays in our lives. One of the hindrances in India’s growth is illiteracy. I always wanted to contribute my bit in this regard but my studies and my work kept me from doing something for this cause.

One day I came across this add in TOI about “Teach India”. Herein you were required to spent just 2-3 hours per week teaching kids from less privilleged background. As soon as my exams ended I applied for it. Based on your preference of location, you are allocated an NGO with whom you get associated. I was allocated “Akanksha”. After an introductory session and an orientation session I was allocated a center where I could go and assist the teacher in teaching kids.

Wednesday was my first day as a volunteer.. I was excited but at the same time nervous!! Kids and me? I was always too disciplined. As kids, my cousins would never consider me as a probable accomplice in any of their plans. (My brother has long given up attempts to bring some disorder in me!!) Not that I don’t deal with people at all. I have been part of various teams right from school, heading them most often. But this was different. Kids belong to a different world altogether. A world where there is no limits to imagination, where innocence prevails to an extent that even absurd questions are asked in a plain way!!

I was right on time at the Akanksha Centre. Soon a marching brigade of kids in Akanksha t-shirts arrived. The teachers at the centre made sure that the kids walked in the centre in a line. As soon as we entered the center the kids occupied their predefined seating positions. The teacher announced my presence and it was amazing to see that the class rules were explained one by one by the kids themselves.

The teacher then told me that we would start by playing a game called “Hot seat”. She said this is how kids would know me. As per the game, kids would ask me questions and I would answer them. And trust me there stood Shaiz completely stumped!! Shaiz who never minds going in first for vivas, Shaiz who never prepared for her interviews was stumped by the questionaire of mere toddlers!! “So why do you like red?” “Are you married?”. On being asked “which is your favourite story?” I couldn’t think of any other than Rowling’s Harry Potter series to which their answer was “Most of the didis like the same one..we already know it!!”

Dealing with kids is by no means an easy task. I knew this beforehand but experienced it as well!! What amazed me the most was the enthusiam of the teacher at the center. Her liveliness and the personal attention she was giving to each of them kept them all interested in what was happening in the class. We taught the kids prepositions and some basics of computers.

All in all it was a very different experience for me. I really am looking forward to interacting with the kids next week!!

The time I saw him I was bound to fall in love. Such an amazing behavior!! Such a consistent performance!! Unbeatable, I told Swati. She was still scrutinizing him (No, he is not an athlete).This post is about my very first love.

I am a computer science engineer (There you raise your eyebrows.) I mean I am positive I will be one in about 7 months. I don’t believe in fuzzy logic (as of now.. Life has taught me ‘never say never!’). I don’t think I can have a crush. Either I am in love, or I am not. And yes. This was for sure love.

He is a Heap. Oh you never heard of him? Or if you did you think he is not friendly? Oh no. He is the most friendly data structure around. Arrays, link-list no one comes even close to performance that Heap offers. So wanna know more about him? Read on.

Heap data structure is an array object that can be viewed as a nearly complete binary tree. (The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point) If heap is an array object then what makes it different?? There is an interesting property that differentiates a heap from an array and that it is: key stored in parent node should be less than the key stored in any of its children. This is an example of a min-heap. Heaps are two kinds, min-heaps and max-heap. Max-heap being one in which the parent has key value greater than the any of its children. Here’s an example:

Max-Heap

a)Max heap viewed as a binary tree b) Max heap in its array representation

(Each node with two children)

Any data structure is judged by the asymptotic complexity involved in various operations that we perform on it, which includes create, search, insert, delete. Let’s analyze each of these in turn.

Create:

Consider that we are building a max-heap (binary). Our input is an array with arbitrary elements and we ought to make sure that the ‘heap property’ is valid i.e. each parent node holds a key greater than any of its children (in this case 2 children). Now if we observe in the diagram above parent nodes / internal nodes begin from position 5. Given n nodes/elements, internal nodes begin at array position n/2. (Assuming array indexes start from 1. If we take this to be 0, this will change to (n/2-1)).

Now to create heap all we got to do is start scanning the array from the last internal node (index =n/2) to index 1 and check if ‘heap property is satisfied or not. Anytime we find that the heap property is violated we ought to swap the nodes. Here’s a pictorial representation of this procedure:

Creation of max-heap

A: initial array a) 16 compared with 7, no swap. b) 2 compared with 14 and 8, the larger node 14 is swapped with 2. This ensures heap property is not violated as 14 >8. c) 3 and 10 are swapped. d) 1 and 16 swapped e) 4 and 16 swapped f) the final max-heap.

The asymptotic complexity of building heap is O (n).

Insert:

To insert an element into the heap just place it in the next empty array location and let it bubble up the tree till heap property is not satisfied. Since height of heap (in binary tree representation) is O (log n), complexity of insert is O (log n).

Delete:

Deleting a leaf from heap is straightforward. When it comes to deleting an internal node, replace it with the larger of its two children and continue this down the tree. Again since height of heap (represented as binary tree) is O (log n), complexity of delete is O(log n).

Search:

Searching the heap is O (n) i.e. you can search a heap in linear time as you do in arrays or link-list.

Heaps have huge applications in numerous algorithms cause of their property to give the minimum /maximum of a set of elements in constant amount of time (O(1)).If you have observed carefully in a max-heap we always get the largest element of the array in array index 1. So we can use this property to sort numbers as follows:

1)Form heap from n input elements: O(n)

2)Delete the element at array index 1 (this is the largest element) : O(1)

3)Adjust the heap with n-1 elements. O (log n). (As we saw above deleting an element and readjusting heap is O(log n))

4)Repeat from step 2 till 1 element is left in heap.

This is my favorite sorting algorithm. It is called the Heapsort and it is an optimal sorting algorithm. The overall complexity of this algorithm is O (n log n) cause we adjust the heap n times (after deleting element at array index 1 to get the largest in present set).

So this was all about Heap. Trust me once you know him well you really can’t stop falling in love with him!

Yes……Shaiz is Activated!! Not long ago, ie approximately for 2 months I was completely grounded.Reason : Submissions and exams.But now I am so relieved. My exams are over and though I am not completely free (my NVIDIA internship is back in full swing) atleast I am not completely tied up.

One really important developement in my life right now is my parent’s gift on my 20th birthday. They gifted me a Honda Activa.Jeez! She is cute and fast. And she really has put my life in the fast lane. So here I stand fully “activated” thanks to my dear parents.

My bike

My bike

Last 15 days of my life have been really hectic, both mentally and physically.

I had been home for a week for our yearly Diwali Bunk.Home is where I love to get back to. This trip back home was not planned.It was all of a sudden (not that most of my trips back home are planned), but this one was completely unplanned. And I think as a consequence of this I ended up exhausting myself so badly that I caught high fever and cold all of a sudden and I was in bed almost till I left. I dont remember the last time I slept so much ( almost 5 days in a row). That was how the first week was spent.

There comes a time (in each semester) in an “to be” Engineer’s life when he has to write silly things and put them down in a file, when he has to answer silly questions. Yes…. I am speaking about submissions and vivas.Submissions are always a hectic activity “for me”.  Here “me” is emphasized cause of two reasons:

1) I dont believe in putting borrowed things in my file. If something has got my name it should have a standard and like to maintain one myself.(Though Swati’s contribution cannot be denied and she shares my passion for a standard.). No matter what we make sure we do our programs ourselves and dont depend on some magical printer to print them out for us.

2) I am an Engineer (yes yes.. to be) and I dont do things regularly, hence end up with lots of load in the end.

But with all the missed lunches (for I never miss my dinner) and insomniac nights, I am finally done with my submissions.

So that was what I was caught up with and which kept me from blogging. But well this post primarily is about something else. In my state of semi-consciousness back home I finally found time to finish the book which I was reading for a long time. “IT happened in India” a biography of Mr Kishore Biyani, owner of popular shopping centres like “Big Bazar”, “Central”, “Pantaloons” and so on. Biographies are definately not my cup of tea  and hence I took time to finish this one.

In this book KB (as he is called) sketches his entire journey from being a simple fabric dealer to being the “Raja of Indian Retail Industry”. One of the most striking things about this man is his beleif in the Indian way of doing things. His decisions, actions all are influenced by Indian values and Indian way of life. The efforts which KB takes to understand the Indian consumer are indeed tremendous. He spends his sundays watching people shop, just to understand what they desire and the new trends that emerge in the way they shop!!

Rewrite rules Retain values…Isnt it an amazing statement? Yes KB believes in it and his this beleif made him what he is today. His simple background didnt stop from achieving what he has acheived till date and hence goes the title “IT happened in India”. For me this book just reinforces my beleif in the power of being an Indian. Yes I think I am really blessed to be one. The kind of environment I have grown up in gives me a very unique way to look at things and take decisions.In all if biographies dont bore you this book is worth a read. Big Bazar definately is going to get a visitor soon…