O(2n) and O(n.2n) are different as we can say 2n is O(n.2n) but the converse is not true.

7 Jan 2016 - 11:36am

Dijkstra Algorithm takes \(\Theta((|E| + |V|) \log |V|)\) when implemented using binary heap (min priority queue) to calculate shortest distance from source vertex.

Now, in case of finding all pair shortest path, we need to run Dijkstra Algorithm \(|V|\) times (once for each vertex), thus the total complexity will be \(\Theta|V|((|E| + |V|) \log |V|)\).

6 Jan 2016 - 4:48pm

A can be regular. The only difference between A and B is, in case of B, there is a clear distinction between x and y due to the presence of $ between them. But in case of A, there is no distinction between x and y, means you don't know where x will end and from where y will start. Thus, we can see that there is no implicit comparison involved.

23 Dec 2015 - 2:34pm

I guess the FirstHalves will be regular, as there is no comparison involved, which implies no specific information needs to be stored for future.

23 Dec 2015 - 2:25pm

@Parimal, no it is not necessary that the number of a's is same as the number of b's, because the condition talks about the length of string only. You can see the same example given in the question, here bbab does not contain equal no of a's and b's.

23 Dec 2015 - 2:20pm

The idea is to first insert all the given values into the hash table according to given hash function. After that you will see that only five indices are remaining where no value gets inserted, so next element will get inserted into these five indices without causing collision. Thus the probability is 5/11.

23 Dec 2015 - 12:09pm
4 Dec 2015 - 11:06am

Physical memory size = 2^36 and second level page table size = 2^11 so number of pages in second level page table will be (2^36)/(2^11) = 2^25. Thus 25 bits are required to address it.

4 Dec 2015 - 10:56am

Yep, you got it right.

28 Nov 2015 - 8:58am

Follow the below link. It contains the same graph with same dfs traversal query except the starting vertex is changed.

Follow the same method explained there and see what you get.


27 Nov 2015 - 10:43am