Java Tidbidz 1: Access modifiers, Arrays

• Access Modifiers - All members of interfaces are implicitly public. It is, in fact, a compile-time error to specify any access specifier for an interface member other than public (although no access specifier at all defaults to public access).

• Array - Arrays are special objects in java with no "class definition" (no .class file).

• Array.length [public final int variable], but String.length()

Java tidbidz 2: Abstract class and Interface

• Interface variables static and final by default [interfaces cannot be instantiated in their own right; the value of the variable must be assigned in a static context in which no instance exists. The final modifier ensures the value assigned to the interface variable is a true constant that cannot be re-assigned by program code.]

• We can have abstract class without abstract method but not abstract method in non-abstract class, because declaring a class abstract only means that you don't allow it to be instantiated on its own, while an abstract method must be defined by subclasses.

• You can even have abstract classes with final methods but never final classes with abstract methods.

Detect and identify cycle in linked list

Tortoise-Hare Algorithm illustrated -

Detection:
The classic Tortoise-Hare algorithm (Floyd Cycle Detection) requires two pointers, one fast (Hare or H) and a slower (Tortoise or T). Start both of them from the same (head) node and run the Hare twice as fast as the Tortoise. Clearly, they will meet at some point if there is a cycle. So far so good, very clear and intuitive.

Identification:
Let's assume that the singly linked list is represented as x = {x(0), x(1), ..., x(z)}. It has a cycle of length n starting at node x(m). T and H meet at node x(k), which is i distance away from start of the cycle. [For simplicity, I am eliminating obvious assumptions like, i <=n, k>=m, etc).

As H is twice as fast as T, by the time T crosses k nodes, H will traverse 2k nodes. Hence, we can write the following equations,

For T: k = m + i
For H: 2k = m + n + i
=> 2(m + i) = m + n + i
=> m =n - i

Based on this observation, T is restarted from the head or x(0), and both T and H are moved at the same speed of 1 node per time.
You will see that they ALWAYS meet at start of the cycle. This is because, by the time T crosses m nodes to reach x(m), H will now also cross m nodes. But H is moving in the cycle. So, it will cross, remaining (n-i) nodes of cycle (as it was at node x(k), where k = m + i) and reach the beginning of the cycle, x(m). But hey! (n-i) is actually m! So, H has just crossed m nodes, and will stop at x(m), where T has just reached :)
Thus, we know where the cycle starts.
The reason I wrote this blog is because the usual descriptions of this algorithm just tells you to restart T from head and move them at the same speed without this little description (which can be intuitive for many). But I felt the need of explaining the reason.

The rest is simple. Keep either T or H fixed at x(m), move the other till it reaches the fixed pointer again. The number of nodes traversed is length of the cycle.

Java TidBidz 3: Final Vs. Finally Vs. Finalize

http://javarevisited.blogspot.com/2012/11/difference-between-final-finally-and-finalize-java.html

Realizing that it's time for the dissertation dread

Well, it is this time of the life again. I am thinking of graduation, and thinking very hard. So hard that I can say "I am graduating this year". So here comes the most crucial phase of my PhD - the dissertation.

I have started working on my PhD thesis (I like calling it thesis too) sometime back, but never did I realize it so evidently and obviously that it is that very period of my PhD. It is the final stage, and I have read so much about it already. Starting from PhD Tips, Time Management for Dissertation, Secrets of Successful PhD Students, What They Don't Tell You, How to Write a Good PhD Dissertation, I never missed PhD Comics, GradCafe, How to Improve your Concentration, Resume and Thesis-writing workshops. I attended seminars not only in my own department, but in other departments and watched research-talk videos online - all keeping my overall research growth in mind, which is supposed to converge concisely in my thesis. I devoted considerable amount of time, thought, anxiety and finally panic on my dissertation. Now I am in a stage of actually working on the dissertation dread and getting the actual thesis out of the mess.

Yes! That's a very important thing. My thesis is there, somewhere at the back of my mind, hear soul, knowledge, library, internet and ofcourse, my supervisor. I now realized that I need to cultivate it.

I'm in this phase where I am writing publications parallel to my thesis. I am reading a lot and thinking even in my shower or while driving (well, not that I suggest that to anyone). I will be posting more often here, as I ride this tide.