Leap Year checking

What is Leap Year?

The standard Gregorian Calendar that we follow in our daily life, has a leap year every four years. In such a year the month of February contains one extra day in order to keep the calendar year synchronized with the Astronomical Year. So the number of days in the month of February becomes 29 and the number of days in the leap year becomes 366.

The Rule

The full rule for checking a leap year is not very well known, and I often find many of my juniors and fellow pupils lacking the exact knowledge of the full rule. What most people know is that if the year is divisible by 4 then it is a leap year. But although this rule is good for nearly all practical purposes, it is not the full rule. The exact rule for finding out whether a year is leap year or not, is best described by a flowchart:

It was of course designed keeping the programmers in mind. But non programmers too, should not have much of a problem to understand the logic. Just to aid them, a%b denotes a mod b, which in simple terms mean the remainder obtained when a is divided by b. The numbers a and b are positive numbers only. The above diagram is technically called a flowchart.

Programming Language Construct

We can of course translate this to a programming language with the use of three if-then-else constructs. But there is an easier way of doing this as I will demonstrate:

Let us denote the three condition checks by three boolean variables, A, B and C (as shown beside flowchart). So the condition for leap year is:

AB’ + ABC
= A ( B’ + BC )
= A ( B’ + C )

The reduced boolean expression when expressed in C-like constructs become:

year%4==0 && (year%100!=0 || year%400==0)

Conclusion

What prompted me to write the article was the popular misconception to the rule and the ability to demonstrate the boolean reduction technique. The article took shape while I was trying to explain the rule to my brother Bikkhan for the the n-th time and decided to draw the flowchart to make matters easy for him. Lastly, I also figured out that this could be an excellent way of showing him the practical usage of boolean reductions that he has learnt in his Std XI curriculum, but never grasped the true significance of.

References

1. To know more about Leap Year, Gregorian Calendar and Astronomical Year, just follow the links. You will also get an insight on the exact scientific reasons behind the rule.

2. For a similar discussion and actual program in C language, consult the book “The C Programming Language”, 2nd Ed., by Brian Kernighan and Dennis Ritchie. They have given a similar construct along with a full program on date computation.

3. For non-programmers reading this blog, here are some links on Boolean Algebra and Flowcharts.

Gold Bar Division Problem

The regular readers of this blog have by now figured out, and most correctly so, that this is going to be yet another post on Puzzle. I got this one from a friend of mine in IIT Bombay who shares my passion for brainteasers. This one appeared in one of the interview question dumps that gets circulated.

Problem Statement

So here goes the statement of the puzzle:

Amongst Bengalis Durga Puja is the biggest festival of the year and usually takes place in the month of October. Rajiv is a Bengali man, who needs money for buying gifts for his family during Durga Pujas. He plans to use his inherited 31cm gold bar as a security against taking the money. October has 31 days, Rajiv plans to give 1 cm of gold each day to the money lender and get some money from him.

However, Rajiv wants to make as few gold pieces as possible. So the obvious solution of making 31 x 1cm bars is out of question. He can rely on a scheme like giving 2 x 1cm bar on days one and two, then giving 3cm bar on day three and taking back the previous bars.

Find out the minimum number of gold bars, their individual sizes and how does Rajiv manage to use them.

Solution

The solution is rather simple. Rajiv needs to divide the gold bars into sizes 1, 2, 4, 8, 16, which adds up to 31. The scheme is very simple and best explained by a diagram of how each number from 1 to 31 will be made.

16	8	4	2	1	Value
0	0	0	0	1	1
0	0	0	1	0	2
0	0	0	1	1	3
0	0	1	0	0	4
0	0	1	0	1	5
0	0	1	1	0	6
0	0	1	1	1	7

 

Along similar lines the table will be extended till 31. The point to note here is that the numbers have a binary representation. So in problems of this nature (i.e. divide in minimum parts) where the weights of each part are non negative, the trick is to use the binary notation. The division have to be done using the binary positional numbers whose general representation is of the form 2^n for n = ( 0, 1, 2, … }.

Generally when the individual parts have two states we can safely assume binary representation. In this case the two states are: “with Rajiv”, “with money-lender”. Similarly for three states we will have to use ternary representation. I have an excellent example of usage of ternary number system, which I will be posting soon, so check back this space soon.

Trisecting an Angle

In mathematics the problem of trisecting an angle is a very interesting one. Perhaps more so, due to its seemingly impossible nature when compared to the similar problem of bisection of an angle which is easily achieved using compass and straightedge. Several literature have shown the problem to be impossible to solve using Euclidian geometric construction tools. However the problem is not impossible in nature. I have got a brilliant way of doing this using a very old technique originally attributed to Archimedes, the famous Greek mathematician.

The construction does not follow the Euclidean rules of construction which were used to prove its impossibility. However there is a bit out confusion about the rules themselves, as they are nowhere clearly mentioned in the writings of Euclid. However, most of the scholars agree on a set of rules apparent from the constructions described by Euclid. The following construction circumvents the rules, but does manage to trisect an angle accurately.

Archimedes’s method of Trisection of Angle

Let the angle to be trisected be AOB as shown in the figure. The trisected angle is PRA where 3xPRA = AOB (will be proved).

The steps of construction:

1. Using compass draw a circle with O as center. The intersection of the circle with OB is marked as P.

2. Draw like PR intersecting the circle at Q, such that QR = OP, where the point R is collinear with O and A. This is achieved by marking the distance OP on the straightedge and aligning the markings with the like OA extended backwards. Although it may seem a difficult procedure, it is actually quite easy to do.

3. Angle PRO is the trisected angle of AOB

Proof of Correctness

The proof is quite easy. I have put it down in a step by step way:

1. OP = OQ, as P and Q are points on circumference and O is the center of the circle.

2. triangle_POQ is isosceles, so angle_PQO = angle_QPO

3. angle_QOP + angle_PQO + angle_QPO = 180
   => angle_QOP = 180 – 2*angle_QPO

4. angle_RQO = 180 – angle_PQO = 180 – angle_QPO

5. triangle_RQO is also isosceles as QR = OP = QO, so angle_QOR = angle_QRO

6. angle_RQO + angle_QRO + angle_QOR = 180
   => 180 – angle_QPO + angle_QRO + angle_QOR = 180
   => angle_QRO + angle_QOR = angle_QPO
   => angle_QPO = 2*angle_QRO

7. angle_AOB + angle_POR = 180
   => angle_AOB + angle_QOP + angle_QOR = 180
   => angle_AOB + (180 – 2*angle_QPO) + angle_QRO = 180
   => angle_AOB – 2*angle_QPO + angle_QRO = 0
   => angle_AOB – 2*(2*angle_QRO) + angle_QRO = 0
   => 3*angle_QRO = angle_AOB
   => angle_QRO = (1/3) * angle_AOB

8. Hence we conclude that angle_QRO is the trisection of angle_AOB

So what is the catch?

There is no catch, the proof is indeed correct. In the beginning I have mentioned that the problem is impossible in nature, yet the proof that we showed is correct. The problem lies with the point 2 of the construction. The step required us to do a marking on the straightedge, which is not permissible in Euclidean constructions.

Bending the Rules !!

So you can actually intersect an angle after all, using the standard set of tools only. But the construction is not Euclidian. The interesting part is that this construction is quite old, but somehow this did not receive much publicity as the problem itself. Sometimes to solve a problem you have to bend the rules a bit.

Hollow Rhombus, a change in perspective

What is Hollow Rhombus?

For all those of you who do not know what exactly is Hollow Rhombus, here is a little intro for that. Hollow Rhombus is a homework problem given to students learning programming in procedural languages like BASIC, C, C++, Java etc. The problem goes like:

Write a program to input a word and print it out in the following format (for input word “HAPPY”):

HAPPY#HAPPY
HAPPY HAPPY
HAPP   APPY
HAP     PPY
HA       PY
H         Y
HA       PY
HAP     PPY
HAPP   APPY
HAPPY HAPPY
HAPPY#HAPPY

The whole point is to make students get acquainted with the various ways to use the looping statements like for, while, do-while. The problem is not a very easy one to solve for somebody who has just started with the looping constructs. It seemed to be quite an hurdle when I faced it back in std IX.

Usual Approach

The usual approaches towards solving the problem is to break up the figure into 6 parts:

First Line:
HAPPY#HAPPY

Left-Top:
HAPPY
HAPP
HAP
HA
H

Right-Top:
HAPPY
 APPY
  PPY
   PY
    Y

Left-Bottom:
HA
HAP
HAPP
HAPPY

Right-Bottom:
   PY
  PPY
 APPY
HAPPY

Last Line:
HAPPY#HAPPY

Then to code each part individually. The first and last lines are printed as it is. The top left and right parts are combined within a loop. Similarly the bottom parts are also combined within a loop (usually a for loop).

Sample Java Code for the usual approach

import java.io.* ;
public class gap
{
public static void main(String args[])throws IOException
{
 BufferedReader input = new BufferedReader( new InputStreamReader( System.in )) ;
 int j, k=0, x, y, z, Wl=0, sp=-1, st=0 ;
 String W="" ;

 System.out.print("\nENTER A WORD (MAX:19) : ") ;
 W = input.readLine() ;
 Wl = W.length() ;

 W = W+"#"+W ; // changing the string including a hash
 System.out.print("\n"+W ) ; // printing first-line

 for( j=0 ; j<Wl ; ++j )
 { // loop to generate top half
  System.out.println() ;
  sp += 2 ;// increasing space by 2
 
  for( x=0 ; x<(Wl-j) ; ++x )
   System.out.print( W.charAt(x) ) ;
  for( y=1 ; y<=sp ; ++y )
   System.out.print(" ") ;
  for( z=st ; z<Wl ; ++z )
   System.out.print( W.charAt(z) ) ;
 
  ++st ;
 }

 st -= 2 ;
 for( k=Wl-1-1 ; k>=0 ; --k )
 { // loop to generate bottom half
  System.out.println() ;
 
  sp -= 2 ;
  for( x=0 ; x<(Wl-k) ; ++x )
   System.out.print( W.charAt(x) ) ;
  for( y=sp ; y>0 ; --y )
   System.out.print(" ") ;
  for( z=st ; z<Wl ; ++z )
   System.out.print( W.charAt(z) ) ;
  --st ;
 }

 System.out.println("\n"+W+"\n") ; // printing last-line
}
}

Change in Perspective

The method that I have demonstrated so far to solve this looping problem is usual run-of-the-mill type. The coding is lengthy and the start and end loop values have to be carefully thought out. My brother, Bikkhan, who is in Std XII now had got this as a part of his programming assignments. When he came to me with this problem, I was quick to show him the common way of doing it by breaking it into 6 parts as demonstrated. It took him quite sometime, about 6 hours to come up with the Java code that you saw above.

I have been doing a lot of Prolog recently and I guess this is what led me to think recursively. Prolog does not have any traditional iterative statements, instead all sort of looping is achieved using recursion. To my surprise, thinking recursively had great effects on this program, and I solved it in almost no time in C++. The code length is very small compared to the former approach and I guess the logic is simpler too. So I guess its all about perspective. Here is a copy of my code in C++.

#include<iostream>
#include<string>

using namespace std;

int len;   // length of the input string

void hollow_rhombus ( string str, int n )
// str : is the string to be printed
// n   : is the step count
{
   cout<<str<<endl;

   if ( n < len )  // n==len indicates the middle line
   {
       string newstr=str;
       newstr[len-n] = newstr[len+n] = ' ';   // adding 2 new blanks
       hollow_rhombus ( newstr, n+1 );
       cout<<str<<endl;
    }
}

int main()
{
    string str;
    cin>>str;      // the word is taken as input

    len = str.length();
    str = str + "#" + str;     // first line is generated
    hollow_rhombus(str,0);     // calling the recursive function
}

Why talk about a silly looping exercise?

When I started writing this piece for my blog, my brother was the first one to ask about why did I like to share something trivial as this? After all this is another exercise in looping given to novice programmers. But what I felt was that this is a great example of how the right sort of problem analysis can lead to a simpler code, which is easier to write and read.

Win 7 RC1 Review

I was awaiting the release of Win 7 RC1 for quite some time. As a Microsoft Student Partner, I have a MSDN Premium subscription. So as a soon as it was available in MSDN (30th April), I downloaded it.

Here are my observations for the last 2 days:

• Win 7 continues to be FAST. I installed it on a AMD64 3000 with 1GB RAM and 6600GT ... worked great.

• Minor tweaks in taskbar ... check out the "task bar thumbnail overflow" feature

• Address Bar has been tweaked. In Win 7 Beta, if you browsed to a folder nested deep within the file structure the entire path could not be displayed and was truncated. In RC1, the parent folder and the current folder are always displayed.

• Jumplists tweaked a bit

• Search results are easier to view and understand. Snippets have been made longer and labeled up.

• Start Up, Shut Down and Hibernate times have become smaller ... or is it because of a clean install?

• AutoRun has been disabled by default in Flash drives

• Windows Media Player's "Lightweight Playback Mode" has been rechristened to "Now Playing Mode" which takes us less resources.

• UAC prompt now blacks out the desktop

• Couple of Psychedelic wallpapers ... this is so un-Microsoft-ish ... but I liked the design work ... keep it coming

• A friend reported some stuff about the battery meter in her laptop, but I’m not too sure about that

In summary. I see no new major feature. I was waiting for Win XP mode, but it was a disappointment not finding it in RC1. The new features are nothing but minor improvements from technical aspect, but it does beef up the usability of the OS. The improvements will enhance the UX and give a boost to the productivity.

In one line unless you are a UI geek, you would not see much improvements in Win 7 RC1 from Win 7 Beta. But if you just want to try Win 7 out after Vista or XP, this is a worthwhile download.

GMail “inbox”

I do not know if anyone noticed or not, but with such a fan following, someone was bound to notice. From today morning, the GMail Inbox is being pronounced as “inbox” with a small “i”. Here is a pic:

I guess this has got to do something with today being the April Fool’s day. Google has a history of putting up weird things on this day for the last couple of years.

GATE 2009 Rocked :-)

Today the GATE 2009 results have been announced. My results surpassed my expectations. After the examination on Feb 8th, I was more-or-less confident about getting into top 100. This confidence even withstood the discussions that I had with my friends at college who had also appeared in GATE. Lots of mistakes were discovered in the process. Eight of my 2-marks answers were wrong. Among the wrong ones around 3 were silly mistakes. The rest 5 were conceptual faults. Some of my wrong concepts stood corrected, which I guess is the long term benefit of the process.

Today morning was awesome, I was expecting a rank below 100 and secretly hoping it to be below 50. But the rank was better than all that at AIR 12, 99.97 %tile. I just could not believe it. It was Sukanto who gave me the good news at 09:58. We were all waiting for the results to go live at 10:00, but it was live at the IIT Kgp site shortly before that.

Future Plans

Now that GATE 2009 result has been very good I intend to go for higher studies in either IISc or a top IIT of the country in a M.Tech. or M.E. program. Will be applying for them as soon as possible. It feels great that I would be able to study under the best faculty that the country has to offer.

Poems on IT Recession

The recent global economic meltdown has caused the IT Industry in India to suffer a setback. The effect has cascaded to the students who were seeking job opportunities in the Information Technology related domains. Here are a few poems that our friends at IT industry have written along the lines of a few famous poets’ creations. The poems are in Bengali, and in JPG format.

Sukanto Bhattacharya

Rabindranath Tagore

Nazrul Islam

Jibonando Das

Its good to see that even in these tough times, people have not lost their sense of humor.

Happy Holi

Happy Holi and Best Wishes to everybody.

Using Firefox Profiles

As I mentioned in my last post, I have just reinstalled XP SP3 in my desktop machine. I was worried very much about having to reinstall Firefox in my new OS. I used the saved password feature to log-in to numerous sites. With the passing years of Firefox usage, right from version 1.0, I have picked up many good add-on. Then there is my library of bookmarks, which contains 1000+ links, all meticulously tagged, acquired through the years of browsing. I needed a way to transfer all these as seamlessly as possible to my new machine.

What I needed to transfer were (in order of importance):

• Bookmarks
• Saved passwords
• Firefox Add-on
• Auto-complete list
• Browser History

Firefox Profile

very few people are aware of a feature called Firefox Profile, which is:

Firefox saves your personal information such as bookmarks, passwords, and user preferences in a set of files called your profile, which is stored in a separate location from the Firefox program files.

Profile contains the complete set of user information that Firefox uses. Any changes that we make in the program settings are also saved. The program updates, the search engines, toolbars, add-on, saved passwords, in short everything that you would like to export is all saved in profile. Another great thing about Profile is that it is inherently exportable. You do not need to be a geek to do all these.

Where is this Profile

The profile is located in a folder “xxxxxxxx.default”, where the xxxxxxxx string is generated by Firefox installer, and is random in nature. The folder can be found in location “%APPDATA%\Mozilla\Firefox\Profiles\”. Please note that the path given is for Win 2000 and Win XP. For other OS, please consult the official guide.

Backup & Restore

Backup the “xxxxxxxx.default” folder. To restore the data, go to the same location of a newly installed Firefox, and copy the contents of the old “xxxxxxxx.default” folder to the new “xxxxxxxx.default” folder. This should do the trick, now start Firefox and see the results yourself.

Cross OS

What is most interesting is that this procedure is cross OS compatible. I copied the contents of my Windows Firefox profile folder to the Fedora Firefox profile (I had to change one .ini file too), and it ran seamlessly.

Show Hidden Files in Win XP SP3

Yesterday I formatted my desktop computer and installed Win XP SP3. There was this strange problem of not being able to see the hidden files in Explorer. By default, users are not not supposed to be seeing hidden files. So the standard way is to go to the “Tools > Folder Options” in Explorer.

Then browse to the “View” tab, in the window.

Select the radio button corresponding to “Show hidden files and folders”. Then apply this setting.Close all the explorer windows and then open one Explorer window to check the effect of the new setting.

However in my case, the setting did not have any effect what so ever. I repeatedly followed the above steps but somehow it did not seem to work. Maybe its due to some program conflicts, or maybe due to SP3. I did not face this problem in my older SP2 installations even after installing SP3 on top of SP2.

Thankfully, this has a workaround by tweaking the registry. From the “Start” menu, select “Run” option,

Then type “regedit” (without quotes) and press enter.

You should now see something like,

Then browse to
“HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\Advanced”.

In the right hand area, double click on “Hidden”. And change the value to 1.

The final regedit window should look like,

Now close the all the explorer windows. Log off and log in. You should see the effects of your registry change. The hidden files will be shown in the explorer.

Weighing puzzle

This is one gem, that I got from a friend of mine. The puzzle in its simplest form goes like this:

There are a set of 8 balls. Out of which 7 are of same mass, and the remaining one is heavier than the rest. What is the minimum number of weighings required to find out the heavier ball? i.e. How many times do you require to use the balance?

My Method

I do not know what you would do, but what I did was to divide the balls first into groups of two groups of 4 balls, then take the heavier set, and divide it into two parts and so on. This yields an answer of 3. More precisely, the answer is:

where n is the number of balls.

 

Actual Answer

However the actual answer is two weighings. The technique is to split the balls into three approximately equal groups, here we have 3,3,2. Then weigh the 3,3 groups against each other, if they are the same, then weigh the two remaining balls against one another. If one of the two 3,3 groups are heavier, then select that group and weigh any of the two balls against one another, if one is heavy, then you got the ball, if both are equal, then the third one of the group is the heavier.

So the correct expression is

for n balls.

 

Decision Tree

Here is a schematic diagram:

GATE CS 2009 Question Paper

A lot of people are asking for a copy of the GATE 2009 papers. Here is a copy of my GATE CS 2009 paper photographed and merged in DJVU format.

In case you cannot open the file, download the Win DJ View software for Windows.

GATE 2009 CS Solutions

There seems to be a lot of arguments over the GATE CS 2009 solutions. Here is my version of it. I have provided explanations and diagrams wherever I felt them necessary.

1. A Follows directly from the definition of a Group.
2. A A look at this figure should clear your doubts:
3. B I did this in the lame way, by drawing graphs. I am quite sure that it can be proved mathematically too. Something along the lines of "let all the vertices have dissimilar degrees", and then proof by contradiction.
4. D Not symmetric as (x,y) is present but (y,x) is absent. Not anti-symmetric as (x,z) and (z,x) are both present.
5. B This one was quite simple, just use base convert function of your calculator. Alternatively use the age old method of grouping the binary digits in groups of 3.
6. B Draw the K-Map and group 0s taking 2 0s per group. You should get 2 such groups. Each group requires one NOR gate. Then these 2 groups, together will require another NOR gate. Formally it looks like: AB+C = (A+C)(B+C) = ( (A+C) (B+C) )'' = ( (A+C)' + (B+C)' )'
7. C We need 256 Kbytes = 256 x 1024 x 8 bits. We have RAM chips of capacity 32 Kbits = 32 x 1024 bits. Dive the former by latter, and you arrive at 64 chips.
8. C I do not remember where I read it from, but I guess its either in 8085 book by Gaonkar or in the Architecture book by Hayes. you can also try Mano's book.
9. A Belady's anomaly is a typical (and very odd) feature of FIFO. Its explained nicely in Galvin.
10. B Page frame numbers are most important. Virtual page numbers may not be stored entirely in the page table.
11. A In each pass, there can be at most 1 swap. There are n such passes.
12. B This is evident from the grammar itself. Just try generating some strings, if you feel otherwise.
13. C* I am sure about the Q part. Q is true. But I have some confusion over the P part. P can be shown to be false for certain directed graphs. But from the general definition of Graph, directed is not to be assumed. So I hope P & Q both are true. personally I did not answer this question.
14. C This is best explained by the set diagram (original diagram in the book of Algorithms by Horowitz & Sahani.
15. C This is again evident from the RE given. The string must have at least two 0s.
16. D Some CFLs cannot be accepted by Deterministic PDAs. I got this from the book of Automata book of Hopcroft, Motwani and Ullman.
17. B Check out the Dragon book (Compilers by Aho, Sethi, Ullman)
18. B Just dry run the GATE_09_18.c program. Giving the steps would be laborious for me. In case you want to just see how it works, try running the program.
19. C I do not know from which book this was given. Thankfully it was there in my SW Engg paper that I appeared for in 2008.
21. B This was quite simple, you can apply Bayes Theorem, or just use the basic probability theorems.
23. D Gold and Silver does not literally translate to "G(x) AND S(x)". it means that "All ornaments which are made of Gold or Silver are precious".
24. B The function given the the table is P+Q'
25. D
26. B See the corresponding chapter on the book of Discrete Mathematics by Rosen.
27. A Look at the transition diagram: State 00 means A=0 and B=0. State 11 has not been drawn as it cannot be reached from any other state. The smallest input satisfying the criterion is 101.
28. B Click to view the enlarged image.
29. D 4 way set associative cache with 16 blocks imply that each set has 4 blocks numbered 0,1,2,3. We take each memory block and use the last 2 bits to place it into proper cache following LRU replacement scheme. 216 would not be in cache as it is followed by 8, 48, 32 and 92.
31. B Initial position of head = 50. Nearest request is 34. The sequence of access would be: 50, 34, 20, 19, 15, 10, 7, 4, 2, 73
32. C Consult the OS book by Deitel.
33. A I is true. II is false, as it does not ensure fairness. III is false as there is no queue of sleeping processes.
34. B This is the one and only reason for using multilevel paging. All other benefits are direct or indirect effects of this reason.
35. B The equation is of the form: T(n) = T(n/3) + cn On solving this recurrence relation we get T(n) = Big_Theta (n log n) Without going into the details of the proof, let me give you something that wil explain it much more naturally. Just download GATE_09_CS_Q35.pdf, where I have shown the data plotted against various values of c {5,10,15,20,25} and n {1,3,9, ... 3^11}. Then I have plotted n*log(n,b_up) and n*log(n,b_dn) as the two lines that give the upper and lower bound for the series for some values of bases b_up and b_dn. Most importantly the nature of the curves are similar to that of type n*log(n).
36. C Open addressing and linear probing results in table C. Just try it out in pencil and paper.
37. B The minimum number of nodes required for an AVL tree of height h is given by, F(h) = F(h-1) + F(h-2) + 1, where F(0) = 1 and F(1) = 2. For the deduction of this expressions, look into the book by Kruse.
38. D (a,c) cannot follow (b,c) as (a,c) < (b,c)
39. B
40. C This follows directly from the property of CFGs, where we see that CFGs are not closed under intersection, but produces CFGs when intersected with RLs. Even if you are not aware of this, just examine the languages L1 and L2. The intersection is given by (a^m)(b^m)c. This is obviously a CFG.
41. C Try generating a few strings.
42. B I is true for simple languages like assembly language of 8085. II is false, dynamic allocation is a must for implementing recursion. III is true as written in the Dragon book. IV is true.
43. B Draw the dependency graph. S2 and S3 will have no cycles.
47. A Maximum packet lifetime is 64s and the number of packets can range from 0 to 2^32-1 and the counter increments by 1 per millisecond. Thus the minimum permissible rate is 0.0149.
48. C Look into any discussion on CRC. I read this from Forouzan.
49. C I is true II is false, it is to be defined only in level 0 and 1 III is true IV is false, data stores cannot be connected between each other
50. D All of the options are true. For I, look into the book of Jalote. others are true from the definition of Cyclomatic Complexity.
51. C 400x2x10x63 + 16x63 + 29 = 505037
52. C 16x63 + 31 = 1039
53. C This is the Longest Common Subsequence problem.
54. B Look into the above link.
55. D B and C are clearly wrong. Amongst A and D, D is chosen as it also returns suppliers who have not supplied any part.
56. B Follows from the dependencies and definitions of 3NF.
57. D Let n be the number of frames. Then, 25e-3 = 100n / 1e6, which gives the value of n = 25. Thus we need ceiling (log 25 / log 2) = 5 bits.
58. B Time taken to send 2^5 frames = 32. Time taken for the first fram to be acknowledged = 25x2. Thus waiting time = 50-32 = 18
59. C Try constructing the max heap.
60. D In case of the 1st deletion there is no problem. In case of the 2nd deletion, the tree loses its almost complete nature, thus we have to replace 8 in a proper place in order to retain this property.

The * mark indicates that I am not sure about the answer to that question. Please keep in mind that the answers may not be correct. These are what I believe to be correct. Most of them were computed by me, and some of them are from fellow GATE aspirants (mostly Sukanto).

If you believe that any of the answers are wrong, or cannot seem to follow the explanation that I have provided, please leave a comment here. I'll try to reply to all the questions.

GATE 2009

The regular readers of this blog are all asking about my absence for such a long time. The sole reason for this is GATE 2009, which took place today. This examination has a lot of importance for me, as the result of this is going to shape up my future career. So a lot of time and energy was devoted to it, resulting in lesser time to other activities like maintaining this blog.

Thankfully GATE 2009 CS paper was easier than expected. There have been some silly mistakes on my part, which could have been avoided, but overall I expect a better ranking than GATE 2008.

Welcome 2009