11/26/2009

GATE


OC chapter 2 Ullman


I just started reading Theory of Coputation from Ullman. Well.. I have to admit it. It is tough to understand things.. I skipped the very first chapter and started reading from the second chapter which deals with finite automata. I have read almost 10 pages befgore getting tired. I wonder whether I would ever be able to complete reading the relevant GATE portions from that book.

Recently I got an online copy of a book on automata written my an MIT prof called Sipster.

Some previous GATE toppers are recommending a book wrttten by cohen.

I am really confused how i will study automata...


Monday, July 21, 2008


Yogic way of life – Part III (Meditation)

Yogic way of Life – Part IIIMeditation
*********
The main objectives of meditation are
1. to feel and enjoy the state of being alive at the present moment,
irrespective of all external circumstances and challenges of life.
2.to improve concentration , awareness of breath, extent of total
relaxation, control over sense organs like ears, tongue, nose, eyes,
skin and above all mind.
3. to experience spiritual delight and enlightment
# The first step is to prepare for meditation. It would be better if
you could meditate in the morning at sunrise, with an empty stomach
after taking bath. Do it sitting on the floor on a mat. It is better
to have a place devoid of furniture,except the carpet, an atmosphere
which calms your mind and has good air circulation and above all which
is free from all external distractions. You should be able to feel
completely comfortable and secure at this place.
# First empty your bowels,got to bathroom and attend the cals of the
nature if necessary.
#Do Santhi Asan to calm your body and try to relax.
Stage I : Breath Awareness
**********************
1. Lie down in santhi asan. Close your eyes. Lift your right arm and
place the uter side of it just above your nostrils and do Kabala
Pranayam. The purpose is to feel the impact of breath on the outer
surfaces of the palm,and to bring your attention and concentration to
the breathing process. Do this for 2-3 minutes or as long as you feel
comfortable. Bring right hand back to initial posture of santhi asan.
2. Feel cool air entering ya nostrils,and warm air leaving out.
Observe carefully to feel it with your mind. Concentrate on this
process for sometime.
3. Feel oxygen coming in (energy coming in) Feel oxygen going out with
ya mind's eye.
4. imagine and feel good habits entering,bad habits leaving
5. good thoughts in , bad thoughts out.
6. As you breath in let your mind follow your breath through
nostrils,throat,to lungs. Follow the same process while breathing out.

Stage II: Control over the 5 senses
# sit in sugasan or lie down in santhi asan. don't sleep. you must be
completely comfortable with ya body now.
1. Control over ears
(i) Listen to just one single sound for 2 seconds. Concentrate on it.
Then move on to the next sound that may come. Do this for 2-3 minutes.
(ii) Close your ears. Observe your internal sounds like the sound of
breathing in, the sound of bones miving etc.
2. Control over the tongue.
(i) Concentrate on ya tongue.
(ii) Feel the good and bad things you have tasted in the past 24 hours
one by one.
(iii) Try to recreate that taste with the help of ya mind.
3. Control over nose.
(i) Concentrate on ya nose.
(ii) Feel the smell of all things that you had smelt during the past
24 hours with the help of ya mind.
4. Control over ya eyes.
(i) Close ya eyes.
(ii) Observe the different colors that form on the inner surface of ya
closed eye lid.
(iii) With ya mind, try to see what all things your eyes has seen
during the past 24 hours. Rewind from present moment, like try to see
what your eyes has seen just before shutting them close, and rewind
from the to 24 hours back slowly.
5.Control over skin.
(i) Feel the cool air of fan/breeze on ya skin.
(ii) Feel the clothes touching ya body.
(iii) Feel the effect of gravity on ya body.
Stage III: Antarang Yog Sadhana
1. Pratyahaar(No thought, No Body Movement, Concentrate on the silence
between two thoughts)
2. Dharana
3. Dhyan
Pratyahaar:
The aim is to make the mind still and empty. It is a preparation for
deeper meditation. Mind constantly runs after thoughts one after
another. But in between 2 thoughts mind is silent for a very short
moment. Catch that moment. Try to feel the silence between the
thoughts and try to prolong its duration. Try to delay the thoughts.
Make mind empty slowly.
Dharana:
There are 4 centers in our body. ie 4 chakras.
Concentrate on
1. The pit of the navel. (For getting physical fitness)
(i)Join five fingers of right arm and gently touch the pit of ya navel
a few times with full concentration.
(ii)Recreate the same effect with the help of ya mind.
2. Pit of ya heart. (For Spiritual fitness)
Repeat same procedure as above after joining 5 fingers of right hand.
3. Pit of the throat(Mental fitness)
4. The area between eyebrows. (Intellectual fitness)
See the divine light,which is sooo minute…but sooo precious like a
diamond… soo much brith even than the sun..It should be the supreme
light.Try to see it with ya mind while concentrating on the area
between eye brows.
Dhyan.
******
It is the ultimate aim of yoga… It is the union of mind with your
spirit… the union of ya spirit with God.
With your mind , enter into your body through the heart
charka(center). You should be fully aware,alert and concentrated..
Enter inside your body and search for your soul. Find it and enjoy
supreme bliss.Remain in that state of bliss as long as you can.It is
the ultimate aim of yoga.
End your meditation by chanting OM…and praying the regular prayers.
Thanks for coming,
AamzillaA

Sunday, July 20, 2008


Yogic way of life – Part II

Yogic way of life – Part IIYogic way of having food.
***************************
"Eat liquids, drink solids"
"Rest a while after lunch"
"Walk a mile after dinner"
"Roti-Sabji-Dal-Chawal"

1. Food timings
Breakfast: 7-9 am
Lunch: 1-2pm
Tea:3:30-4:30pm
Dinner:7-8pm
Water: Drink a glass of water every hour if you don't have any kidney
problems. (If you have problems with ya kidneys consult ya doctor to
know about how much water you can drink in a day.) Don't drink water 1
hour before or after or while having food. Try to drink 2-3 liters of
water everyday. If you have a kidney problem or indigestion don't
drink too much water.
Note: Drink a glass of water when u get up. Drink a glass of butter
milk , one hour after lunch. Drink a glass of milk, before you sleep.
Eat dry fruits like badam, cashew, resins to increase your memory
power.
Guidelines on how to eat well
********************************
1. Eat only when u feel hungry.
2. Breakfast: 7-9 am
Lunch 1-2pm
Dinner 7-8pm
Tea and Snacks 3:30-4:30pm
Water : Every one hour drink one glass of water. Don't drink water
while eating. Don't drink water one hour before or after having food.
Try to drink 2-3 liters of water daily.
Buttermilk: Drink a glass of butter milk one hour after lunch.
Milk:Drink a glass of milk one hour after dinner,before going to sleep.
Vajrasan: Sit in Vajrasan for 30 min after dinner, before going to sleep.
Yoga Nidra: Practise Yoganidra for complete relaxation.
Sleep: Go to sleep only 2 hours after having dinner. Ideally have your
dinner before sunset. Give time for ya food to pass through ya
stomach.
Posture: It is good to sit (sugasan) on floor on a mat and eat. If
this is not possible try to sit in sugasan on a wooden chair and eat
slowly after prayer. Never waste food.
Avoid: Meat, Fish, Eggs, Potatoes etc. You can eat them once in a
month if you want, but please don't more than once.
Nails: Make sure the nails in ya right hand is trimmed.
Yoga Nidra: Practice Yoga Nidra before sleeping. It will free your
mind from all tensions and will give you complete relaxation to body,
mind and soul.
Surya Namaskar: Practice Surya Namaskar, ideally in an open space,
with plently of fresh air, at the time of sun rise. Practice Shanthi
Asan compulsorily before and after Surya Namaskars. Do 5-6 rounds
daily. Do more rounds if you want to improve your stamina.
Thank you ,
AamzillaA

Yogic way of life - Part I

Yogic way of life"Early to bed, early to rise, Makes a man,
healthy wealthy and wise"
Part I
"Getting ready for the day"
1. Go to sleep by 10 pm
2. 6 – 8 hours of sleep is required for a normal healthy person
3. Get up atleast 45-60 minutes before sunrise. If you sleep by 10 pm
, you can get up by 4:00 am
4. Pray for a while, lying down on the bed itself. Expel all negative
thoughts and emotions from your mind. Lie down in Shanthi Asan for a
while and start performing the following 7 asanas
i. Niralambasan
ii. Shanthi Asan
iii. Supta pawan muktasan
iv. Tanasan
v. Paschimottasan
vi. Utkut Pavan Muktasan
vii. Nispanda Bhavasan
Note: Attend nature calls in-between if you feel the urge.
5. Wash your hands first. Pray for a while, praising God for giving
you hands and pray to Him to give you strength to do good deeds today.
6. Wash your eyes and face and mouth
i. Massage your eyes to increase eye power
ii. Gargle with a little salty warm water
iii. Fill your mouth with water and blow up your cheeks like a
balloon. It is good for your face and mouth
iv. For having string teeth
Use Danthamrutham to brush, don't use brush if you can, use your
middle finger for that. It is good to brush once in a while with salt,
using middle finger. Use up and down motion while brushing. Don't use
sideways motion that might damage your teeth. For strong teeth , don't
drink cool drinks, have ice creams or chocolates. For strong teeth
breath maximum air using mouth and make your cheeks like a balloon,
and chew air and massage your cheeks while doing this. Press your
teeth hard while attending the calls of nature.
Use your thump to clean the upper palate of your mouth. Make sure your
nails are cut short. Make side ways motion using your thump.
Use soft tongue cleaner to clean your tongue, without hurting your taste buds.
Gargle and clean your mouth and throat
7. Drink initially a glass of warm/normal water initially after
cleaning your mouth. Finally you should be able to drink one liter of
water at this stage.
8. Do Shanka-Prakshalan asanas (2-3) rounds
Sarpasan, Urdhva Hastasan, Kati Chakrasan, Udar Akarshanasan
9. Now go to toilet and relieve yourself. If you take care of your
diet and perform yogasanas and have good thoughts you shall never
suffer from constipation. If you are presently suffering from
constipation, drink another glass of warm water and repeat shanka
prakshalan asanas. You should make it a practice to shit in the
morning itself. It is advisable if you could shit twice everyday. In
the morning and also before going to sleep at night.
10. You should take bath after shitting. You should once in a week
massage your whole body with oil and should then take bath. If it is
not possible, try to do it once in a month. Make your Sunday bath
elaborate and ritualistic so that you get complete relaxation to your
body.
Everyday before bathing, massage your body with your hands. First pour
water on your feet, then pour water on your whole body. Be in a
prayerful mood while bathing. Dedicate each part of your body to God
and pray to make them strong and healthy. pray to God to heal your
diseases, if you have any. Wipe your body with a clean towel. Change
your under garments daily. Under garments should be preferably made of
cotton.
11. Once in a while do Jala-Neti after taking bath. While doing "Jala
Neti" in the specially designed tumbler, make sure the water you use
is slightly warm, saline , drinking water. Put a little teaspoon of
salt to make the warm salind water.
After performing Jala Neti, you should compulsorily perform the
following three things.
First perform pranayamam, close your ears with your fingers and with
force breath out continuously.(Bhastrika pranayamam) Repeat it by
closing one nostril at a time.
After performing Jala neti, you should compulsorily perform Bhastrika
Pranayamam to blow out any remaining water particles from your
nostrils. If water gets blocked in ya nostrils you may get frequent
colds.
After Jala Neti and pranayamam compulsorily perform Shanthi Asan. When
ever you do pranayam you should perfom Shanthi Asan before and after
Pranayamam. Some yoga Gurus suggests that you should NOT do yogasans
after HEAVY pranayamam. They say yogasanas are a preparation for
pranayamam and pranayamam is a preparation for meditation and
meditation is the door to knowledge and wisdom and peace.
Pranayamam should be done at sunrise, when the atmosphere is so pure.
Do Surya Namaskars at sun rise, when the atmosphere is so pure. Do
Surya Namaskars at Sunrise. All yogasanas , especially Surya Namaskars
must be performed on an empty stomach.
12. After bath and possibly Jala Neti + Pranayam+Shanthi Asan. Sit in
either Sugasan or Padmasan or Ardha Padmasan or Vajrasan and Meditate
and pray and plan your day till Sun rises.
13. If you have enough time in the morning do yogasanas for one hour
around the time of sun rise. Always take care to do yogasanas on empty
stomach(ie atleast 5 hours after taking heavy food or 3 hours after
tea+snacks)
If you have time , first start your yoga practice with prayer
then perform
(i)micro yoga, then
(ii)shanthi asan and Surya Namaskar
(Do 3 rounds of Surya Namaskars Initially, gradually increase number
of rounds depending on ya stamina and available time. No food should
be taken atleast 5 hours before Surya Namaskars. Do Shanthi Asan
atleast for 2 minutes compulsorily before and after Surya Namaskars)
(iii) Shanthi Asan
(iv) Other Yogasanas according to time available
(v) Shanthi Asan
(vi) Prayer.
14. It is advisable to take bath after yogasanas even if you had taken
bath in the morning. Or else take bath after Yogasanas, skip bath
before starting yoga practice.
15. All these things should be finished before 7 am.
Thank you for visiting this page.
AamzillaA

Friday, July 18, 2008


Institutes conducting GATE

Hi freinds,GATE is conducted by IITs or IISc. Some times it is helpful to know
which institute is conducting the GATE exam. Here comes the list of
institutes who has conducted GATE before.
AamzillaA
***********************
GATE 2009 (Most probably will be conducted by IIT Madras)
GATE 2008 IISc Bangalore
GATE 2007 IIT Kanpur
GATE 2006 IIT Kharagpur
GATE 2005 IIT Bombay
GATE 2004 IIT Delhi
GATE 2003 IIT Madras
GATE 2002 IISc Banglore
GATE 2001 IIT Kanpur
GATE 2000 IIT Kharagpur
GATE 1999 IIT Bombay
GATE 1998 IIT Delhi
GATE 1997 IIT Madras
GATE 1996 IISc Banglore
GATE 1995 IIT Kanpur
GATE 1994 IIT Kharagpur
GATE 1993 IIT Bombay
GATE 1992 IIT Delhi
GATE 1991 IIT Madras
GATE 1990 IISc Banglore
GATE 1989 IIT Kanpur
GATE 1988 IIT Kharagpur
GATE 1987 IIT Bombay
GATE 1988 IIT Delhi
GATE 1987 IIT Madras
GATE 1986 IISc Banglore

Guidance for GATE 2009 (Computer Science) by AIR 98

Hi friends,Here is yet another GATE guide from orkut. Hope this would be helpful.
Link to the original thread:
http://www.orkut.co.in/CommMsgs.aspx?cmm=5582348&tid=2591717978069554910&kw=AIR+98
Thanks,
AamzillaA
***********************
Guidance for GATE'09(Computer Science)...from AIR98
To All GATE Aspirants,
i have received many requests for guidance for GATE'09 so i m trying
to put them all together here.
i ve got AIR 98 (percentile 99.44 branch CS) in GATE'08 and this
letter is just an attempt to analyze -
1. how i succeeded to reach to rank 98 , and
2. why i failed to get rank in first 30

also i want to clear that these are just my views to look towards GATE
and it may differ from person to person, so my request to all is take
this letter just as guidance but build ur own strategy to unlock the
GATE!!!
So let me start with most important part of this process (cracking the
exam) i.e. analysis of paper!!!
ANALYSIS OF PAPER
First of all, go through all previous papers. Especially, the papers
of the year when organizing institute is same as that of GATE'09.
GATE'08 was organized by IISc. The previous years when IISc was
organizing institute were year 2002, 1996, and 1990. When I solved
these papers, I found out that there are some concepts on which IISc
was focusing more. E.g. In each of these papers there was question on:
B/B+ tree,
Newton-Raphson Method,
More stress on CO and Digital,
Mathematics is more inclined towards Calculus than Discrete Maths
On the contrary problems on Probability, Networks and Compilers were
not much difficult…..
If u solve GATE'08 paper u ll find the same thing here also….
So we can say that GATE paper is much predictive. so first task to do
is go through all the papers (I think the organizing institute this
time may be Madras and prev years when madras was organizing institute
were 1991, 1997, 2003…) and find out the similarities….stress on them.
I m not saying to skip all other topics…but practically its really
difficult (not impossible) to focus on all the subjects….so, I just
want to say, if u want to skip some topics don't skip the topics
stressed by the organizing institute. Also don't underestimate the
remaining topics …. here comes my first mistake…I under-estimated
Mar 30
स्थलांतर...
Probability and solved very simple problem wrongly ….result was -2.5 marks []
But warning is if u skip some topics u must be perfect in all the
remaining topics. And the definition of perfect, here, is there must
be only one person to solve particular problem on that topic before
u….the paper setter!!!.....no one else
Now next point is,
Every GATE paper contains three kinds of questions:
1. problems on tricky concepts
if u know the concept, ur done…
2. Difficult problems
U ve to put ur brains to solve these problems…
3. Practically unsolvable problems
U may find totally unknown and new concepts which couldn't be solved
in 3hrs time this typically includes problems on CO and probability.
To crack the GATE u ve to solve correctly ALL the problems of first
kind….for 2nd kind, the more the problem u solve, lesser the rank u ll
get!!!
Now while solving the paper, I solved it in 3 passes….
1. Solve all the problems that u can solve undoubtfully…means answer
only when ur 200% sure about the ans ….for this pass I ve given 2hrs
during the paper which is quite sufficient
2. Check all the problems…Remember while checking have thorough
checking….check whether u ve marked correct option…check
question-to-ans correspondence is correct…many times it happens that
we solve Q.30…leave Q31 blank and after solving Q32 we mark option in
front of Q31….here comes my another mistake…I haven't checked three of
questions for which I thought no checking is necessary…but I lost 7.5
marks….this pass may take 15-20 min…
3. after careful checking only turn towards problems for which u are
doubt full…try to rethink on these problems…u may solve 3-4 of them…

I ld like to explain u how much imp ur hit ratio….in GATE'08 I
attempted 54 questions…out of which 14 are of 1 marks and 40 are of
marks…out of 14, 11 are correct and 3 came to be wrong…and out of
40…28 came to be correct and 12 came to be wrong…so my score, I think
is round about 60/150….
Mar 30
स्थलांतर...
Now if I ld ve attempted only 11 one marked questions and 28 2 marked
questions….for which I was 200% sure…then my score ld ve been
67/150….means surely I ld ve got rank <50

Continuing the discussion about marks…
I think, for easy paper(like GATE'07) 75/150 = IIT
For difficult paper(like GATE'08) …u can see even 60/150 is done!!!
So in general attempt 50-60 questions with hit ratio >90% and ur through!!!
Well,
Now I ll come to preparation part of the GATE
BOOKS and SUBJECT ANALYSIS
Discrete Mathematics
MOST IMP subject as far as CS is concerned
First order logic:
prepare it from Trembley-Manohar and solve exercise from Discrete
Mathematics and Application by Kenneth Rosen. Easy topic. Once concept
is clear marks are urs….
Important rules of thumb are given in Kenneth Rosen
Probability and Combinatorics:
I skipped this part. But Kenneth Rosen again has variety of problems
on this topic.
Set Theory:
Trembley-Manohar
Boolean algebra,Groups, Lattice, Relations:
Kenneth Rosen has good discussion on Relations and Lattice.
Book by K.D.Joshi on Discrete Maths has good derivations regarding
enumerating the relations…go through it, it ll surely help to build up
the ideas…
For Boolean Algebra and Group Theory again book by Trembley-Manoher is
good, but for exercises I used book by Ross(I don't remember the full
name of author…sorry for that)
Trembley-Manoher includes good theorems in Group Theory…
Linear Algebra, Calculus and Numerical Methods:
For these subjects I used the course books by local authors which we
used for semester exams…
There are some quickie methods to find out inverse of matrix, eigen
values and eigen vectors, determinant…understand those from Profs in
ur college
Recurrence Relations:
Kenneth Rosen includes some rules of thumb for Particular Solutions of
Recurrence Relations…once u got them solving problems on RR is work of
few secods…
Particularly for Recurrence Relations, try to find ans by eliminating
wrong options…
Mar 30
स्थलांतर...
i.e. if u know f(1)=a and f(0)=b…try to put 1 and 0 in options and see
where u get correct ans….believe me in most of cases u ll get quick
and correct ans by this way….
Graph Theory:
MOST IMP topic for CS
Try to go through all possible books and material for Graph Theory.
Note down the general formulae/theorems given in books…read them frequently…
Kenneth Rosen includes good discussion in most of the concepts of GT.
Graph Theory by Douglas West is also gr8 book.

Theory of Computation
Book by
John C. Martin
This is gr8 for Regular Languages, Finite Automata…theory and problems
Cohen
This includes variety of problems on every other concept of TOC…theory
is also very perfect (as good as spoon feeding) …especially for
pumping lemma
Peter Linz
Again good theory …easy to understand….problems on Turing Machine are tricky…
Michel Sipser
This book is good especially for Un-decidability, Recursive and RE
languages, NP-completeness
For NP-completeness book on Algorithms by Sahani is also good
I suggest u to read these books in following order
1. Read concepts from Cohen….u also can refer Peter Linz…solve exercises
2. Solve exercise from John Martin
3. Read Michel Sipser for advanced concepts
statutory warning: TOC book by Ullman is injurious to brain …but do
read this book once…this contains, exclusively, concepts of
Homomorphism, HALF of LANGUAGE etc…
Digital Logic:
Morris Mano…morris mano…morris mano!!!!!!!!
There are ppts on the department website of IIT-D regardin this
course…which contains good discussion on some concepts like Fault
Detection and Hazards in Circuits…
Walkerly is also good book…
There is also a book Fundamentals of Digital Circuits by A. Anand
Kumar which includes thorough discussion on Number System(don't
under-estimate this point…there are many tricky concepts in it!!!)
Mar 30
स्थलांतर...
Computer Organization and Architecture:
Book by Morris Mano(not the same as Digital…there is separate book for
CO)…it contains good theory and problems for Addressing Modes, DMA and
IO…refer latest edition coz previous editions doesn't include concepts
of Register Window….so I could not attempt problem on it
Book by J. P. Hays contains good discussion on Micro-programming and
Hard-Wired Design, also it contains good formulae for Pipelining
J. P. Hays also contain thorough discussion on Floating Point number formats….
Good and exclusive formulae for Secondary Storage…
Book by Zaky
It has good theory for Pipelining
Also thorough discussion in Cache memories…. Don't skip any word and
any problem written about cache in this book
Algorithms
Read each and every word written in book by Cormen…solve every other
excersies….this is enough…solution manual is available over the
internet…search on esnips.com
Also there is one book, I found on flazx.com, named "Problems on
Algorithms"…this book contains only problems …no theory…..but good
book
Book by Sahani is also good
IMP subject for CS
Get perfection in:
Master Theorem and Asymptotic notations
Data Structure and Programming
For programming u must be great in concepts of Pointers and Recursion.
For tricky problems related with programming visit department websites
of various foreign universities and solve the assignments given there…
For data structure
Book by Alan Weiss is great and sufficient for theory….
For problems on Data Structure…nothing is sufficient….solve as many as u can…
To understand various operations on various Trees and Heaps there are
many Java Applets available over the internet…they will demonstrate
it…
Compiler Design
Ullman…nothing else!!!
For lexical analysis some problems are asked on C program like: a C
program is given and we are asked to find out number of tokens
generated…so to understand tokens in C…book by Denis Ritchie is good
Mar 30
स्थलांतर...
Read each and every word given on Parsers in Ullman…there are many
tricks given to find out whether grammar is LL or LR or CLR or LALR
statutory warning: this book requires too much patience to understand
Many students skip this subject but Ullman is best for
Parsers, S-attributed and L-attributed SDT, Scopes of variables,
Passing of Parameters, Code Optimization (defn only)
Prepare at least these points
Operating Systems
Book by Galvin is very good for concepts
Modern Operating System by Andrew Tanenbaum is the best book for OS.
It contains great number of problems. Also includes some of theory
that is not included in Galvin's book.
Operating Systems by Stallings also contains tricky problems…soln
manual is also available on esnips.com
I also suggest Schaum's Series (author: J. Archer Harris) book on
operating systems for problems. It is a very good compilation of
problems from Galvin, Tanenbaum and Stallings. Also soln are given.
While preparing prepare operating system along with CO. it will be
helpful for Memory Management.
statutory warning: while solving problems on OS keep ur head cooool
and….recheck them thrice…better not to attempt problems on OS in
doubtful situation
Database
For physical database organization (theory) and SQL, RA, TRC
Book by Raghuramkrishnan…soln manual is available
For transaction management and Normalization
Book by Korth … soln manual is available
For ER diagrams and problems on physical database organization
Book by Navathe….available on ebookee.com
Once u finish reading topics in Korth and Raghuramkrishnan and ur
concepts are clear, then onwards I suggest u to read and stick up with
Navathe coz it contains lot of techniques and algorithms not given any
where else
Computer Networks
For application layer protocols
"Computer Networking – A top down approach" by Kurose and Ross
available on flazx.com
"TCP/IP" by Forouzan
Mar 30
स्थलांतर...
For Frame Formats, TCP and IP Header formats
"TCP/IP" by Forouzan
Data Link Layer, Network Layer, Transport Layer
"Computer Networks" by Tanenbaum
Go through all the exercises given in the book…soln manual is
available on esnips.com
Some Suggestions for Preparation/Study
1. Strictly use Reference books, don't rely on any class notes.
2. In first phase of ur study (in month of May-June) go through all
GATE papers. Solve them by ur own. Once problem is solved try to find
out similar problems from refernce books and solve them. This will fix
up the concepts well.
3. Use department websites of various universities to get latest assignments.
4. plan ur schedule in such a way that u ll be able to finish up whole
syllabus in month of Dec. from jan onwards try to solve papers.
5. keep ur feb first week for revision only…don't read any new
concepts ( I tried to do calculus in month of Feb…i couldn't even
solve simple problem on limits…total time-waste)
hope this was not too boring …and will be helpful to all of u….
if u have any doubts…feel free to ask me anytime…

also i request all those who have cracked GATE to add their experinces
here to help out those who are going to appear for GATE'09

Tuesday, July 15, 2008


GATE CS guide from Mayur (AIR 16)

Hi friends , Just now stumbled upon some very valuable information while browsing
through orkut threads. The following GATE guide is written by Mayur,
who has secured AIR 16 in GATE CS 2009. Here is a link to Mayur's
profile on orkut if guys visiting this blog wants to thank the
original author of this GATE guide.
http://www.orkut.co.in/Profile.aspx?uid=16559036155955276195
original thread in orkut:
http://www.orkut.co.in/Profile.aspx?uid=16559036155955276195
Hope this would be helpful to people preparing for GATE CS 2009.
AamzillaA
****************************
Guidance for GATE By AIR 16....
HOW TO CRACK GATE?(AIR 16 2008 CSE)
This is what I think is required to crack GATE.
1>>Good technical knowledge
2>>Good understanding of Basic Concepts
3>>Ability to apply the knowledge and concepts on variety of problems
To Develop 1 and 2 you will need to read and understand reference
books, to develop 3 you will need to solve the problems. Now question
is from where to get the problems or the MCQs, the answer is the
problems are given at the back of every chapter in the reference
books, you will need to solve those problems,may be not all of them.
Problems reveal lot of truth and clear our misconception and false
convictions. And GATE has certain property that lot of Quesions in it
are based on concepts that are revealed in certain problems in
reference books. So its really really important to have a shot at the
problems.
Now here is the list of reference books that I used for preparation.
• DISCRETE MATHEMATICS
I started my preparation with discrete maths, and I would recommend
you also to start with this perticular subject because this is the
subject from where Computer Science spreads out. Understanding of this
subject is very important. I used following books:
1>>"Discrete maths and its applications" By Kenneth Rosen
This is an excellent book for GATE preps. Lot of problems are given at
the end of every chapter plus answers are also given to odd numbered
exercises. The explaination in this book is really very good and "easy
to understand". This book is must read for GATE preps.
2>>book by Tremblay and Manohar
I recommend you to read this book after you have read Rosen's book.
The contents in this book is hard to comprehend. You need to have your
basics cleared before you attempt this book. This book is also a "must
read". I also have the lecture notes on discrete maths from some prof
at McGuire university the advanced counting and recurrence relation
part is good in these notes you can download them from my esnips
profile.
May 26
MAYUR
• ALGORITHMS
I recommend to you to read this subject along with Discrete maths or
after you have completed discrete maths. I used only one book for this
subject and found that to be more than enough for GATE.
1>>"Introduction to Algorithms" By T.H.Cormen et al.
This is "THE" book for Algorithms. The Book is simply brilliant, it
makes you understand every details of Algorithms. So this book is a
must read. Although I did not read the entire thing. Here is the list
of chapters that I had read. If you are interested of course you can
read the entire book.
Chapter 1,2,3,4[excluding 4.4],6,7[excluding 7.3],8,10,11[excluding
11.5],12[excluding 12.4],18,22,23,24[excluding 24.4 and 24.5] for
NP-Completeness you can read 34 also.
In addition to this book I strongly recommend you to see the video
lectures from MIT. The lectures are given by Lieserson[who BTW is also
one of the authors of CLRS] and Erik demaine. The lectures are
absolutely brilliant. You may download them from ocw.mit.edu
• DATASTRUCTURES
I did not read this subject exclusively. I mostly participated in
discussions in Algorithms and datastructures communities on orkut .
That is i think more than enough.
• THEORETICAL COMPUTER SCIENCE
I initially tried to decipher Ullman's book but I found the content
too much for my brain to comprehend. So I switched to "Introduction to
Computer Theory" By Daniel Cohen. The contents in this book are lucid.
Also solving or atleast attempting the problems in the exercises is a
must. But its really great if you could read Ullman.
• DATABASE MANAGEMENT SYSTEMS
I used Korth and Navathe for this. Initially I read korth because it
is lucid and then only for normalization i read Navathe. The database
design part in korth is difficult so read this part with utmost
concentration and you may require several readings before you begin to
understand things.
May 26
MAYUR
• OPERATING SYSTEMS
Read this from following books:
1>>Operating System Concepts By Galvin et al.
2>>Stallings
Attempt problems in Stallings they are very important especially
problems on memory management and virtual memory. In Galvin the theory
on memory management is excellent.
• Digital Design
Read "Digital Design" By morris mano [period].
• COMPUTER ARCHITECTURE
Read this from following books
1>>"Computer Architecture" By Morris mano
2>>"Computer Organization" By Zacky,hamacher
3>>"Computer Organization Hardware/Software Interface" By Hannessey
and Patterson
Read book 1 almost completely then read memory system from book 2 then
you can read
book 3, I had read only the performance measurement chapter from book
3 as it is not given in any other book and also solve numericals from
exercises they are very very important. I recommend you to read this
subject after "Digital Design".
• COMPUTER NETWORKS
I had read this subject only from forouzan and had read some chapters
from Comer's book. Attempt the exercises from forouzan they are
important.
• C programming
You read this from "the C programming language" by kernighan and
Ritchie that is more than enough plus spend some time in actually
programming in C that is the best way you can learn C.
• C++
I dont know C++ much and I did not read anything for C++. Dont be
spoiled, you can read C++ complete reference if you wish to.
May 26
MAYUR
• Compiler Design
Did not read this subject at all. "People" say Ullman's book is
excellent so you can read it from Ullman if you believe "People".
In the final phase of your preps "try" to solve GATE papers. The
answers for the GATE papers are not present anywhere but still you
should attempt them anyway. This will give you confidence that you can
actually solve GATE.
You can read all the subjects given here you can skip one or two if
you dont have much time But more important thing is to "MASTER"
atleast 2 or 3 subjects. Also actively participate in discussions at
GATE CS or GATE CS/IT 2009 and Algorithms and Datastructures community
in orkut.com that helps alot in patching few loopholes in our concepts
and enhancing your problem solving skills. Thats it guys,this much is
I think enough to crack GATE. You can ofcourse Device your own methods
and set of books. Just be confident you can do it!
These are few URLs Which I think "might" be helpful
1>>Opencourseware at MIT>>>>OCW
2>>Lots of computer science resources and e-books at >>>>>>esnips
3>>My esnips profile >>>>>>here

Sunday, February 17, 2008


Follow your dreams

If while pursuing your distant dreams..
Your bright hopes turn grey..
Don't wait for reassuring words..
Or hands to lead the way..
For seldom will you find a soul..
With dreams the same as yours..
Not often will another help you..
Pass through untried doors..If inner forces urge you..
To take a course unknown..
Be ready to go all the way.
Yes, all the way alone...
Thats not to say you shouldn't..
Draw lessons from the best..
Just don't depend on lauding words...
To spur you on your quest..
Find confidence within your heart..
And let it be your guide..
Strive ever harder towards your dream..
And they won't be denied..
- Bruce B Wilma

Friday, February 15, 2008


GATE 2008 Answer Keys ( CS , IT , EC , EE , CE , ME , PY )

Ladies and gentlemen , uncles and aunties , boys and girls....Its AamzillaA again…
Please find the answer keys for the following papers of GATE 2008 below.
* GATE 2008 : Computer Science and Engineering (CS)
* GATE 2008 :Information Technology (IT)
* GATE 2008:Electronics and Communication Engineering (EC)
* GATE 2008: Electrical Engineering(EE)
* GATE 2008 :Civil Engineering(CE)
* GATE 2008:Mechanical Engineering(ME)
* GATE2008 : Production Engineering(PY)
Just now got them from various online forums...
AamzillaA thought why not simply put them all in this blog to help
people visiting this blog...
Hoping blindly that they are reliable accurate and correct...
If you find any errors in them,
kindly leave a comment below this post.
You will get a FREE "Thank You" mail from me with in 2 weeks
;-)

Take care and keep smiling what ever might be your GATE score…..
Life doesn't end or begin with GATE…
With lots of love,
Yours truly,
AamzillaA
****http://living-in-shadows.blogspot.com*****

GATE 2008 CS Keys
(Computer Science and Engineering)
***********AamzillaA********************
1.A
2.D
3.
4.D
5.A
6.D
7.C
8.C
9.D
10.B
11.-
12.-
13.D
14.B
15.-
16.A
17.D
18.A
19.C
20.D
21.A
22.C
23.C
24.B
25.B
26.A
27.C
28.A
29.A
30.C
31.B
32.C
33.C
34.D
35.A
36.D
37.C
38.-
39.D
40.B
41.A
42.D
43.B
44.B
45.D
46.C
47.B
48.D
49.A
50.A
51.B
52.C
53.A
54.A
55.-
56.D
57.C
58.B
59.D
60.B
61.D
62.B
63.C
64.-
65.A
66.B
67.B
68.A
69.C
70.C
71.D
72.B
73.C
74.B
75.C
76.B
77.B
78.D
79.
80.-
81.-
82.-
83.-
84.C
85.A
NOTES :
*3. No Option is correct. Correct Answer is a ¹ 5.
*79. No Option is correct. Correct Answer is 13.
****http://living-in-shadows.blogspot.com*****

GATE 2008 IT keys
(Information Technology)
***********AamzillaA********************
1.A
2.B
3.B
4.C
5.C
6.B
7.D
8.A
9.B
10.C
11.C
12.A
13.A
14.B
15.D
16.C
17.D
18.C
19.C
20.C
21.C
22.D
23.C
24.A
25.A
26.D
27.D
28.A
29.D
30.A
31.A
32.A
33.B
34.C
35.A
36.A
37.D
38.A
39.B
40.C
41.B
42.B
43.B
44.A
45.C
46.D
47.B
48.D
49.B
50.C
51.C
52.B
53.D
54.B
55.C
56.D
57.D
58.D
59.C
60.A
61.-
62.-
63.-
64.B
65.-
66.C
67.D
68.D
69.C
70.C
71.B
72.C
73.B
74.-
75.-
76.B
77.B
78.D
79.A
80.D
81.A
82.D
83.C
84.D
85.C
****http://living-in-shadows.blogspot.com*****

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

NOTES : *58. No Option is correct. Correct Answer is P R + Q R S
+ P Q R S + P S.
****http://living-in-shadows.blogspot.com*****

GATE 2008 EE Keys
(Electrical Engineering)
***********AamzillaA********************
1.A
2.B
3.C
4.C
5.D
6.A
7.D
8.C
9.B
10.A
11.D
12.B
13.D
14.D
15.D
16.B
17.A
18.D
19.D
20.D
21.C
22.C
23.A
24.B
25.B
26.B
27.C
28.B
29.D
30.A
31.B
32.A
33.D
34.A
35.A
36.D
37.B
38.B
39.C
40.C
41.D
42.B
43.A
44.A
45.B
46.B
47.A
48.C
49.B
50.B
51.C
52.C
53.B
54.D
55.B
56.A
57.B
58.C
59.B
60.C
61.C
62.B
63.C
64.A
65.A
66.C
67.C
68.C
69.B
70.A
71.B
72.C
73.D
74.B
75.C
76.B
77.B
78.D
79.A
80.D
81.B
82.A
83.A
84.D
85.A
****http://living-in-shadows.blogspot.com*****

GATE 2008 CE Keys
(Civil engineering)
***********AamzillaA********************
1.B
2.A
3.D
4.D
5.B
6.C
7.C
8.D
9.B
10.B
11.B
12.A
13.A
14.C
15.D
16.C
17.C
18.A
19.C
20.A
21.D
22.A
23.D
24.D
25.B
26.B
27.A
28.D
29.C
30.A
31.D
32.D
*33.
34.C
35.D
36.A
37.D
38.A
*39.
40.C
41.B
42.A
43.C
44.B
45.A
46.A
47.B
48.B
49.B
50.A
51.C
52.–
53.–
54.–
55.B
56.B
57.B
58.A
59.C
60.D
61.A
62.B
63.A
64.B
65.A
66.A
67.B
68.A
69.C
70.D
71.A
72.B
73.C
74.B
75.C
76.–
77.–
78.C
79.C
80.C
81.C
82.D
83.C
84.C
85.B
NOTES : *33. No Answer .
*39. No Answer .
****http://living-in-shadows.blogspot.com*****

GATE 2008 ME keys
(Mechanical Engineering )
***********AamzillaA********************
1.C
2.D
3.B
4.A
5.C
6.D
7.D
8.D
9.B
10.D
11.B
12.A
13.C
14.C
15.D
16.B
17.C
18.A
19.C
20.C
21.A
22.B
23.B
24.D
25.A
26.D
27.B
28.C
29.A
30.B
31.D
32.B
33.A
34.B
35.B
36.D
37.D
38.C
39.D
40.B
41.B
*42.
43.A
44.C
45.C
46.B
47.A
48.C
49.A
50.D
51.D
52.A
53.D
54.B
55.C
56.D
57.C
58.D
59.D
60.C
61.D
62.D
63.B
64.D
65.C
66.A
67.B
68.A
69.C
70.A
71.C
72.D
73.C
74.B
75.A
76.B
77.A
78.A
79.B
80.A
81.B
82.D
83.B
84.B
85.C
NOTES : *42. No Option is correct. Correct Answer is 4.88 MPa.
****http://living-in-shadows.blogspot.com*****

GATE 2008 PY Keys
(Production Engineering)
***********AamzillaA********************
1.A
2.B
3.C
4.D
5.A
6.A
7.D
8.D
9.D
10.D
11.C
12.-
13.C
14.C
15.D
16.A
17.C
18.A
19.D
20.A
21.A
22.D
23.C
24.A
25.A
26.B
27.D
28.C
*29.
30.-
31.D
32.-
33.-
34.C
35.B
36.-
37.A
38.A
39.B
40.A
41.A
42.A
43.C
44.-
45.A
46.-
47.C
48.B
49.A
50.C
51.B
*52.
53.B
54.A
55.B
56.D
57.C
58.B
59.B
*60.
61.C
62.C
63.B
64.D
*65.
66.B
67.A
68.D
69.D
70.B
71.D
72.C
73.B
74.D
75.D
76.C
77.D
78.-
79.-
80.B
81.A
82.D
83.B
84.B
85.A
NOTES :
*29. No Option is correct
*52. No Option is correct. Correct Answer is 20.
*60. No Option is correct. Correct Answer is 14.52°.
*65. No Option is correct. Correct Answer is (P - D)t.
*******************************************************
Wish you all a very happy + successful + healthy + rich + sexy future !!!
;-)
AamzillaA
*******************************************************

Thursday, January 10, 2008


The unreachable star

To dream the impossible dream
To fight the unbeatable foe
To bear with unbearable sorrow
And to run where the brave dare not go
To right the unrightable wrong
And to love pure and chaste from afar
To try when your arms are too weary
To reach the unreachable star
This is my quest
To follow that star
No matter how hopeless
No matter how far
To fight for the right
Without question or pause
To be willing to march, march into hell
For that heavenly cause
And I know If I'll only be true
To this glorious quest
That my heart
Will lie peaceful and calm
When I'm laid to my rest
And the world will be better for this
That one man, scorned and covered with scars,
Still strove with his last ounce of courage
To reach the unreachable, the unreachable,
The unreachable star
And I'll always dream
The impossible dream
Yes, and I'll reach
The unreachable star

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;
}