Left to Right binary exponentiation

I did study this algorithm last year when I took my advanced algorithms course but I always missed the forest for the trees.

It is said that left to right binary exponentiation is faster than naive multiplication. For example, x^108 = x*x*x.... (108 times), now, that's 108 multiplications.

A wee bit faster technique is left to right binary exponentiation. x^108 = (x^54)^2 = ((x^27)^2))^2 = ((x* (x^13)^2)^2)^2 and so on.  Apparently, this achieves the same result in logN multiplications, more precisely, 5. I wondered what sense it actually made and I was always told that squaring was not to be treated as multiplication. In technical terms, I thought squaring was just as computationally intensive as multiplication. In software terms, I was right but I was wrong otherwise, in hardware respect.

Actually, squaring a number is equivalent to a 1 bit left shift of its binary representation. That can be achieved using bit shifters and that's where the speed up is achieved. This is programming in such a way so as to exploit hardware capacity.

Where Algorithmic Complexity is not a function of the number of loops

When we take a look at the above algorithm, we can see that there is an outer loop that runs from 1 to n, where n is the number of vertices. For each vertex, i, the algorithm calls DFS routine if i is not explored yet.

Here, the outer loop runs n times, and each inner loop examines on an average of the order of n vertices, but that said, the algorithmic complexity is not O(n^2).

While that may be how it looks like, on closer inspection, we can see that the outer loop doesn't invoke the DFS subroutine if the vertex i is already examined. So, here, for the cases where i is already explored, the work done by the outer loop is in fact, O(1). 

So, for example, the complexity is more like O(n/4) + O(n/2) + O(n/8) +  O (n/8) + m * O(1) which is O(n) or linear.

BFS for Undirected Graphs

Both BFS and DFS may be used to compute connected components of an undirected graph. 

BFS

Here, s is the source vertex.  We use a queue and put s into it. Remove s first, mark as explored and insert into it a and b when we remove s. Recall that we can use an adjacency list to maintain a list of neighbours of a given node. Let us assume, a is put in first and then b.

Queue state: a,b

Now, a is taken out, marked as explored and it's adjacent nodes, c,b,s are inserted back into the queue. Queue : b,c,b,s

Take out b, mark b as explored and put it's adjacent nodes, a,c,d,s into the queue.

Queue state: c,b,s,a,c,d,s

Take out c, mark as explored and put it's neighbours, a,b,d,e into the queue.

Queue state: b,s,a,c,d,s,a,b,d,e

Take out b. But b is explored so simply proceed to the next queue element.

Take out s, s was the first item to be explored. So go on to the next element.

Take out a, explored so proceed.

Take out c, explored so proceed.

Take out d, unexplored, so mark as explored and put it's neighbours, b,c,e into the queue

Queue state: s,a,b,d,e,b,c,e

Take out s, explored so proceed.

Take out a, explored, move on.

Take out b, explored, move on.

Take out d, explored, so move on.

Take out e, unexplored, mark as explored and put it's neighbours c,d into the queue.

Queue state: b,c,e,c,d

Take out b, explored, move on.

Take out c, explored, move on.

Take out e, explored, proceed.

Take out c, explored, so proceed.

Take out d, explored, proceed.

Queue is empty. BFS completed.

Abstract classes and Interfaces

Both abstract classes and interfaces facilitate polymorphism but we see their differences here and then move on to examining valid use cases for each.

1. Abstract classes may not be instantiated, this for a fact, holds true for interfaces as well.

2. Abstract classes may have implementations for some of their methods, but interfaces have no method implementations at all.

So, that's essentially one difference only. But this critical difference also governs their suitability and applicability in programming contexts.

1. Use abstract classes if you anticipate some level of versioning for your components. To explain briefly, if you anticipate that your implementations will all have newer features tomorrow, use an abstract class for it may be updated to correspond to the newer functionality. Interfaces, on the other hand, once created cannot be updated and you will have to create a whole new interface.

2. Use abstract classes if you believe there will be some level of identical functionality among all implementations of your component. This is because, the common functionality may be implemented in the abstract class method  whereas, interfaces do not support any implementations at all.

3. It's a good idea to use an abstract class to provide common functionality among all implementations of an interface. One manifestation of this idea lies in the abstract classes of  Java Collections. 

HTTP Get and Post Methods

Use Get only for safe and idempotent operations. Safe operations are those which do not update a state, for example, a database table. Idempotent operations are those which return the same result no matter how many times you call them. 

It's evident that Get is suitable for retrieving the result of a query and in this regard, similar to a SQL select.

Use Post where the operation is neither safe nor idempotent. For example, imagine you want the client to register on your registration page. Here, if the registration succeeds, a new entry will be added to the database table. In this case, of course, the state is being modified and a Post would be the better thing to do. We can see that such registration operations are not idempotent either. While it is true, that the system would not permit a user to register with the same credentials over and over again, this is a business logic concern. In theory, a database would not disallow two objects to have identical values. We can see that a Post is similar to a SQL insert.

There is also a Put operation that is suited to unsafe operations that are idempotent but I will not discuss that here.

As for other differences, a Get causes the url to bear the entire query and as such not suitable for transmitting sensitive data like passwords. In contrast, the query is transmitted invisibly with Post, so it may be used to safely transmit passwords and other information that require some element of confidentiality. There is also a limit to the amount of data that Get supports. There is apparently, no such limit for Post request.

Randomized selection to return the i'th order statistic

Suppose you have an unsorted array of size N and that you want to determine the ith order statistic for the same array. This is nothing but the ith smallest element in the array. While a simple way to do this would be to sort the array using an efficient sorting technique like say merge sort in O(NlogN) and then return the element in the ith position in O(1) time, apparently, there exists a much faster algorithm to achieve the same end. It's called QuickSelect.

int quickSelect ( int[] a , int lb , int ub , int i ) throws Exception {

if ( lb >= ub )

throw new Exception ("invalid i");

p = partition ( a , lb , ub );

if ( p > i )  //look to the left

    quickSelect ( a , lb , p-1 , i );

if ( p < i )  //look to the right

    quickSelect ( a , p + 1 , ub , i - p );

if ( p == i )

    return a[p];

}

Now, what is randomized here is the selection of the pivot in the partition routine. The pivot for this pass of the quickSelect is chosen randomly among ub-lb elements of the array and the partitioning is done around this pivot.

The difference between quicksort and the quickselect routine is that while quicksort recursively applies the partition toboth halves of the sub-array, quickselect determines which side of the pivot the ith order statistic resides and applies the recursive routine to only that side of the sub-array.

T(n) = O(n) + T(n/2)

While this may be suggestive of O(nlogn), it is not. It reduces to 8cn which is in fact O(n).

QuickSort Variants

QuickSort is a rather well-known sorting algorithm and for many reasons I think it is also fairly deceptive. There are several variants of it and I think each one is interesting in its own right.

Version 1

void quickSort ( int[] a , int lb , int ub ) {

if ( lb >= ub )

    return;

int pIndex = partition ( a , lb , ub );

quickSort ( a , lb , pIndex );

quickSort ( a , pIndex + 1 , ub );

}

int partition ( int[] a , int lb , int ub ) {

int pivot = a [ ( lb + ub ) /2 ];

int left = lb;

int right = ub;

while ( left <= right ) {

          while ( x[left] < pivot ) 

                    left++;

          while ( x[right] > pivot )

                    right--;

          if ( left <= right ) {

                    int t = x[left];

                    x[left] = x[right];

                    x[right] = t;

                    left++;

                    right--;

          }

}

int p = right;

return p;

}

Note: This one does work but note that for some inputs, the split may not be precise. Example: Consider the case where 8,4,1,7,6,2,3,5 is input and 1 is chosen as the pivot first. After 1 pass, 1 would be in its right position, but say 7 is chosen thereafter. Here, in the subsequent pass, 7 will be in its appropriate position but the implementation passed the sublist 7,8 yet again. While this may not incur significant performance penalty, it's worth a note.

Version 2: Canonical QuickSort

int partition ( int[] a , int lb , int ub ) {

int pivot = a[lb]

int i = lb+1;

for ( int j = lb+1; j <= ub; j++ ) {

if ( a[j] < pivot ) {

    swap (a[i], a[j]);

    i++;

}

swap ( a[lb], a[i-1 ); 

}

What I did like about the canonical version was its inherent simplicity. It also makes apparent that each partition has a computational complexity of O(n). As for a counter example for this one, there isn't.

Version 3: Another canonical scheme

int partition ( int[] a , int lb , int ub ) {

int mid = ( lb + ub )/2;
swap ( a[lb] , a[mid] );

int pivot = a[lb];
int left = lb + 1;
int right = ub;

while ( left <= right ) {

while ( a[right] > pivot )
          right--;

while ( left <= right && a[left] <= pivot )
          left++;

if ( left < right ) {
       swap ( a[left] , a[right] );
       left++;
       right--
}

}//end while

swap (a[left],a[right]);
return right;

}

This works fine too. The right returned is correct and it does not work on sub-arrays with pivot already selected previously.

              

JSP <=> Servlets

A servlet is in essence, a Java class that is executed by the server in response to a client request. A JSP file on the other plays many different roles in the context of a web application. For one role, it could simply be a view that renders the server side response in HTML, XML, JSON or other formats. For another, it could be the intermediary code like ASP or PHP that does some kind of input validation and thereafter forwards this input data to a server for persisting the same in permanent storage. Whatever the role, a JSP is compiled into a servlet and the JSP scriptlet code itself constitutes a part of the doGet() or doPost() methods of the servlet. 

What one needs to internalize here is this interesting relationship between JSPs and Servlets for the former eventually gets rendered into the latter. This leads to a critical inference regarding JSPs and Java classes. A servlet being a Java class, the ultimate form that a JSP takes is a Java class. This relationship between JSPs and Java classes leads to yet another interesting result. A class is composed of member functions and data, so a JSP that eventually gets compiled into a class must provide some mechanism to declare and define class members. The answer is of course, yes. Using the declaration tag, one may declare and define class members in the very same way as in a Java class itself. An example is shown below:

<%!

private String name;

private Integer roll;

public void setName (String name) {

this.name = name;

}

%>

Now one may call a function as shown above from a scriptlet as shown below:

<% 

setName ("Joe");

%>

It's important not to miss the forest for the trees. The crux of the idea is that every web servlet is nothing more than a simple class and the information being passed around is nothing more than a simple object. When you learn object-oriented programming for the first time, it is not very uncommon to read that object passing facilitates message communication. While then it appealed to the senses as nothing more than some kind of an abstract fantasy, we are now seeing rather elegant manifestations of that concept.

Forwarding and Redirecting

While both redirect and forward seem to show the same effect, they are in essence two extremely different things:

Forwarding is done when a client submits a request for a page (url) and the server side code assesses that the page should not be accessed directly by the client in such fashion. Imagine an account dashboard page that shows up after a login. Such a page, let's say, "www.domain-name.my-account.html" should only be displayed after a successful login in the login page, say, "www.domain-name.login.html". If the client attempts to bypass login and access the dashboard directly, the natural thing to do for the server would be to forward the user to the login page where he would be prompted to login and thereby access his dashboard. Note that forwarding takes place entirely on the server side and it does not involve the browser at all. In fact, the browser would not even be aware of the actual page forwarding.

Client - > Server : Access page B

Server -> Client : Shows page A as the requested page, B 

Redirect is done when a client requests a page and the server sees that the requested page is no longer accessible may be on account of page expiration or on account of change of url or even absolute removal of the requested page. In such cases, the server responds with a page that mocks the requested page but that includes a header that may be decoded by the client to access a different page altogether. The client browser then needs to make another request to access the specified page. Note that client side browsers are aware of redirects unlike forwards.

Client - > Server : Access page B

Server - > Client : Page B | Header: Page C

Client -> Server : Access page C

Server -> Client : Page C

This distinction also has another interesting ramification. If the client browser has disabled cookies, then cookies may not be sent to the client. Thus session information cannot be transmitted between successive client requests in the regular way. This browser behavior does not however affect server-side forwards .This may be worked around by URL encoding which essentially involves embedding the session id in the URL to maintain session state. 

JSP Include directive and Dynamic include

The interesting difference between the include directive and the dynamic include is that the former is a static import and the latter is a dynamic import. 

To explain, the include directive is similar to a macro call while the dynamic include is like a function call. While a macro call simply inserts or includes the contents of the macro definition in the body of the program where it is called at compile-time, a function call is more than a mere include. Function calls perform some kind of computation on the data that is passed to them as arguments. 

In our own context of JSPs, use of the static import using <@include file = " " /> essentially inserts the contents of the file specified at that place and compiles it with the JSP into a servlet. The dynamic import using <jsp: include page = " " / > on the other hand, compiles the included JSP page as a separate JSP and embeds a call to it at the point of dynamic import statement.

Heads up tip on Java web application deployment

It's not unusual to compile your Java web application with JDK 7 and then deploying it on a platform that runs it on an earlier version of Java or for that matter, a later version.

Make sure that you compile your application with the same JDK version as that used by the platform that you deploy it on.  

Java String overrides Object.equals

The Java String object extends the Java Object like any other Java object does. It must however be noted that the Java String overrides Object.equals method to compare two String objects character by character.

Let's briefly look at the Object.equals code:

public boolean equals(Object other)
{
   return this == other;
}

We can see that Object.equals compares the references of the objects themselves and as such returns true only if the two references are in essence referring to the same object in heap. The equals is overriden by Java String to return true if the two objects are logically equal.

Consider,

String a = "abc";

String b = new String ("abc");

String c = "abc";

System.out.println (a.equals(b));

System.out.println (a.equals(c));

System.out.println (a == b);

System.out.println (a == c);

The output would be:

true

true

false

true

Getting started with caveofprogramming.com

For beginners and intermediates alike, I would recommend that you check out these awesome video tutorials by John Purcell:

http://www.caveofprogramming.com/

Anonymous classes

Over the last week, I have been working with Java multi-threading in great detail. During this time, I started passively working with anonymous classes, all the while, without realizing that this was yet another worthwhile Java concept. 

Anonymous classes enable you to write programs that are concise. While a regular class has a name, anonymous classes don't. Just look at the following segment of code:

Thread t = new Thread ( new Runnable() {

public void run () {

/*do something */

}

});

Now, we can see that the Thread constructor is passed an instantiated Runnable with the action to be performed in tact and encapsulated in the "run" method.

What we are in fact doing is creating an instance of a class that implements the Runnable interface and then declaring and defining the methods of this class. This is the idea of anonymous class. It's particularly useful if you do not wish to instantiate a class more than once. 

Key note on Java Generics

1. While you may safely assign a generic type object to a raw type, the converse is not true.

e.g. : Box <Integer> b = new Box <Integer> (); //Generic type

Box newBox = b;

This is legal. As for the converse, Box newBox = new Box ();// raw type

b = newBox;

The above doesn't result in a compile-time error but leads to a compile-time warning. Note that raw types bypass generic type checks at compile-time.

2. When using bounded generic type parameters, note that you may invoke method of the class being extended.

e.g. :

public class Box <T extends Integer>  {

     

       public T getDouble (T t) {

              return t.intValue() * 2;

       }

}

This is to note that the application of intValue() as shown in the preceding example is legal.

3. From 1, we can see that it is perfectly legal to cast an Integer to an Object. This is by virtue of their super type - sub type relationship or "isa" relationship as it is sometimes called. This does somehow lead to a common misconception which is shown below:

public void someMethod ( Box <Number> boxN ) {

/*do something */

}

Now, the parameter boxN here accepts any Box <Number> object. It must be noted though that boxN cannot accept objects of Box <Integer> types even if Integer extends Number. This is because Box <Integer> is not a subtype of Box <Number> and this is true even if Integer itself is a subclass of Number.

Thread.sleep() and Thread.yield()

An interesting comparison to make with no real loud, resounding solution at all.

Thread.sleep(long millis) typically causes the currently running thread to go to a sleep state. What this essentially means is that it actively uses CPU cycles to sleep for the duration specified in millis. After this sleep, however, there is no guarantee that the thread will continue to execute and may be moved to runnable state where it will join the queue of runnable threads waiting for execution.

Thread.yield() causes a current thread to defer its execution state to another thread of equal or higher priority. Apparently, the JLS does not provide guarantees that this thread will indeed be moved to the runnable state from running state.

It must be noted that neither of these methods result  in a thread forfeiting its locks, so they should be used with caution.

Immutable and Final

It is a known fact that String objects are immutable? What does this mean? Does this mean that String objects are implicitly final?

• String objects are indeed immutable. Now, this means that once a String object has been initialized, it's state cannot be changed.

String str = "India". Once such an assignment has been made, you can consider the heap allocated with an object "India" as shown with str being the reference.

Now, if we make an assignment, str = "China", what we are in fact doing is reassigning str to another object, China on the heap.

Here, the reference str has changed value. It was formerly pointing to object with state "India" and now it has been reassigned to refer to object with state, "China". In fact, the assignment of form, str = "somestring" creates a new string object on the heap each time. This is why String object is said to be immutable, immutable in that once initialized with a value, it can never change its state.

• What if we had initialized with the final keyword:  final String str = "India"?

What we have done now is made the reference str immutable. 'Immutable' may not be the best choice of a word here for what I had intended to say was that we have made the reference a constant, constant in that it will now point to the object "India" on the heap and can never be reassigned to refer to any other object on the same. In fact, the statement, str = "China" is now illegal.

• Why is it better to initialize a string object with the statement, String str = "India" as against String str = new String ("India")

Well, apparently, String is implemented in Java using a String pool. Now, what happens here is that once you create an object using the statement, str = "India" and subsequently reassign str with the statement, str = "China"; the former object "India" on the heap loses its reference but is not immediately garbage collected. If you then had to create another string with the former value "India", the already created object is reused. This obviates the need to recreate already existent objects. This is in fact one of the reasons why immutable objects do not provide the clone() or copy constructor method.

Now, let's say you initialize a string using the statement,

String str = new String ("India"). The above idea of deferred garbage collection applies here as well. But if you happened to write another String str2 = new String ("India"), Java would in fact create yet another object with value, "India" on the heap. This is to say that the existing String object would not be reused with a duplicate reference. This may be visualized as shown below:

Such duplicate object creation may not be in keeping with the space efficiency of the program as evidenced by the above example. A simple way to check the above result would be to compare str with str2: str == str2 which would return false. The object hash codes would also be different as they are two different objects. It must be noted that str.equals(str2) would return true.

Just another subtle addition to the above note. This scheme of deferred garbage collection applies only with some object types, String being one of them. For those to which it does not apply, (Integer, for example), the two initialization statements are in fact, equivalent.