Ranita works as an Assistant Professor at the Computer Science and Engineering Department at IIT Roorkee. She has completed her PhD from the Computer Science and Engineering Department at IIT Kharagpur. Before that, she has done her MTech from IIEST Shibpur, and got job offers from companies like Amazon, Samsung Labs etc. However, she preferred to pursue higher studies to stay in the field of academics and teaching. She believes in the motto of free education and contribution.


Alma Mater:

IIT Kharagpur
2012 to 2016
Master of Engineering
Indian Institute of Engineering Science and Technology, Shibpur
2010 to 2012
Bachelor of Technology
Kalyani Government Engineering College
2005 to 2009


Assistant Professor
Indian Institute of Technology Roorkee
Project Linked Personnel
Indian Statistical Institute, Kolkata
2009 to 2010
7 months 1 week ago

The correct answer is (b) remains same. To understand this, let us revise the informal algorithm for Timestamp based protocol for concurrency control (copied from Wikipedia, you can also refer to the formal version of the algorithm there):

1) If a transaction wants to read an object,

a) but the transaction started before the object's write timestamp it means that something changed the object's data after the transaction started. In this case, the transaction is canceled and must be restarted.
b) and the transaction started after the object's write timestamp, it means that it is safe to read the object. In this case, if the transaction timestamp is after the object's read timestamp, the read timestamp is set to the transaction timestamp.
2) If a transaction wants to write to an object,

a) but the transaction started before the object's read timestamp it means that something has had a look at the object, and we assume it took a copy of the object's data. So we can't write to the object as that would make any copied data invalid, so the transaction is aborted and must be restarted.
b) and the transaction started before the object's write timestamp it means that something has changed the object since we started our transaction. In this case, we use the Thomas write rule and simply skip our write operation and continue as normal; the transaction does not have to be aborted or restarted
c) otherwise, the transaction writes to the object, and the object's write timestamp is set to the transaction's timestamp.

Now consider the following example schedule:

T1      T2      T3      T4

Consider that after the execution of the last R(A), T4 needs to rollback (as given in the question). So, RTS(A) was 4 and now we need to decide what should be the new RTS for A. Note that, the schedule at hand now is something like the following:

T1      T2      T3

Independent of T4, this schedule will have RTS(A) = 3 when T2 tries to write and hence T2 should be aborted by rule 2(a).

Now, after rollback of T4, consider option (a) i.e. changing the RTS(A) to 0. This will certainly allow W(A) by T2 to execute without any problem as it falls under rule 2(c) and hence violates concurrency by allowing T2 to write a data already read by T3.

Consider option (c) i.e. RTS(A) becomes equal to the timestamp of the transaction which read 'A' just before T4, in this example then RTS(A) becomes 1. And hence the same problem arises as choosing option (a).

Therefore, if we choose option (b) and keep the RTS(A) same as before i.e. 4, then W(A) by T2 will fall under rule 2(a) and hence will be aborted. So, option (b) is the correct answer.

This is why RTS is kept as the largest of the timestamps of the transactions which has read the data, and not the recent timestamp.

Example text
8 months 3 weeks ago

This is an example of fan trap and chasm trap and how to resolve these scenarios. The following brief explanation may help you in understanding the concept which is usually found to be dubious across the web. This explanation is made in parity with the concept explained in Wikipedia (https://en.wikipedia.org/wiki/Entity–relationship_model#Model_usability_issues). You can also refer to https://db.grussell.org/section005.html to understand in detail.

Example text
10 months 1 week ago

You are very close to the answer. But, there is one catch; the first row of pixels (at y = 0) and the last row of pixels (at y = 37) are not full length. You may try to modify the approach accordingly to get to the correct answer. Very good presentation, by the way.

Example text
10 months 2 weeks ago

Consider the attribute set ABCDEG and the FD set
AB → C, AC → B, AD → E, B → D, BC → A, E → G
Is the following decomposition of R(ABCDEG)
(a) dependency-preserving?
(b) lossless-join?
Give proper justification for your answer.

jayantachakr's picture
Jayanta Chakraborty
innovwelt's picture
arvind.rawat's picture
Arvind Rawat
pritam's picture
Pritam Prasun
techtud's picture
Techtud Admin
pritam's picture
Pritam Prasun
vivek14's picture
Vivek Vikram Singh
pashupati's picture
Pashupati Jha
priyesh's picture
Priyesh Priyatam
girraj's picture
shreyans's picture
Shreyans Dhankhar
ribhu122's picture
Ribhu Ranjan
prafull's picture
Prafull Ranjan
antonio's picture
Antonio Anastasio Bruto da Costa
shabinmuhammed's picture
Shabin Muhammed
shuvankarchakraborty's picture


26 May 2016 - 8:08pm

A tree with 100 vertices always has 99 edges - you can think it as one edge pointing to each vetex except the root vertex. Now, each edge exactly contributes to the neighbor list of two vertices. So, total number of neighbors s is 99*2 = 198. So, correct answer is option (b) s = 198.

more less
26 May 2016 - 11:25am

@shivanisrivarshini The complexity is not O(nlogn), please check here: http://www.techtud.com/comment/5422#comment-5422

more less
26 May 2016 - 10:34am

Khushboo, This you have already asked before: http://www.techtud.com/comment/5422#comment-5422 and it has already been explained how the complexity is O(n). If you still have some doubts, kindly ask in that relevant thread. You can tag your preferred user by using '@' symbol and his/her username, so that he/she gets a notification email and can try to answer.
Shivani, Please try to give full-stops and new lines properly so that the meaning of the answer becomes clear and not ambiguous. One suggestion: use SHIFT+ENTER to give new line and use ENTER only when you want to start a new paragraph. Your answers will look better this way.

more less

Thank you so much. Just corrected.

more less

Please correct the question. It should be "atmost 20n-3 edges."

Here goes the answer assuming the correct question. Let us approach the options one by one. (There may be simpler techniques to solve this kind of problems, but I am just writing down how I have tried it.)

Option a: To have a graph with all vertices connected to at least 42 other vertices, you must have at least 43 vertices in your graph because it is simple and hence self-loops or multiple edges are not allowed. In a graph with n = 43 vertices, having all vertices connected to at least 42 other vertices, we get a complete graph. Therefore, we have n(n-1)/2 edges i.e. 43×42/2 = 903 edges; whereas, 20n-3 = 857 which is the upperbound for allowed number of edges. Therefore, option a is definitely false. (This option can also be checked the way I have tried option b.)

Option b: This says that we cannot find a graph with at most 20n-3 edges where every vertex is connected to at least 42 other vertices. Now, if we assume that every vertex is connected to at least 42 other vertices, the minimum number of edges we get is 42×n/2 = 21n which can never be less that or equal to 20n-3 for any positive value of n. Therefore, it is true that for all such graphs the number of vertices connected to atleast 42 other vertices is at most cn for some constant c<1 (c cannot be equal to 1). Therefore, option b is true.

Option c: Let us try to find out a graph with each vertex connected to at most 38 other vertices with at most 20n-3 edges. There are numerous possiblities. But let us take a complete graph with 39 vertices; so it has 39×38/2 = 741 edges which is less than 20n-3 = 20×39-3 = 780-3 = 777. So, option c is false.

Option d: As option b is true, option d is false.

more less
25 May 2016 - 10:42pm

I assumed that until the stack is empty, the string is not accepted even if we are in final state. But, possibly you are right, as @arvind.rawat also pointed out. I forgot almost all of these stuffs and referred https://www.cs.wcupa.edu/rkline/fcs/pdas.html#palindromes to try the problem. Thanks for pointing out the mistake. If possible, it would be great if the DPDA figures for both L and L' can be provided.

more less
25 May 2016 - 7:44pm

According to this note: http://www.cs.toronto.edu/~sacook/csc463h/notes/CFL.pdf
If L is the DCFL corresponding to DPDA M, we get complement of L from M' which is obtained from M by changing accept states to reject states and vice versa. DPDA for your given DCFL looks like this:

Now, changing the accept state to reject state and vice versa, gives us this:

which does not seem to be the correct answer to me as getting 'c' anywhere takes us to the rejecting state, and there is no way to come back. A language's complement should hold all strings that are not acceptable by the language. Your given language does not accept 01c00, so this M' should accept 01c00 which it does not. I am not sure, but there must be something else to catch here which I am missing.

more less
25 May 2016 - 6:42pm

If the input does not follow stack permutation, an algorithm with single stack memory wont be able to sort that input. As you can follow from the links given, stack permutations do not contain the permutation pattern 231. So, you need to change the input to a stack permutation (not containing 231 pattern) before feeding it to your sorting algorithm which is using a single stack memory.

more less

P(X) = X5 + 4X3 + 6X + 5
= X(X4 + 4X2 + 6) + 5
= X(X2(X2 + 4) + 6) + 5
Now, we have only one temporary variable, let us name it 't'.
t = X * X
t = t + 4
t = X * t
t = X * t
t = t + 6
t = X * t
t = t + 5
Therefore, minimum number of required arithmetic operations is 7.

more less
24 May 2016 - 8:29pm

The best source to learn about some mathematical definition or term: http://mathworld.wolfram.com/PrimitiveRoot.html

more less