GATE question papers for CS and IT

GATE question papers for CS and IT

Hi friends, AamzillaA thinks solving previous question papers is
very important to get a good score in GATE. Its a little challenging
for anyone to find time to solve, type and post topic wise questions
to various forums. So I was just thinking why don't we guys and gals
preparing for GATE CS / IT come together and start solving previous
papers from now one. I feel that if we are able to go through each and
every question asked in previous GATE papers, it would indeed be a
great way to start our preparation. At the very least we will get an
idea about what kinda questions are asked in GATE.
Every one will be proficient in some areas right ? May be if every one
contribute their knowledge in solving previous question papers, we may
be able to solve the
entire paper very quickly. Well, even I have bought the GK publishers
question paper book. But there are more errors in it than correct
answers and the solutions
are prepared in a very careless and ambiguous way, just for the sake
of providing some stuff to name them as solutions. Since we are going
to write GATE exam, its
our need to understand the questions and solve them correctly. So I
think we could attack GATE as a group , it would be more beneficial to
each one of us, and also for all future generations of GATE CS
aspirants. I think it would be a worth while way to spend our free
time for a noble cause.
Please post a comment at
http://living-in-shadows.blogspot.com
if u are interested in sharing ur knowledge in tackling GATE questions.
Its indeed so difficult for me to stop once I start a mail. But I do
respect your precious time , and am posting straight away the links to
previous GATE question papers of Computer Science and information
technology.
By the way , thanks a lot to visit my home here in cyberspace. You are
always welcome to come again here. I shall daily post here the fruits
of my GATE studies
here. If you are of the curious type, please go through my previous
posts regarding GATE.
My dear friends, please leave a comment if u think this post was
useful to you. It would just take a few moments of your time, but
would provide a great deal of
inspiration for me to do more good things with my life.
Thank you very much,
All the Best for GATE 2008 !!!
AamzillaA
Here comes the links....
gatementor guys rock !!!!
http://www.gateforum.com/cs2007.pdf
http://www.gateforum.com/it2007.pdf
http://gatementor.com/gatepapers/CS2006.pdf
http://gatementor.com/gatepapers/CS2005.pdf
http://gatementor.com/gatepapers/CS2004.pdf
http://gatementor.com/gatepapers/CS2003.pdf
http://gatementor.com/gatepapers/CS2002.pdf
http://gatementor.com/gatepapers/CS2001.pdf
http://gatementor.com/gatepapers/CS2000.pdf
http://gatementor.com/gatepapers/CS1999.pdf
http://gatementor.com/gatepapers/CS1998.pdf
http://gatementor.com/gatepapers/CS1997.pdf
http://gatementor.com/gatepapers/CS1996.pdf
http://gatementor.com/gatepapers/CS1995.pdf
http://gatementor.com/gatepapers/CS1994.pdf
http://gatementor.com/gatepapers/CS1993.pdf
http://gatementor.com/gatepapers/CS1992.pdf
http://gatementor.com/gatepapers/CS1991.pdf
http://gatementor.com/gatepapers/IT2004.pdf
http://gatementor.com/gatepapers/IT2005.pdf

Tuesday, September 25, 2007

Gate 2007 CSE Operating Systems Questions Solved.

\week 1\days 2,3\24,25-09-07\monday, tuesdayHi friends,
AamzillaA is back with another post. The day was
spent trying my wit against the 2007 GATE CSE OS questions. Well, I
can't claim to be my effort to be fruitful because I haven't made
much progress. One thing , I really learnt today was how much i
don't know about OS, and how much more I need to study. Well, won't
waste much of ya time with my blabbering, lets get straight in
to business. As usual I am waiting eagerly to hear ya comments about
this post. Please be free to voice ya suggestions to improve the
style of my posts or any errors in the method of solving or anything
that u think is relevant regarding this post. There are lot of OS
concepts which still remains elusive, please help if u have any ideas
regarding them.
So here we go....
/////////////////////////////////////////////////////////
GATE2007CSE Question Paper Analysis:
Total Marks for OS :14
1 mark questions : 2 [ 16(A), 17(D) ]
2 mark questions: 6 [ 55(B),56(B),57(C),58(D),82(A),83(C) ]
//////////////////////////////////////////////////////////
G07\CSE\Q16\OS
Q. Group 1 contains some CPU scheduling algorithms and Group 2
contains some applications. Match entries in Group 1 to
entries in Group 2.
Group 1 Group 2
P. Gang Scheduling 1. Guaranteed scheduling.
Q. Rate Monotonic Scheduling. 2. Real time Scheduling
R. Fair Share Scheduling 3. Thread Scheduling.
A) P-3 , Q-2, R-1
B) P-1 , Q-2, R-3
C) P-2, Q-3, R-1
D) P-1, Q-3, R-2
/* Can any one enlighten me about what are these scheduling mentioned
in the options. Me never heard about them before. Any good
books to find more about the various scheduling algorithms mentioned
in this question ? */
The answer is A
but sorry , I don't know why....
//////////////////////////////////////////////////////////
G07\CSE\Q17\OS
Q. Consider the following statements about user level threads and
kernel level threads. Which one of the following statements is false.
A) Context switch time is longer for kernel level threads than for
user level threads
B) User level threads do not need any hardware support
C) Related kernel level threads can be scheduled on different
processors in a multi processor system.
D) Blocking one kernel level thread blocks all related threads.
ANS. D
I need to read more about what user level threads and kernel level
threads are and how context switch takes place between them ,Can
any one suggest some book where context switching is mentioned clearly.
//////////////////////////////////////////////////////////
G07\CSE\Q55\OS
Q. An operating system uses shortest remaining time first (SRT)
process scheduling algorithm. Consider the arrival time and
execution time of the following processes.
Process Execution time Arrival time
P1 20 0
P2 25 15
P3 10 30
P4 15 45
What is the total waiting time for process P2 ?
A) 5 B) 15 C) 40 D) 55
ANS:
This is a simple one but is a little bit tricky.
U need to know some terms first....
Turn around time (TAT) = Completion time (CT) - Arrival time. (AT)
Waiting time (WT) = TAT - Burst Time (BT , also known as execution time, ET)
Shortest remaining time first scheduling algorithm is a pre-emptive
algorit. So any process can get pre-empted at any time when a
process with less time for execution arrives.
Time
0: P1 with ET 20 arrives and starts execution
5: P1 executing
10: P1 executing
15: P1 executing, P2 with ET 25 arrives but is not allowed to run is
its ET is 25 , since remaining time to complete P1 is only 5 So
Mr. Scheduler tells P1 to wait till P1 gets over.
20: P1 completes execution , P2 starts execution.
25: P2 executing
30: P2 is pre empted now and P3 starts running since P3 with a
lesser time to finish executing ie 10 sec arrives. P2 still needs 15
seconds to finish executing.
35: P3 Executing , P2 waiting
40: P3 finishes execution , hands over control to Poor P2. P2 starts executing.
45: P2 executing , P4 with ET 15 arrives , but Mr. Scheduler tells P4
to wait since P2 now needs just 10 more seconds to finish his
task , while P4 needs 15 seconds.
50: P2 executing , P4 waiting
55: P2 finishes execution and hands over control to P4.
60: P4 executing
65: P4 executing
70: P4 finishes executing and now every one is happy !!!
So P2 arrives at time 15 and finishes its execution at time 55.
So TAT is 55-15 = 40
ET of P2 is 25 seconds.
So Waiting time of P2 is TAT-ET = 40- 25 = 15 !!!
So answer is B
//////////////////////////////////////////////////////////
G07\CSE\Q58\OS
Q. A virtual memory system uses First In first Out (FIFO) page
replacement policy and allocates a fixed number of frames to a
process. Consider the following statements.
P: Increasing the number of page frames allocated to a process
sometimes increases page fault rate.
Q: Some programs do not exhibit locality of reference.
Which of the following are true ?
A) Both P and Q are , and Q is the reason for P
B) Both P and Q are true but Q is not the reason for P
C) P is false , but Q is true
D) Both P and Q are false
ANS:
P: FIFO page replacement policy is one of the simplest and
most straightforward page replacement policies on earth. But it
suffers from a disease called Bellady's anomaly where the page fault
rate may actually go up , after increasing the number of page
frames. Whether page fault rate increases or decreases depends upon
the reference string.
Q: Some programs do not exhibit locality of reference. Isn't it
obvious. I guess no explanation is required for this statement. Q is
actually un related to P.
So answer is B
////////////////////////////////////////////////////////////
G07\CSE\Q57\OS
Q. A single processor system has three resource types X,Y,Z which are
shared by three processes. There are % unitis of each
resource type. Consider the following scenario, where the column alloc
denotes the number of units of each resource type allocated
to each process, and the column request denotes the number of units of
each resource type requested by a process in order to
complete execution. Which of the processes will finish last ?
alloc request
X Y Z X Y Z
P0 1 2 2 1 0 3
P1 2 0 1 0 1 2
P2 2 2 1 1 2 0
A) P0
B) P1
C)P2
D) None of the above, Since the system is in deadlock.
ANS:
Lets first get the facts straight. There are 5 instances
each of X,Y and Z. And there are three guys P1, P2 and P3 competing
for them.
Out of 5 Xs , P0 takes 1, P1 takes 2 and P3 takes 2. So after
allotment there are no X remaining. But P0 and P2 has both requested
for one more instances of X. Obviously their requests cannot be
entertained. So they will have to wait.
Lets now consider P1's case. P1 already have 2 instances of X and it
doesn't need any more X. but P1 needs 1 instance of Y and 2
instances of Z. Out of the total 5 Ys only 4 are allocated. So P1's
requirement for Y can be met. Out of 5 Zs only three are aloocated.
P1 needs 2 more instances of Z. Even this demand can be taken care of.
So first P1 completes execution and gives back 2 Xs, 1 Y and 3 Zs.
Now the request of P0 can be met. Since P1 needs 1 X, 0 Y and 3Z.
So , P0 is the guy to complete execution second.
Lastly , P2 can have all the resources and can finish its execution.
So P2 finishes the execution last.
So our answer is C. Don't jump and conclude that a dead lock will
arise, since its also mentioned as an Option , indeed a fairly lengthy
option when compared to other options.
/////////////////////////////////////////////////////////
G07\CSE\Q58\OS
Q. Two process, P1 and P2 , need to access a critical section of code.
Consider the following synchronization construct used by the
processes.
####################################3
/* P1 */
while (true) {
wants1 = true;
while (wants2==true);
/* Critical
Section */
wants1=false;
}
/* Remainder section */
#############################################
/* P2 */
while (true) {
wants2 = true;
while (wants1==true);
/* Critical
Section */
Wants2=false;
}
/* Remainder section */
###################################################3
Here wants1 and wants2 are shared variables, which are initialized to
false. Which one of the following statement is true about the
above construct ?
A) It does not ensure mutual exclusion
B) It does not ensure bounded waiting.
C) It requires that processes enter the critical section in strict alternation.
D) It does not prevent deadlocks, but ensures mutual exclusion.
ANS:
Code ensures mutual exclusion. but does not prevent deadlock. Just
imagine what will happen if both P1 and P2 gets hold of
wants1 and wants2 simultaneously and keeps waiting for the other to
release the key. It shall never happen and both will be
DEAD-LOCKing each other.
So answer is D
+ //////////////////////////////////////////////////////////
G07\CSE\Q82\OS
Q82) A process has been allocated 3 page frames. Assume that none of
the pages of the process are available in the memory initially.
The process makes the following sequences of page references.
(reference string) : 1,2,1,3,7,4,5,6,3,1
If optimal page replacement policy is used , how many page faults
occurs for the above reference string ?
A)7 B)8 C)9 D)10
ANS:
All ideal things in life are impractical !!!!
No, i'm not here to preach philosophy. Optimal page replacement(OPR)
policy is an ideal policy which would have been possible to
implement if we could see future events in the present. If u can
predict ur GATE score in 2008 now, u might be gifted enough to see
future and may be u should try to implement optimal page replacement
policy using ur super natural powers.
But since ordinary mortals like me still don't know how to predict the
future , OPR still remains as an impractical page replacement
policy.
Now, what is this optimal page replacement policy ? Page replacement
policy comes into play when u have lesser number of frames
to hold the pages in memory than the number of pages. So eventually
according to ur reference string , there comes a time when u
have to replace some of pages in memory to be replaced by another. How
u do this is determined by page replacement policy.
In OPR u replace that page that u don't need for the longest period of
time. Since the complete reference string is not known at the
point of making the decision, u can't do this unless u can predict future.
But still for the sake of theory we shall do this problem.
The closest thing to OPR that can be practically implemented is LRU
(Least recently used )page replacement policy. In this one
,instead of looking at the future u look at the past , and u replace
that page which was least recently used. The next problem is all
about LRU.
reference string : 1,2,1,3,7,4,5,6,3,1
optimal page replacement policy
Read 1, 1st page fault , put it in frame 1 // 1, _ ,_
Read 2, 2nd page fault, put it in frame 2 // 1,2,_
Read 1, Since one is already in frame 1 , no page fault // 1,2,_
Read 3, 3rd page fault, load 3 in frame 3. // 1,2,3
Read 7, 4th page fault, look into future, realize that u don't need 2
again throw it away from frame 2 , load 7 in frame 2. // 1,7,3
Read 4, 5th page fault, look into future, realize that u don't need 7
again, throw it away and load 4 in frame 2. // 1,4,3
Read 5, 6th page fault, look into future, realize that u don't need 4
again, throw it away, and load 5 in frame 2 // 1,5,3
Read 6 , 7th page fault, look into future, realize that u don't need 5
again, throw it away, and load 6 in frame 2 // 1,6,3
Read 3, No page fault since 3 is already in frame 3
Read 1, No page fault since 1 is already in frame 1
Congrats !!! U have finished doing this problem , go and have a cup of tea !!
So if we use Optimal page replacement police as demonstrated above u
will have 7 page faults.
//////////////////////////////////////////////////////////
G07\CSE\Q83\OS
Q.Least recently used (LRU) page replacement policy is a practical
approximation to Optimal page replacement policy. For the above
reference string, how many more page faults will occur with LRU than
with the optimal page replacement policy.
A)0 B)1 C)2 D)3
ANS:
reference string : 1,2,1,3,7,4,5,6,3,1
LRU page replacement policy
Read 1, 1st page fault , put it in frame 1 // 1, _ ,_
Read 2, 2nd page fault, put it in frame 2 // 1,2,_
Read 1, Since one is already in frame 1 , no page fault // 1,2,_
Read 3, 3rd page fault, load 3 in frame 3. // 1,2,3
Read 7, 4th page fault, look into past, realize that u didn't use 2
recently, throw it away from frame 2 , load 7 in frame 2. // 1,7,3
Read 4, 5th page fault, look into past, realize that u didn't use 1
recently, throw it away and load 4 in frame 1. // 4,7,3
Read 5, 6th page fault, look into past, realize that u didn't use 3
recently, throw it away, and load 5 in frame 3 // 4,7,5
Read 6 , 7th page fault, look into past, realize that u didn't use 7
recently, throw it away, and load 6 in frame 2 // 4,6,5
Read 3, 8th page fault, look into past, realize that u didn't use 4
recently, throw it away, and load 3 in frame 1 // 3,6,5
Read 1, 9th page fault, look into past, realize that u didn't use 5
recently, throw it away, and load 1 in frame 3 // 3,6,1
Congrats !!! U have finished doing this problem , go and have an ice
cream for a change !!
So number of page faults is 9 which is 2 more than 7
So answer is C
/////////////////////////////////////////////////////////////////////////////////////////////////////
Hello !!
Can some one volunteer to solve portions of the GATE 2007 CSE papers ?
Are there any TOC\Digital\Computer Architecture
experts here ?
Friends, please feel free to post your suggestions about these
solutions. I would like to know how many people find these solutions
helpful. So please tell if u liked this or not. It would indeed be a
great motivation and encouragement to post more solutions here.
Wishing u all the best for GATE 2008,
AamzillaA

Gate 2007 CS Keys

Hi freinds,Just thought you might be interested in having the keys to GATE 2007 CS paper.
As far as my strong belief , the keys are 100% correct , but please
don't sue me for damages if there are any mistakes in the keys.
Anyone , like to solve GATE CS previous question papers ? If you are
interested please get in touch. Presently I'm working on the 2007
papers. I hope to cover more papers in future. By the way , I have
posted some things related to GATE in previous posts please have a
look , and please be kind enough to leave a comment at the end of the
post as a small gift to me to keep alive the memory of your esteemed
presence in my blog. Please feel free to link this blog in as many
places as u wish. I hope to chronicle my preparations for GATE in this
blog.
Wish you all the very best in GATE 2008 !!!
Thank you very much,
AamzillaA

Here comes the key....
Gate 2007 CS Keys
1. A
2 B
3 C
4 B
5 D
6 B
7 B
8 C
9 B
10 D
11 A
12 C
13 B
14 A
15 A
16 A
17 D
18 A
19 A
20 C
21 A
22 D
23 A
24 D
25 C
26 C
27 A
28 A
29 A
30 B
31 C
32 D
33 D
34 C
35 B
36 C
37 B
38 A
39 A
40 B
41 D
42 D
43 C
44 C
45 B
46 C
47 A
48 B
49 D
50 B
51 B
52 C
53 C
54 A
55 B
56 B
57 C
58 D
59 D
60 C
61 D
62 D
63 B
64 C
65 D
66 D
67 C
68 B
68 C
70 B
71 D
72 D
73 C
74 C
75 B
76 A
77 D
78 C
79 B
80 C
81 C
82 A
83 C
84 A
85 D

Sunday, September 23, 2007

GATE 2008 CSE Data Structure Questions Solved !

Day 1
20 weeks remaining for GATE !!!Hi Friends,
Was trying to solve some DS questions from GATE
2008. The questions asked were some what simple. Here I'm posting my
solutions to those problems. I am getting the answers, but if you find
any errors in the solution please be kind enough to leave a comment.
GATE2007CSE Question Paper Analysis for DS:
Total Marks for Data Structures :14
1 mark questions : 2 [ 12(C), 13(B) ]
2 mark questions: 6 [ 38(A),39(A),40(B),42(D),43(C),46(C) ]
///////////////////////////////////////////////////////
G07\CSE\Q12\DS
Q. The height of a binary tree is the maximum number of edges in any
root to leaf path. The maximum number of nodes in a binary tree of
height h is :
A) 2h B) 2h-1 C)2h+1 D)2 h+1
ANS:
A node in a binary tree cannot have more than 2 children. The maximum
number of nodes is possible when each node has 2 children
when height , h=0 number of nodes, N =1
h=1, N = 1+2 = 3
h=2, N = 1+2+4 = 7
h=3, N = 1+2+4+8 = 15
h=h, N = 2^0 + 2^1 + 2^2 +... + 2^h = 2^(h+1) -1
There fore answer is B
///////////////////////////////////////////////////////////////////////
G07\CSE\Q13\DS
Q. The maximum number of binary trees that can be formed with three
unlabeled nodes.
A)1 B)5 C)4 D) 3
ANS:
A binary tree can have utmost 2 nodes.
I wish I could have drawn the tree to make explanations simple. But
drawing is taking a lot of time, so please forgive me the lack of
visual info and try to get the picture.
While placing a new node , two conditions should be met.
1. It should be connected to a previously placed node , unless its the
first node , ie root
2. It should be placed in a valid position, ie as a right child or
left child of an existing node , if its not the first node.
When we add a node to a binary tree, each newly added node consumes
one previously existing valid position and adds two new valid
positions. There fore net addition in no of valid positions after
connecting a new node to a binary tree is 2-1=1.
In a more general case, if it was an n-ary tree, each new node will
consume one previously existing valid position for adding a new node
and adds n new valid positions to the n-ary tree. So the net addition
of valid positions in an n-ary tree after adding a new node will be
n-1.
Another point is that , if a binary tree has k nodes the number of
valid positions to add a new node that the resulting tree is still a
binary tree will be always k+1.
Now with this concept lets approach the problem ,
With one unlabeled node, there is only one way to create a binary tree.
With 2 unlabeled nodes, we can create 2 binary trees by connecting the
second node either as a left child or right child of root.
With 2 nodes , the number of valid positions we have to create a three
nodes binary tree is 3.
But there are two ways in which we can create a 2 node binary three .
Therefore total options we have to create a 3-node binary tree is 2*3
= 6. But among these 6 trees two are symmetric, and since the nodes
are unlabelled we have to consider them as a single tree. There fore
the total number of binary trees possible with 3 unlabelled nodes is
6-1 =5.
There fore answer is B
Can some one tell how many identical trees (same shape) will be there
in a binary tree if there are n-labeled nodes. If n is even there will
be no identical trees. But if n is odd, i think there will be (n-1)/2
identical trees. Can someone please give me a proof for this ? I
simply drew all the trees and counted them.
In the above problem if there were n unlabelled trees the maximum
number of binary trees possible will be what ?
////////////////////////////////////////////////////////////
G07\CSE\Q38\DS
Q. The following postfix expression with single digit operands is
evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * -
Note that ^ is exponentiation operator . The top two elements of the
stack after the first * is evaluated are :
A) 6,1 B)5,7 C) 3,2 D)1,5
ANS:
postfix notation is also know as reverse polish notation. Refer: Mark
Allen Weiss, chapter 3.
The concept we need to know here is that when evaluating a postfix
expression using stack, when ever an operand is seen its pushed into
stack, when ever we read an operator, the required operands are popped
out of stack the result is computed and the result is pushed into the
top of stack.
In postfix the relative position of operands remain same as the
original expression but the relative position of operators can change.
If operation is binary operator the top most is second operator.
8 2 3 ^ / 2 3 * + 5 1 * -
Reading : 8 // push 8
Stack : 8
Reading :2 // push 2
Stack :8 2
Reading :3 // push 3
Stack :8 2 3
Reading :^ // pop 3,2 compute 2^3 = 8,( don't do 3^2 =9 ) and push
8 to top of stack.
//Note top most is second operand
Stack :8 8
Reading : / // pop 8,8 computer 8/8 =1 and push 1 to stack
Stack : 1
Reading : 2 // push 2
Stack :1 2
Reading :3 // push 3
Stack : 1 2 3
Reading : * // pop 3,2 and do 2*3 = 6 , push 6
Stack :1,6
There fore top two elements after evaluating the first * operator is 6,1
So answer is A
////////////////////////////////////////////////////////////////
G07\CSE\Q39\DS
Q. The in order and pre order traversal of a binary tree are
d b e a f cg and a b d e c f g , respectively.
The post order traversal of the binary tree is
A) debfgca
B) edbgfca
C) edbfgca
D) defgbca
ANS:
To solve this question first we must construct the tree from
inorder and pre order.
How are we going to make the tree ? We know that , in pre order the
root is always the first element. Using this concept we should keep on
dividing the inorder arrangement into groups until we get the tree. I
know this sounds vague. Well, I don't know how to put the idea in
words, but i'll try my best to show what i know.
preorder : a b d e c f g
in order: d b e a f cg
for group dbeafcg , a is root
divide dbeafcg into two groups. dbe and fcg, a is parent for these two groups
for group dbe, b is root
divide dbe into two groups, d and e, b is parent for d and e
for group fcg , c is root
divide fcg into two groups, f and g
Now the tree is complete
I will try to scan the picture of the tree and post here as a
comment when i get time.
it looks something like. Now just compute the postorder using usual
standard technique and u will get the answer as debfcga.
a
..........................
| |
b c
............... ..................
| | | |
d e f g

////////////////////////////////////////////////////////////////////////////
G07\CSE\Q40\DS
Q. Consider a hash table of size 7,with starting index 0,and a hash
function (3x+4)mod 7.Assuming the hash table is initially empty, which
of the following is the contents of the table when the sequence
1,3,8,10 is inserted into the table using closed hashing ? Note that _
denotes empty location in the table.
A) 8,_,_,_,_,_,10
B) 1,8,10,_,_,_,3
C) 1,_,_,_,_,_,3
D) 1,10,8,_,_,_,3
ANS:
Hashing is explained well in weiss, I just skimmed through the
matter.. need to read it thoroughly sometime later.Please go through
that to get a better idea about hashing.
Hash function is (3x+4)mod7
Keys are 1,3,8,10
(3*1+4) mod 7 = 0
(3*3+4) mod 7 = 6
(3*8+4) mod 7 = 0
(3*10+4) mod 7 = 6
Imagine 7 rooms in a hotel , room 0 , room 1 , room 2 ,room 3 , room 4
, room 5, room 6
Mr.1 is inserted in room 0
Miss. 3 is inserted in room 6
When Mr. 8 tries to get into adress 0 ,he will find Mr. 1 sitting
there, so there will be a collision. Since we are using closed hashing
or linear probing policy, when we find 0 and 8 fighting for the same
room in memory , we say the second comer ie 8 to go and occupy the
next room. So 8 goes and sits in adress 1.
Mr.8 is inserted in adress 1
Now Mr. 10 comes and tries to sit in room 6. he finds Miss 3 already
sitting in room 6. Another collision begins, and Miss 3 gives a slap
and so Mr.10 tries to go to the next room ie room 0, there he finds
Mr. 1, so he goes to room 1 , there he finds Mr.8 , so he goes to next
room ie room 2 which he finds vacant and so he occupies it.
This is a classic example of clustering.
so finally we have the positions :
1,8,10,_,_,_,3
So answer is B
/////////////////////////////////////////////////////////////////////////
G07\CSE\Q42\DS
Q. Consider the following C-function.
int f(int n)
{
static int r = 0;
if (n <= 0) return 1;
if (n > 3)
{
r = n;
return f(n-2)+2;
}
return f(n-1)+r;
}
What is the value of f(5) ?
A)5 B)7 C)9 D)18
ANS:
When attacking recursion questions, you need to have an idea about
activation record. Each time a function is invoked as set of separate
variables is assigned to it unless it is declared as static. Static
variables retains their values throughout the life of the program.This
, if a function is exited and reentered at a later time, the static
variables defined within function will retain their former values.
This is the most important thing to remember while solving the above
question. If u treat static variable r just like a local variable ,
every time u will initialize r to 0 and u will get a wrong answer (you
will get it as 3 instead of 18).

##########################
f(5)
r = 0
r = 5
return f(3)+2 // 16+2 =18
###################
f(3)
// note since r is defined as static r is not assigned as 0 every time
the function is called.
return f(2) + 5 // 11 +5 =16
##################
f(2)
return f(1) +5 // 6+5 =11
###################
f(1)
return f(0) +5 //1 +5 = 6
#################
f(0)
return 1
#################
So answer is 18. ie choice D
///////////////////////////////////////////////////////////////
G07\CSE\Q43\DS
Q. A complete n-ary tree is a tree in which each node has n children
or no children. Let I be the number of internal nodes and L be the
number of leaves in a complete n-ary tree. If L=41 and I=10, what is
the value of n ?
A)3 B)4 C)5 D)6
ANS:
L = I (n-1) +1
41 = 10 (n-1)+1
Therefore, n=5
He he he ....... So simple right ? U get 2 marks for solving an
equation that even a 5th standard student can solve.. but did u get
the logic ?
If u refer Q13 , i have mentioned that if u add a new node to an
existing n-ary tree, u are consuming one valid position and adding n
new positions. So after addition of a new node u add n-1 valid
positions to the previous number of valid positions. here they say
that there are 10 internal nodes. So each time u add these 10 internal
nodes u are adding (n-1) leaves.
Tree looks something like this if n = 5
So answer is C
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
├┬┬┬┐
///////////////////////////////////////////////////////////////
G07\CSE\Q46\DS
Q. Consider the following C program segment where Cell Node represents
a node in a binary tree:
struct CellNode {
struct CellNode *leftChild;
int element;
struct CellNode *rightChild;
};
int GetValue (struct CellNode *ptr)
{
int value = 0;
if (ptr != NULL)
{
if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))
value = 1;
else
value = value + GetValue(ptr->leftChild)+
GetValue(ptr->rightChild)
}
return(value);
}
The value returned by GetValue when a pointer to the root of a binary
tree is passed as its argument is :
A) the number of nodes in the tree
B) the number of internal nodes in the tree
C) the number of leaf nodes in the tree
D) the height of the tree
ANS:
In think this is a little difficult question. First draw a complete
binary tree with say 3 levels. Now point ptr to root.
The key code to watch is
if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))
value = 1;
ie if there are no children for a node value is set as one. that node
is counted if it is a leaf node.
if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL))
value = 1;

This code helps us to descent to just one level above the level of leaf nodes.
So the program computes the number of leaf nodes in a tree.
There fore, the answer is C
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Hi friends,
I hope three hours of my effort would be of some use to you. If you
see any errors in the explanations or if u know any better/faster way
to solve these questions I would be very thankful if you would leave a
comment. If you don't mind please tell me whether u liked this
presentation or not. You can use these solutions for any
non-commercial purpose, if u want to share these contents with others,
please mention the source from which u got this.

Wish u all the Best for GATE 2008
if u are also preparing for GATE2008 Computer Science, please get in
touch... we can share a lot of stuff.. I am looking for solved GATE
papers. If u know of any such sources please let me know. I hope to
solve and post more of the 2007 paper after i obtain some more gyan
but... before that i should eat something...
Bye 4 now ,
aamzillaa

Main topics asked in GATE 2007 CSE

GATE 2007 CSEHi friends,
These are the topics asked in GATE 2007. If u have time , it would be
very helpful if u could share ur ideas on these topics. Like how to
study them.. best books to find relevant materials etc.
Thanks a lot,
aamzillaa
01)
f(x)=|x| is a V shaped graph. There fore it is continuous. But the
right hand limit tends to be a negative quantity since its slope is
negative. And the left hand limit tends to be a positive quantity.
Since its slope is +ve. There fore since Right Hand Limit is not equal
to Left Hand Limit. The function is not differentiable.
so answer is A.
02)
• sets
• equivalence relation .
• ordered pair .
03) Digital

• Maximum number of different Boolean functions involving n Boolean
variables.
04) graph theory
• Non-planar graph
• edge of a graph
• vertice of a graph.
05) graph theory
• what is a DAG .
• what is topological ordering .
06) TOC
• Undecidable problems.
• Membership problem in CFG .
• Ambiguity problem in CFG .
• Finiteness problem for FSA .
• Equivalence problem for FSA .
07) TOC
• regular set .
• every subset of a regular set is regular or not .
• How to find "something" is regular or not .
08)
• 3:8 decoder with enable theory.
• constructing bigger decoders using smaller decoders.
9)
• Boolean function independent of one/two/three variables
10) COR
• 4-way set associative cache
• TAG,LINE,WORD fields
11) OS
• Size and number of bits required to specify a disk pack
12) DS
• Height of a binary tree.
13) DS
• maximum number of binary trees
14) Algorithms
• Lowest worst case complexity
• merge sort
• Bubble sort
• Quick sort
• Selection sort
15) C
• Floor and ceiling functions
• C-programming.
16) OS
• CPU scheduling algorithms
• Gang Scheduling
• Rate monotonic Scheduling
• Fair share scheduling
• Guaranteed scheduling
• real-time scheduling
• Thread scheduling
17) OS
• User level and kernel level threads.
• context switching
18) Compiler
• top down parsers
• Recursive descent parser
• Operator precedence parser
• LR(k) parser
• LALR(k) parser
19) CNW
• Ethernet
• Manchester encoding.
• bit rate and baud rate.
20) CNW
• UDP
• HTTP, telnet, DNS,SMTP
21) Discrete Mathematics
• order of non-isotropic abelian groups.
22) Discrete Mathematics
• Graph , connectivity
• Mathematical logic
• predicate logic notations
23) Discrete Mathematics
• graph theory
• eulerian circuit
• k-regular graph
• complete graph with 90 vertices
• complement of a cycle on 25 vertices
24)
• Permutations
• probability
25)
• matrices
• identity matrix
• eigen values
26)
• sets
• partitions
• partial order
• poset diagram
• πi refines πj
27)
• set of column vectors
• basis for a subspace
• linearly independent set
• span
28) Numerical Methods
• Newton raphson method
29)
• Minimum state DFA accepting a language
30) TOC
• A language over the alphabets
• recursive language
• deterministic CFL
• regular language
• CFL
31) TOC
• check whether a language is regular or not.
32) DIG
• expression equivalent to a function oe not
33)
• DiG
34)
• mux and inverter, used to implement a Boolean function
• minimum size of MUX needed.
35)
• look ahead carry generated
36)
• 4- bit binary counter
37)
• pipelined processor
• operand forwarding
38)
• postfix expression evaluation using stack
39)
• binary tree
• inorder , preorder traversal given find post order
40)
• hash table
• hash function
41)
• unweighted , undirected connected graph
• shortest path
• time complexity
• Dijkstra's algorithm
• Warshall's algorithm
• DFS (depth first search)
• BFS (breadth first search)
42)
• Recursion in C
43)
• Complete n-ary tree
• internal nodes
• leaves
44)
• recursion
45)
• time complexity of a recursive function
46)
• C programming
• tree traversals
• recursion
47)
• Max Heap as an array
• Binary search
• newly inserted element
• number of comparisons
48)
• Conjunctive Normal Form
49)
• undirected connected graph
• minimum weight among all edges
• minimum spanning tree
• cycle
50)
• Number of comparisons needed to find minimum and maximum
51)
• Bg –Oh notation
• T(n)
• Ω(1)
52)
• grammar
• non-terminals
• terminals
• start symbol
• left recursive
• right recursive
• ambiguous
• context-free

53)
• regular grammar
• LL(1)
• LR(1) grammar
• regular set
54)
• COR
• operations
• MOV instructions required
55)
• Shortest remaining time first process scheduling algorithm

56)
• Virtual memory system
• FIFO page replacement policy
• fixed no of page frames
• page fault rate
• locality of reference
57)
• Single processor system.
• Resources
• processes
58)
• Deadlocks
• Critical section
• synchronization
• mutual exclusion
• bounded waiting.
59)
• relation
• relational algebraic expression
60)
• Tuple relational calculus query.
61)
• SQL
62)
• BCNF
• 2NF
• relation
• attribute
• prime attribute
• transitive dependency
• 3NF
63)
• B+ tree
• order of a lea node
• block size
64)
• transactions
• schedules
• conflict serializable
65)
• Slotted LAN
• probability of transmission
66)
• token ring network
• transmission speed
• propagation speed
• 1-bit delay
67)
• Address of class B host
• subnets
• subnet number
• maximum no of hosts and subnets
68)
• message
• CRC polynomial
• protection from errors
69)
• frames
• propagation delay
• channel capacity
• maximum frame utilization
• sliding window protocol
70)
• SMTP
• BGP
• TCP
• PPP
71)
• word addressable memory
• number of memory references
72)
• contents of a particular memory location
73)
• Byte addressable memory
• word size
• return address pushed into stack

74)
• Finite state automata
• regular expression
• language accepted by automata
75)
• Huffman coding
76)
• Average length of Huffman code
78)
• CFG (context free grammer)
• non-terminal alphabets
• terminal alphabets
• production rules
• strings generated by grammer
• Number of derivation trees.
80)
• byte addressable main memory
• direct mapped cache
• data cache misses
81)
• which lines of data cache will be replaced ?
82)
• process
• page frames
• sequence of page references
• optimal page replacement policy
• reference string
• page faults
83)
• Least Recently Used page replacement policy.
• page faults
84)
• Robot movement simulation.
• number of distinct paths
85)
• Robot traversal with constraints

Saturday, September 22, 2007

Compiler !!! Starting trouble

Started studying compilers. The Text book is "Compilers -
Principles, techniques and tools" by Aho, Ullman and Ravi Sethi. I
think this book is also popularly known as the dragon book. So what did I learn about compilers today. Well, just gathered
some introductory ideas about the subject. Compiler is something that
translates a high level language code to machine code. Well, machine
code can be different for different processors. Isn't it wonderful ?
To think about compilers as some magic genie which translates an idea
in ur head in the form of a high level language code to low level
code. I have heard that in ancient days, they took years to write a
compiler. I think , the C-compiler is written in C. Well, the Turbo
C-compiler and the java compiler javac are the only compilers I had
seen.
There are so many new terms that I have seen today... It might take a
while to get acquainted with them. What I have learnt to day is that
from the gate perspective the main topics to study in compilers are
lexical analysis, parsing, syntax directed translation, code
generation, runtime environment and basics of optimization.
Some of the things that I have studied today can be summarized as follows.
Pre-processor : Something that takes a HLL program and expands macros
and includes files
Compiler: Produces assembly language code
Assembler: Takes assembly language code and produces re locatable
machine code. What on earth is meant by re locatable machine code ?
Loader: It allocates, de allocates memory , links and loads. Still
don't know what allocation and re allocation of memory is , how
linking is done , and how loading is done. I guess I need to read
something about system programming. Can anyone suggest some good books
to learn system programming ? I should have taken that as an elective
while at college. Instead I took embedded systems, which I should
admit was very interesting.
Lexical analysis : This produces a stream of tokens. What are tokens?
I think they are things like "if" , "then" etc etc that we use so
often in C-programs. I should read more about it sometime later.
Syntax Analysis: There are some things called grammars. Some kinda
rules based on regular expressions (what is this ? ) to define things
in a general way. I know thats the dumbest definition that u might
have heard.. but thats all i know now. Well... atleast there is
something useful in blogging about what I study , it makes to me clear
what things that I don't understand.
Semantic Analysis: Its something to do about the meaning of programs.
Don't ask anything more.
Symbol table manager: The compiler needs something called a symbol
table to do compiling.
Static type checking: What is static type checking ?
Intermediate Code generation
What is three address code ?
Parse trees : Is this some tree which produces a fruit called parse
? just kidding...
Lexeme:
What is Lex tool ? If any one has heard about this can u please tell ?
"Lexical Analyser can be designed by describing token rules by means
of regular expressions and converting them to Finite automata" . I
think I should learn theory of computation to learn about these
things.
A parse tree can be formed by left most derivation(LMD) and right most
derivation(RMD). If LMD and RMD of a string is not the same, then the
grammer used to define that string is said to be ambiguos grammer. I
have seen a 2007 GATE question in which one of the options is about
ambiguity of grammers.
Well, that is all I learned about compilers...
May be I should just take a break from compilers and start reading OS now.

Friday, September 21, 2007

GateWay

My dear friends, I would like to appear for GATE on 10th Feb, 2008. Today is 21st
September. There is roughly 20 weeks remaining. I am planning to try
my luck in computer science and engineering. Me basically having a
non-computer science background don't know whether this is going to be
a wise decision or not. But at times , I feel we should listen to our
heart to know the deepest desires of our soul and to decipher the
inner voice that tells us about the things that would give purpose and
true joy in being alive.
Why do I like computer science. I like it because computer science
represents one of the greatest achievement of mankind. I truly believe
its one thing that has changed our civilization in a big way and which
would truly be a breeding ground for the next wave in the evolution
of the human species. The evolution is bound to happen , not may be in
the physical form of human being , but in the structure and form of
his intellect and mind. When knowledge becomes so pervasive like air,
water and soil and better still , free .. When each human , with
reasonable means to own a computer and net connection is given an
unprecedented opportunity in human history to pursue his intellectual
desires, a great revolution of ideas is bound to happen. Till the dawn
of last century or so , mainly due to lack of technology, mind never
had enough opportunities to grow in the scale in which it is possible
now.. Not one of my ancestors , who might have lived a century back
might have ever dreamt about communicating with any stranger in this
world from the luxury of the sweet confines of his home , without
spending a fortune. Its not the politicians nor the religious
preachers who have brought this great change in human life possible.
Its mainly the scientific minds who made the computers and had in the
process lighted the lamp to remove darkness and that set the millions
of ordinary human minds free. Its computers that has truly liberated
the minds of the people. Its this technology which has made
innovations like blogger, which gives a voice to anyone who cares to
speak, orkut, which connects any person with anyone else in this
world , and operating systems like windows and linux which has both
made its own contributions in making the computers friends and also
cheap to the ordinary human being.
We have been witnessing tremendous change in our lives every day. I
still remember the days when there was no TV in my neighborhood. The
growth in technology has been mind-blowing. But I feel much more
exciting times awaits us. Computers are still going to evolve into
better machines. Humans will make better computers and computers would
in turn help humans become better. Its a symbiotic relationship.
Computers have learnt to read aloud printed texts, the time they will
identify our faces, our handwriting and our speech and could talk to
us like an ordinary human is not far. They will learn to recognize
and classify the things they see through a camera. They will evolve
closer to human being and from our part mainly due to the fruits of
technology we would be able to maximize the efficiency and creativity
of our minds. The best of both worlds will happen when two of the most
wonderful things in the the whole of the observable universe shall
converge to create a new generation of being , part computer and part
human... The day we shall integrate smart machines into our bodies for
entertainment and also to enhance our productivity is not very far.. I
have already read somewhere about brain computer interfaces , which by
combining signal processing with some smart technologies can indeed
read what u are thinking. I know, the biological science lag behind by
many centuries , when compared to the improvements in physics and its
byproducts. But may be I shall live , to see this new wave of
evolution , when the best among the human race shall become even
better by acquiring the best traits of the machines. Progress is the
pulse of nature. Nature exists so that it can reinvent itself into a
better being. Humans with intelligence and wit were the jewel in the
crown of mother nature. But she is not yet satisfied. Her quest for
excellence manifests as the desire in a smart mind to innovate. And
its innovation that changes the living standards of humanity. Its not
politics not religion not any lame ideology but only innovation that
can change present living standards of humanity on a large scale. The
effects of politics and all other factors should be to provide
conditions ripe for innovation to happen. The purpose of all politics
and all religion should be to nurture and safe guard the spark only
found in a human mind that makes innovation possible. Innovation
cannot happen when you have a barrel of a gun is pointed to your head.
Innovation germinates in a mind only when it experiences the sunlight
of freedom and water of financial resources. Innovation bears fruits
in the form of big social changes like orkut and other gigantic
improvements in the living standards of an ordinary man. This is the
importance of the scientific mind which explores new ideas, searches
for the truths hidden behind the veil of nature and which in turn
makes human race sustain itself on the face of the earth what ever may
happen.
I have tremendous faith, almost a religious faith in the ability of
the best minds among humans to overcome any kind of adversity that
nature may throw in front of human race as a whole. Without the
collective efforts of the best minds among humans , ordinary man is
mostly at the mercy of nature. A simple fever can claim his life, if
not treated with drugs invented by the best among men and delivered by
the doctors. But nature is always giving means for the human race to
survive in the form of this specially gifted people who can take care
of all the not so well gifted people. So the ozone layer may deplete,
the sea may swallow great extents of habitable land, temperatures
might become unbearable, pure drinking water might become a luxury,
germs capable of mass murder may emerge , all other animals may perish
due to lack of habitat and environmental changes , but human race
shall prevail for ever... Human race shall prevail until we choose to
annihilate ourselves by wars or we choose politico-social systems in
which growth of the innovative mind is made impossible. I pray that we
shall not choose rulers who are so foolish or evil enough to risk the
survival of the gem of all life in the universe , the human being.
But what does all this got to do with GATE 2008 ? Well, the only
chance for an ordinary human being like me, who doesn't have millions
to inherit , to have a chance to contribute the fruits of my mind to
the well being of humanity, to find joy in exploring the hidden truths
of nature and the thrill of playing with new ideas and also at the
same time find the financial means to sustain my life and that of my
family is to get a seat for M-tech in some good institution, hopefully
an IIT.
But the challenges that lies between me and my dream are numerous.
Till now the age of complete liberalization of knowledge has not come
, well , things like MIT open courseware and many other useful stuff
still exists. But still much more can be done. This blog is going to
be my humble attempt in helping me and anyone else who have achieve
the goal of attaining a good result in GATE CSE in 2008 or the years
to come. I am going to post to this site what I learn everyday. I plan
to post anything that I find interesting. It could be a challenging
GATE problem , or it could be the ideas my mind has absorbed from
reading books by great minds. This may not be helpful for anyone
except me in the long run, but if it could inspire anyone else who is
preparing for GATE , or help any one clarify at least a single doubt,
them I would be really proud of my blog , because then I would know
that I have made a small contribution to human race and a tribute to
the great minds that has lived before me who have made life on this
planet such an exciting thing to live.
The remaining 140 days or so shall make or break my life. Like a
caterpillar in its cocoon waiting for the day its wings sprout , I
shall burn my days till GATE as an offering before God, who was after
all the greatest innovator of all times. Please wish me luck and if
you find yourself in the same position as mine or if you think you
also have the same attitude towards life please do leave a comment or
get in touch. We could be great friends in future.
With lots of love,
aamzillaa

Friday, September 14, 2007

Better version of MemWiz

Hi Friends,This one is a better version of MemWiz.
No great changes, its just that its look-and-feel is better.
~aamzillaa~
// MemWiZ
// MemWiZ is a game to sharpen your short term memory
// aamzillaa at gmail dot com
// 12-09-2007 AD
#include
#include
#include
#include
#include

void main()
{
int num,i=0,j=0,char_ok_flag=1,count=0,guess_flag=1,choice=0;
char temp,ch[100],letter,guess[100];
int LOW_LIMIT= 65,LEVEL=0,HIGH_LIMIT= 90,LAST= 100, MAX_CHAR_NUM =5,
DELAY_TIME= 1, WAIT_TIME= 1,OLD_WAIT_TIME=0;
int replay_flag=0;

start_mem_wiz:
//INITIALIZING
i=0;
j=0;
char_ok_flag=1;
count=0;
guess_flag=1;
choice=0;
LOW_LIMIT= 65;
HIGH_LIMIT= 90;
LAST= 100;
MAX_CHAR_NUM =5;
DELAY_TIME= 1;
WAIT_TIME= 1;
if(replay_flag==1)
{
MAX_CHAR_NUM=LEVEL;
WAIT_TIME=OLD_WAIT_TIME;// ADD 1 HERE IF YOU WANT TO INCREASE 1
SEC EXTRA FOR EACH HIGHER LEVEL
goto start_new_game;
}
clrscr();
printf("\n\n\n\n\n\n\n\n\t MemWiz \n");
printf("\n\n\n\n\t\t\t\t\t\t\t aamzillaa at gmail dot com \n");
getch();
clrscr();
printf("\n\n\n\n\n\n");
printf("\n Welcome to MemWiz \n");
// printf("\n\n\n\n This is a memory game \n");

printf("\n\n Enter Level [1\\2\\...\\26] : ");
scanf("%d",&MAX_CHAR_NUM);
if(MAX_CHAR_NUM>26 || MAX_CHAR_NUM < 1)
{
printf("\n\n Invalid level !!! Press any key to play again \n");
getch();
clrscr();
goto start_mem_wiz;
}
// printf("\n\n Enter Delay in seconds between displaying new
characters : ");
// scanf("%d",&DELAY_TIME);
printf("\n\n Enter time in seconds to memorize characters : ");
scanf("%d",&WAIT_TIME);
// printf("\n\n Enter Lower limit for character set (Default is 65) : ");
// scanf("%d",&LOW_LIMIT);
// printf("\n\n Enter Higher limit for character set (Default is 90) : ");
// scanf("%d",&HIGH_LIMIT);
// printf("\n\n Enter Last digit in randomizer (Default is 100) : ");
// scanf("%d",&LAST);
clrscr();
//ch[0]='a';
start_new_game:
randomize();
while(1)
{
num=rand()% LAST ;
char_ok_flag=1;
if(num>=LOW_LIMIT && num <= HIGH_LIMIT )
{
// checking whether number is already in array
temp=num;
for (j=0;j<=i;j++)
{
if(temp==ch[j])
{
char_ok_flag = 0;
}
}

if(char_ok_flag==1)
{
//printf(" %c ", num );
ch[i]=num;
i++;

if (i >= MAX_CHAR_NUM)
{
ch[i]='\0';
break;
}
//getch();
}
}

}// end of while
//printf("\n\n %s \n Thank You ",ch);
//getch();
// delay(1000*DELAY_TIME);
clrscr();
printf("\n\n\n\n\n\n\n\n\t\t\t\t Level %d ",MAX_CHAR_NUM);
delay(1000);
clrscr();
printf("\n\n\n\n Look carefully into the following letters...\n\n\n");
for(i=0;i<=MAX_CHAR_NUM;i++)
{
printf(" %c ",ch[i]);
delay(1000*DELAY_TIME);
}
delay(1000*WAIT_TIME);
clrscr();
//getch();
printf("\n\n\n\n\n\n");
printf("\n Please try to type the letters you saw a few moments
ago...\n\n\n");
//printf ("\n\n in the order you saw them \n\n\n");
count=0;
while(count< MAX_CHAR_NUM)
{
letter=getch();
guess[count]=letter;
printf(" %c ",guess[count]);
count++;
};
guess[count]='\0';
//printf("\n \n The String you have typed is %s\n\n\n ",guess);
//getch();
for(i=0;i
{
if(guess[i] != ch[i] )
{
guess_flag=0;
}
}
if(guess_flag==1)
{
printf(" \n\n\n Congrats !!! \n\n\n You have guessed the string
correctly \n\n\n" );
}
if(guess_flag==0)
{
printf ("\n\n\n Sorry, Better luck next time \n\n You entered %s \n\n
The sequence was %s \n\n\n" ,guess,ch);
}

printf("\n\n To Play again enter 1 : ");
scanf("%d",&choice);
if(choice==1)
{
replay_flag=1;
if(guess_flag==1)
{
OLD_WAIT_TIME = WAIT_TIME+1;
LEVEL=MAX_CHAR_NUM+1;
}
if(guess_flag==0)
{
LEVEL=MAX_CHAR_NUM;
OLD_WAIT_TIME=WAIT_TIME;
}
goto start_mem_wiz;
}
clrscr();
printf("\n\n\n\n Hope you enjoyed playing MemWiz ! \n ");
printf("\n\n\n Thank you very much... \n\n\n\t\t\t\t\t
aamzillaa at gmail dot com \n\n ");
getch();
clrscr();
}// end of main

Thursday, September 13, 2007

AlphaBetz

My dear friends,I think I am addicted to memory training using alphabets these days.
If you have noticed my previous posts , you would find many games
dealing with alphabets…. This one , "AlphaBetz" is yet another memory
game which might help you to sharpen your long term memory.
In "AlphaBetz" , each English alphabet is given an index,
corresponding to its position. So A has an index 1, B has 2, Z has 26
and so on.
There are two modes. In the first mode you should guess the index of
an alphabet. In the second mode you are given the index and you should
guess the alphabet.
Hope you would all enjoy this game.
For any suggestions , improvements or advice please give me a comment
or mail me.
You can use the following code in any way you like , but please
mention my contribution.
Feeling so tired now… I should get some sleep soon… by the way , I can
remember the alphabets and corresponding indexes of all 26 English
alphabets. I used a system called pegging. Please send me a mail if
you are more interested in knowing about pegging.
With lots of love,
~aamzillaa~

//Alphabetz
//aamzillaa at gmail dot com
//13th September, 2007 AD
#include
#include
#include
#include
#include
void main()
{
int i=0,num=0,count=0,ok_flag=1,index=0;
int game=1,choice=0,correct=0,wrong=0,alph_correct=0,alph_wrong=0;
char ch_arr[30],alphabet;
start_alphabetz:
//initializing
i=0;num=0;count=0;ok_flag=1;index=0;
game=1;choice=0;correct=0;wrong=0;alph_correct=0;alph_wrong=0;
////
clrscr();
printf("\n\n\n\n\n\n\n\n\t AlphaBetz \n");
printf("\n\n\n\n\t\t\t\t\t\t\t aamzillaa at gmail dot com \n");
getch();
clrscr();
printf("\n\n\n");
printf("\n Welcome to Alphabetz \n");
printf("\n\n\n\n In this game you will be shown either an alphabet or ");
printf("\n the index of an alphabet \n");
printf("\n You should approrpriately guess the alphabet or index \n");
getch();
clrscr();

randomize();
while(1)
{
num=rand()%100;
ok_flag=1;
if ( num >= 65 && num <= 90 )
{
for( i=0; i < count ; i++)
{
if ( num==ch_arr[i] )
{
ok_flag=0;
}
}
if(ok_flag==1)
{
ch_arr[count]=num;
count++;
}
}
if(count>=26)
{
break;
}
};
clrscr();
printf("\n\n\n\n Game 1 : Decode index of an alphabet \n\n");
printf("\n Game 2 : Decode alphabet of an index \n\n");
printf("\n Enter Game Number : ");
scanf("%d",&game);
switch (game)
{
case 1:
for(i=0;i< 26;i++)
{
clrscr();
printf("\n\n\n\n\n\n\n\n\t\t (%d) Enter index of %c : ",i+1,ch_arr[i]);
scanf("%d",&index);
if( index == (ch_arr[i]-64) )
{
printf("\n\n\t\t Correct !!!\n ");
correct++;
}
else
{
printf("\n\n\t\t Wrong !!! Answer is %d\n ",(ch_arr[i]-64) );
wrong++;
delay(500);
}
delay(500);

}
clrscr();
printf("\n\n\n\n\n\n\n\n\t\t Score \n\n\t\t Correct : %d \n\n\t\t
Wrong : %d \n ",correct,wrong);
getch();
break;
case 2:
for(i=0;i< 26;i++)
{
clrscr();
printf("\n\n\n\n\n\n\n\n\t\t (%d) Enter alphabet for index %d :
",(i+1),(ch_arr[i]-64) );
alphabet =getch();
printf(" %c ",alphabet);
if(alphabet == ch_arr[i] )
{
printf("\n\t\t Correct !!!\n ");
alph_correct++;
}
else
{
printf("\n\t\t Wrong !!! Answer is %c \n ",ch_arr[i] );
alph_wrong++;
delay(500);
}
delay(500);
clrscr();
}
printf("\n\n\n\n\n\n\n\n\t\t Score\n\n\t\t Correct : %d \n\n\t\t
Wrong : %d \n ",alph_correct,alph_wrong);
getch();
break;
default:
printf("\n Invalid Game Number \n");
break;
}// end of switch
////////////////////////////////////////////
printf("\n\n To Play again enter 1 : ");
scanf("%d",&choice);
if(choice==1)
{
goto start_alphabetz;
}
clrscr();
printf("\n\n\n\n Hope you enjoyed playing AlphaBetz ! \n ");
printf("\n\n\n Thank you very much... \n\n\n\t\t\t\t\t
aamzillaa at gmail dot com \n\n ");
getch();
clrscr();
}

ZyX

Hi friends,~aamzillaa~ is back again with yet another cute little mind game.
How many of you can recite the English alphabets , A , B,C,D … till Z
without looking at your LKG notebook ? Me just kidding … If u didn't
know, you wouldn't be here.
But are you really sure that you know the alphabets so well?
Well, can you recite the alphabets starting from Z,Y,X… till A ?
The game ZyX (please don't pronounce it as SeX) is all about trying to
recite the alphabets backwards.
Please compile and see how far you can reach.
After one complete sleepless night of training I have at last learnt
to recite Z Y X ….B A .
I guess, I should have learnt to do it while I was still in my
kindergarten school. My teacher would have really been impressed !!!
Here comes the code… as usual , I would like to hear from you guys if
this game is any good.
With lots of love,
Yours truly
~aamzillaa~
********************************************************************************************
// ZyX
// ZyX is a game to train your long term memory
// aamzillaa at gmail dot com
// 13-09-2007 AD
#include
#include
#include
#define DELAY_TIME 1
#define A 65
#define Z 90
#define OFFSET 64
#define NUM_OF_ALPHABETS 26
void main()
{
int i=0,match_flag=1,choice;
char ch,temp_ch,ch_arr[30];
start_zyx:
//initializing
match_flag=1;
////////////////////

clrscr();
printf("\n\n\n\n\n\n\n\n\t ZyX \n");
printf("\n\n\n\n\t\t\t\t\t\t\t aamzillaa at gmail dot com \n");
getch();
clrscr();
printf("\n\n\n");
printf("\n Welcome to ZyX \n");
// printf("\n\n\n\n This is a memory game \n");
//clrscr();
printf("\n\n\n Please observe these letters carefully....\n\n\n\n");
for(i=Z;i>=A;i--)
{
printf(" %c ",i);
delay(1000*DELAY_TIME);
}
getch();
clrscr();
printf("\n\n\n Please try to enter the alphabets in reverse order,ie
Z Y X ... \n\n\n\n");

for(i=0;i< NUM_OF_ALPHABETS ;i++)
{
ch=getch();
ch_arr[i]=ch;
printf(" %c ",ch);
temp_ch =Z-i;
// printf(" temp_ch is %c ",temp_ch);
if(ch_arr[i] != temp_ch)
{
match_flag=0;
printf("\n\n You should have entered %c \n ",temp_ch );
break;
}
}
ch_arr[i+1]='\0';
printf("\n\n You typed : %s \n\n",ch_arr);
if(match_flag==0)
{
printf("\n Sorry ! \n\n Better luck next time \n\n");
printf("\n The correct reverse sequence of alphabets is ... \n\n\n");
for(i=Z;i>=A;i--)
{
printf(" %c ",i);
}
getch();
}
if(match_flag==1)
{
printf("\n Congrats !!! \n\n You have entered the reverse sequence
of alphabets correctly\n");
printf("\n\n You are indeed a memory wiz !!! \n\n ");
getch();
}

printf("\n\n To Play again enter 1 : ");
scanf("%d",&choice);
if(choice==1)
{
goto start_zyx;
}
clrscr();
printf("\n\n\n\n Hope you enjoyed playing ZyX ! \n ");
printf("\n\n\n Thank you very much... \n\n\n\t\t\t\t\t
aamzillaa at gmail dot com \n\n ");
getch();
clrscr();

}// end of main

MemWiz

Hi friends,

Who wouldn't like to have a photographic memory ? Well, probably what you might see in this post may not help you to get exactly a photographic memory, but it will surely help you to improve your short term memory very significantly. In this game, you will be  shown a random sequence of alphabets. You can decide how many alphabets you need to see , and also the time you need to memorize this random sequence of alphabets. After the specified time, the sequence disappears and then you are prompted to recollect the sequence you have just seen and type it. If you type the sequence correctly you win.

You shall find  the complete source code of the game below… You need a C-compiler to compile the source code. You can use it in any way you like , but I would be very much thankful if you would kindly let me know if you liked the game or whether you would like to see any improvements on it. If you decide to make a better version of this game  and  if you don't mind  kindly let me have a look on its source code.

By just un-commenting  some "printf" statements in the source code, you can set the time interval between displaying of new alphabets. Or you can use this to try memorizing a sequence of numbers or even a sequence containing numbers, capital letters, small letters and special characters.

I know , the following code is not "beautiful" there could be a hundred and one ways to improve it, if you have any suggestions to improve the efficiency or even the overall structure of the program , kindly leave a comment.

Well, I was playing MemWiz till now , and I could manage to remember a sequence of 11 random alphabets very easily. I hope to improve upon this in future by playing MemWiz daily.

Hope you all would love MemWiz , as much as I love it….

May God bless you to have a photographic memory eventually…

aamzillaa

// MemWiZ
// MemWiZ is a game to sharpen your short term memory
// aamzillaa at gmail dot com
// 12-09-2007 AD

#include
#include
#include
#include
#include


  void main()
   {

    int num,i=0,j=0,char_ok_flag=1,count=0,guess_flag=1,choice=0;
    char temp,ch[100],letter,guess[100];

int LOW_LIMIT= 65,HIGH_LIMIT= 90,LAST= 100, MAX_CHAR_NUM =5, DELAY_TIME= 1, WAIT_TIME= 1;


start_mem_wiz:
    //INITIALIZING
    i=0;
    j=0;
    char_ok_flag=1;
    count=0;
    guess_flag=1;
    choice=0;
    LOW_LIMIT= 65;
    HIGH_LIMIT= 90;
    LAST= 100;
    MAX_CHAR_NUM =5;
    DELAY_TIME= 1;
    WAIT_TIME= 1;



clrscr();
printf("\n\n\n\n\n\n\n\n\t MemWiz \n");
printf("\n\n\n\n\t\t\t\t\t\t\t aamzillaa at gmail dot com \n");

getch();
clrscr();
printf("\n\n\n\n\n\n");
printf("\n Welcome to MemWiz \n");
// printf("\n\n\n\n This is a memory game \n");


    printf("\n\n Enter Level  [1\\2\\...\\26] :  ");
    scanf("%d",&MAX_CHAR_NUM);

    // printf("\n\n Enter Delay in seconds between displaying new characters : ");
    // scanf("%d",&DELAY_TIME);

     printf("\n\n Enter time in seconds to memorize characters : ");
     scanf("%d",&WAIT_TIME);

    // printf("\n\n Enter Lower limit for character set (Default is 65) : ");
    // scanf("%d",&LOW_LIMIT);

    // printf("\n\n Enter Higher limit for character set (Default is 90) : ");
    // scanf("%d",&HIGH_LIMIT);

    // printf("\n\n Enter Last digit in randomizer (Default is 100) :  ");
    // scanf("%d",&LAST);

    clrscr();



    //ch[0]='a';

    randomize();

    while(1)
    {

    num=rand()% LAST  ;

    char_ok_flag=1;



if(num>=LOW_LIMIT && num <= HIGH_LIMIT )
{
    // checking whether number is already in array
      temp=num;

     for (j=0;j<=i;j++)
     {
if(temp==ch[j])
{
char_ok_flag = 0;
}
     }


     if(char_ok_flag==1)

{
//printf(" %c ", num );
ch[i]=num;
i++;


if (i >= MAX_CHAR_NUM)
{
ch[i]='\0';
break;
}
//getch();
}
}


    }// end of while

    //printf("\n\n %s \n Thank You ",ch);
    //getch();

    // delay(1000*DELAY_TIME);
    printf("\n\n\n\n Look carefully into the following letters...\n\n\n");

    for(i=0;i<=MAX_CHAR_NUM;i++)
{
printf(" %c ",ch[i]);
delay(1000*DELAY_TIME);
}

   delay(1000*WAIT_TIME);
   clrscr();
   //getch();
   printf("\n\n\n\n\n\n");
   printf("\n Please try to type the letters you saw a few moments ago...\n\n\n");
   //printf ("\n\n in the order you saw them \n\n\n");

   count=0;

   while(count< MAX_CHAR_NUM)
   {
   letter=getch();
   guess[count]=letter;
   printf(" %c ",guess[count]);
   count++;
   };

   guess[count]='\0';

   //printf("\n \n The String you have typed is %s\n\n\n ",guess);
   //getch();

   for(i=0;i
   {
    if(guess[i] != ch[i] )
{
guess_flag=0;

}
   }
     if(guess_flag==1)
       {
       printf(" \n\n\n Congrats !!! \n\n\n You have guessed the string correctly \n\n\n" );
       }
     if(guess_flag==0)
       {
printf ("\n\n\n Sorry, Better luck next time \n\n You entered %s \n\n The sequence was %s \n\n\n" ,guess,ch);
       }


       printf("\n\n To Play again enter 1 : ");
       scanf("%d",&choice);

       if(choice==1)
{
goto start_mem_wiz;
}

       clrscr();
       printf("\n\n\n\n Hope you enjoyed playing MemWiz ! \n ");
       printf("\n\n\n Thank you very much...  \n\n\n\t\t\t\t\t aamzillaa at gmail dot com \n\n ");
       getch();
       clrscr();

    }// end of main

Wednesday, September 5, 2007

Cows -N -Bulls

Hi Friends,Cows-N-Bulls , once up on a time , was our favourite game that we used
to play during boring lectures.This is a simple number guessing game.
But this game requires two players.
One to think about a random number and the other to guess that number
correctly within a specified number of chances. Well, with the
following code, the computer plays the role of your friend and thinks
about a number which you need to guess to win. Its a fairly simple and
cute game to play while you want some new means to kill time. I would
be greatly delighted if I could know about your opinions about this
game. Just compiple the following code in a C-compiler
Take care all you handsome hunks and beautiful angels.
Bye
aamzillaa :-)

// Cows-N-Bulls
// aamzillaa
// 29-7-007
#include
#include
#include
#include
void main()
{
int i,j,k,l,temp,r_digit,rnum,count;
int rnum1,rnum2,rnum3,rnum4,rnum5; //random number .. rnum
int d1,d2,d3,d4,d5; //digits of rnum
int gnum,gnum1,gnum2,gnum3,gnum4,gnum5; //guessed number.. gnum
int gd1,gd2,gd3,gd4,gd5; //guessed number's digits
int cow_count=0,bull_count=0; // cow : possition and number same
int rnum_arr[5],gnum_arr[5];
//bull : possition not same, number same
int no_of_digits=3,iterations=20,no_of_chances=10,chance_no=0,choice;
game_begins:
clrscr();
printf("\n\n\n\n\n\n\n\t Cows and Bulls \n");
printf("\n\n\n\n\t\t\t\t\t\t\t aamzillaa at gmail dot com \n");
getch();
clrscr();
printf("\n\n");
printf("\n Welcome to Cows-N-Bulls \n");
printf("\n\n\n\n This is a number guessing game \n");
printf("\n Guess correctly a random number with no repetitions in digits \n");
printf("\n Cow : Correct value,correct position \n");
printf("\n Bull: Correct value,incorrect position \n");
// printf("\n\n Number of chances: 10 \n\n\n\n");
printf("\n\n\n Input level (1/2/3/4/5) : ");
scanf("%d",&no_of_digits);
printf("\n\n Input Number of maximum chances required : ");
scanf("%d",&no_of_chances);
//STEP 1 : Generating a random number with (1-5) digits and no repetitions
for (i=0;i
{
temp=0;r_digit=0;rnum=0;count=0;
do
{
randomize();
temp=rand()%10;
// printf(" \n temp : %d \n ",temp);
if (temp !=r_digit)
{
rnum=rnum*10+temp;
r_digit=temp;
count++;
}
} while (count
if(rnum>32000 )
continue;
// printf("\n\n Random number with out repetitions is : %d \n ",rnum);
// getch();
break;
}

//printf("\n Starting Stage II... \n");getch(); clrscr();
/* ************************************************************ */
/* stage 2
/***************************************************************/

rnum1=rnum%10;
rnum2=rnum%100;
rnum3=rnum%1000;
rnum4=rnum%10000;
rnum5=rnum%100000;
d1=rnum%10;
d2=((rnum-rnum1)/10)%10;
d3=((rnum-rnum2)/100)%10;
d4=((rnum-rnum3)/1000)%10;
d5=((rnum-rnum4)/10000)%10;
// printf("\n %d %d %d %d %d %d \n \n",
// rnum, rnum1, rnum2, rnum3, rnum4, rnum5);
//
// printf("%d %d %d %d %d %d \n \n",
// rnum, d5, d4, d3, d2, d1);
// getch();

/* User input prompt do-while starts here, loop until chance_no

clrscr();
do {
printf(" Guess :-) ");
scanf ("%d",&gnum);
// printf("\n Guessed Number is %d \n ",gnum);
//getch();
cow_count=0;bull_count=0;
gnum1=gnum%10;
gnum2=gnum%100;
gnum3=gnum%1000;
gnum4=gnum%10000;
gnum5=gnum%100000;
gd1=gnum%10;
gd2=((gnum-gnum1)/10)%10;
gd3=((gnum-gnum2)/100)%10;
gd4=((gnum-gnum3)/1000)%10;
gd5=((gnum-gnum4)/10000)%10;

//printf("\n %d %d %d %d %d %d \n",
// gnum, gnum1, gnum2, gnum3, gnum4, gnum5);
//printf("\n %d %d %d %d %d %d \n \n",
// gnum, gd5, gd4, gd3, gd2, gd1);
//getch();

//printf("\n Starting Stage III... \n");getch(); clrscr();
/* ************************************************************ */
/* stage 3
/***************************************************************/

/* Insert here logic for finding number of cows and bulls */
rnum_arr[0]=d1;
rnum_arr[1]=d2;
rnum_arr[2]=d3;
rnum_arr[3]=d4;
rnum_arr[4]=d5;
gnum_arr[0]=gd1;
gnum_arr[1]=gd2;
gnum_arr[2]=gd3;
gnum_arr[3]=gd4;
gnum_arr[4]=gd5;
// printf("\n rnum_arr: %d %d %d %d %d %d \n",
// rnum, rnum_arr[4],rnum_arr[3],rnum_arr[2],rnum_arr[1],rnum_arr[0]);
// printf("\n gnum_arr: %d %d %d %d %d %d \n \n",
// gnum,gnum_arr[4],gnum_arr[3],gnum_arr[2],gnum_arr[1],gnum_arr[0] );
// getch();
/* checking the num of cows */
for (j=0;j
{
for (k=0;k
{
if (gnum_arr[j]==rnum_arr[k] && j==k )
{ cow_count=cow_count+1;
}
}
}
printf("\t\t Number of cows : %d ",cow_count);
//getch();
/* checking the num of bulls */
for (j=0;j
{
for (k=0;k
{
if (gnum_arr[j]==rnum_arr[k] && j!= k)
{ bull_count=bull_count+1;
}
}
}
printf(" Number of bulls : %d \n",bull_count);
printf(" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n
");
// getch();
chance_no=chance_no+1;
if (rnum==gnum)
{
//printf("\n************************************************\n");
printf(" \n\n\n\n \t\t Congratulations !!!\n ");
printf("\n\n\n\n \t\t\t\t The number is %d , You have won in %d
chances \n",rnum,chance_no);
printf(" \n\n\n\n \t\t\t\t\t\t aamzillaa at gmail dot com ;-) \n ");
//printf("\n************************************************\n");
getch();
clrscr();
break;
}
} while(chance_no
starting at the user input prompt
if(chance_no>=no_of_chances && rnum != gnum)
{
printf("\n\n\n\n\n\n\n \t\tSorry !!! Better Luck next time ! \n");
printf("\n \t\tThe number is %d \n",rnum);
printf("\n\n\n\n \t\t\t\t\t\t aamzillaa at gmail dot com ;-) \n");
getch();
clrscr();
}
clrscr();
printf("\n\n\n\n\n\n\n\n\n\n \tTo play again enter 1 , enter
anything else to quit\n");
scanf("%d",&choice);
if (choice==1)
{ chance_no=0;
goto game_begins;
}
clrscr();
printf("\n\n\n\n\n\n\n\n\t\t Hope you enjoyed ~Cows-N-Bulls~
\n\n\n\t\t\t Please let me know if you liked this :-)
\n\n\n\n\t\t\t\t\t\taamzillaa at gmail dot com\n");
getch();
} // end of main ... end of cows-n-bulls !!!

Saturday, September 1, 2007

Towers of Hanoi

This is going to be a very quick post... Please compile the following
code to play and see the solution for "towers of hanoi" puzzle
here comes the code...

// Towers of Hanoi
// 15th aug 2007
// aamzillaa
#include
#include
int count;
void main()
{
int num,choice=1;

clrscr();
printf("\n\n\n\n\n\n\n\n\n\t Towers of Hanoi \n");
printf("\n\n\t\t\t\t\t\t aamzillaa at gmail dot com \n");
getch();
clrscr();
while(choice==1)
{
clrscr();
count=0;
printf("\n Welcome to ""Towers of Hanoi"" puzzle ");
printf("\n\n\n\n There are N disks of different sizes on pole 1 ");
printf("\n Larger disks are below smaller disks ");
printf("\n Pole 2 and pole 3 are initially empty");
printf("\n Move all disks from pole 1 to pole 3 ");
printf("\n Only one move is possible at a time ");
printf("\n A Smaller disk can rest on top of a larger disk, \n but
not vice versa\n\n\t\t\t\t aamzillaa at gmail dot com ");
printf("\n\n Enter number of disks ");
scanf("%d",&num);
clrscr();
printf("\n Towers of Hanoi \n\n Solution for %d disks \n ",num);
toh(num,1,2,3);
printf("\n\n End of ""Towers of Hanoi"" puzzle \n ");
getch();
printf("\n\n Enter 1 to play again ");
scanf("%d",&choice);
};// end of while
}
toh(int n, int l, int m , int r)
{
if(n==0)
return 0;
toh(n-1,l,r,m);
count++;
printf("\n Step %d:\t Move disk from %d to %d ",count,l,r);
getch();
toh(n-1,m,l,r);
return 0;
}