Euclid's GCD algorithm and random musings...
Deprived of constant nurturing from me this blog will starve to death,
so today I'm just gonna scribble something. Well.. for the past
two-three weeks I was feeling so lazy that I had no urge to open my
books at all.. The laziness was mainly due to lack of motivation , and
the lack of motivation was mainly due to a sense of hopelessness. My
preparations for GATE is getting nowhere. There is a lot of stuff to
be learnt for an electronics guy to appear for the GATE CSE paper. The
portions I have to cover stands before me like a big mountain. I have
no idea which subject to start with. Roughly 15 weeks remaining for
GATE. I had started studying for GATE almost a month back.. Did cover
some portions from DS and OS and went through a lot of previous papers
and tried to get a feel about the exams. I think the analysis of
previous question papers did kind of discourage me. I couldn't answer
most of the questions and I am not at all familiar with so many
subjects like DBMS, Theory of computation, Discrete Maths, Computer
Organization, Computer networks etc etc.. the list is indeed a long
one.I really don't know how to study for GATE now. Should I concentrate
only on solving previous question papers ? Well, since I am an
electronics engineering student, most of subjects for Computer Science
is entirely new to me. So I really don't know what is being asked in
the questions. Without any clue of what is being asked in the question
I really don't know how to solve them , even with the help of text
books.
The solution to get some concept about the subjects would be to read
the standard text books, cover to cover. Well, I have been trying to
read some books lately..(Ullman, Knuth Tremblay and manohar etc etc )
but it takes so much time , that there is no hope of ever finishing
reading the text books of all subjects before December.
May be my dream to get into IIT may never materialize. I have been
doing a lot of orkutting lately and was trying to find the profiles of
students who have got into IITs this year. People who are studying in
IITs for M-tech are the people who inspire me the most these days. I
got to visit the homepages of many students studying in IITs. Well, I
have no idea how these people managed to achieve the most difficult
task of getting a rank within the top 100 in GATE 2007.
May be , without worrying about the result too much and thinking too
much about the most efficient and optimal way to cover the portions, I
should just relax and may be I should take it easy. May be , I should
accept the fact that I may never be able to get a rank good enough to
get into IIT. But , if i stop preparing for GATE now... my fate would
be much worse.. I may not get admission anywhere. I think its possible
for me to get into any one of the NITs , if I study hard from today
onwards... So I'm promising myself that I won't give up again...
Let the past be past... Today is gonna be a new beginning and from
today I intend to resume posting to my blog whatever that I am
studying. I have got a huge collection of question papers from various
sources and I am planning to solve them daily and shall post the
solutions to my blog. I may have to work really hard from today.. But
I am going to do it... Because if there is at least one percent chance
for me to get into IITs I want to utilize it. I shall forgive myself
for not starting preparing for GATE much earlier, and also for wasting
the past two-three weeks not studying anything significant. Today is
going to be a new beginning.....
I got this wonderful book, "Fundamental Algorithms-vol 1" - by Knuth.
It has some great introduction to discrete mathematics and data
structures and algorithms. I have just begun reading it.. Its gonna
take a while to finish it.. God, please bless my brain to concentrate
and understand and memorize the concepts in this book. Well... for the
first time in my life , I came across the first algorithm ever
invented by man as far as I know.. Its the Euclid's algorithm to find
the GCD f two numbers... Well... thought of giving it life... So here
comes a crude implementation of Euclid's GCD algorithm. I wonder how
to compute the time complexity and space complexity of any given
algorithm....
Anyway here comes the code...
// Euclid's algorithm to compute GCD of two numbers
// AamzillaA
// 26-10-2007 AD
#include
#include
void main()
{
int m=0,n=1,remainder=0,numerator,temp,num1,num2,choice=0,count=0;
begin:
count=0;
clrscr();
printf("\n\n\n Euclid's GCD Algorithm\n\n\n ");
printf(" \n Input first number : ");
scanf("%d",&num1);
m=num1;
printf("\n Input second number :");
scanf("%d",&num2);
n=num2;
if(n>m)
{
// swapping m, n to make m always greater than n
temp=m;
m=n;
n=temp;
}
start:
numerator = m/n;
remainder= m-(numerator*n);
count++;
printf(" \n\n (Step %d) Computing m\\n, m= %d , n= %d ,numerator = %d,
remainder = %d ",count,m,n,numerator,remainder);
getch();
if(remainder==0)
{
printf ("\n\n GCD of %d and %d is %d ",num1,num2,n);
getch();
goto end;
}
m=n;
n=remainder;
goto start;
end:
printf("\n\n Enter 1 to play again : ");
scanf("%d",&choice);
if(choice==1)
{
goto begin;
}
printf("\n\n Thanks for using Euclid's GCD algorithm \n\n aamzillaa at
gmail dot com \n ");
getch();
clrscr();
}
so today I'm just gonna scribble something. Well.. for the past
two-three weeks I was feeling so lazy that I had no urge to open my
books at all.. The laziness was mainly due to lack of motivation , and
the lack of motivation was mainly due to a sense of hopelessness. My
preparations for GATE is getting nowhere. There is a lot of stuff to
be learnt for an electronics guy to appear for the GATE CSE paper. The
portions I have to cover stands before me like a big mountain. I have
no idea which subject to start with. Roughly 15 weeks remaining for
GATE. I had started studying for GATE almost a month back.. Did cover
some portions from DS and OS and went through a lot of previous papers
and tried to get a feel about the exams. I think the analysis of
previous question papers did kind of discourage me. I couldn't answer
most of the questions and I am not at all familiar with so many
subjects like DBMS, Theory of computation, Discrete Maths, Computer
Organization, Computer networks etc etc.. the list is indeed a long
one.I really don't know how to study for GATE now. Should I concentrate
only on solving previous question papers ? Well, since I am an
electronics engineering student, most of subjects for Computer Science
is entirely new to me. So I really don't know what is being asked in
the questions. Without any clue of what is being asked in the question
I really don't know how to solve them , even with the help of text
books.
The solution to get some concept about the subjects would be to read
the standard text books, cover to cover. Well, I have been trying to
read some books lately..(Ullman, Knuth Tremblay and manohar etc etc )
but it takes so much time , that there is no hope of ever finishing
reading the text books of all subjects before December.
May be my dream to get into IIT may never materialize. I have been
doing a lot of orkutting lately and was trying to find the profiles of
students who have got into IITs this year. People who are studying in
IITs for M-tech are the people who inspire me the most these days. I
got to visit the homepages of many students studying in IITs. Well, I
have no idea how these people managed to achieve the most difficult
task of getting a rank within the top 100 in GATE 2007.
May be , without worrying about the result too much and thinking too
much about the most efficient and optimal way to cover the portions, I
should just relax and may be I should take it easy. May be , I should
accept the fact that I may never be able to get a rank good enough to
get into IIT. But , if i stop preparing for GATE now... my fate would
be much worse.. I may not get admission anywhere. I think its possible
for me to get into any one of the NITs , if I study hard from today
onwards... So I'm promising myself that I won't give up again...
Let the past be past... Today is gonna be a new beginning and from
today I intend to resume posting to my blog whatever that I am
studying. I have got a huge collection of question papers from various
sources and I am planning to solve them daily and shall post the
solutions to my blog. I may have to work really hard from today.. But
I am going to do it... Because if there is at least one percent chance
for me to get into IITs I want to utilize it. I shall forgive myself
for not starting preparing for GATE much earlier, and also for wasting
the past two-three weeks not studying anything significant. Today is
going to be a new beginning.....
I got this wonderful book, "Fundamental Algorithms-vol 1" - by Knuth.
It has some great introduction to discrete mathematics and data
structures and algorithms. I have just begun reading it.. Its gonna
take a while to finish it.. God, please bless my brain to concentrate
and understand and memorize the concepts in this book. Well... for the
first time in my life , I came across the first algorithm ever
invented by man as far as I know.. Its the Euclid's algorithm to find
the GCD f two numbers... Well... thought of giving it life... So here
comes a crude implementation of Euclid's GCD algorithm. I wonder how
to compute the time complexity and space complexity of any given
algorithm....
Anyway here comes the code...
// Euclid's algorithm to compute GCD of two numbers
// AamzillaA
// 26-10-2007 AD
#include
#include
void main()
{
int m=0,n=1,remainder=0,numerator,temp,num1,num2,choice=0,count=0;
begin:
count=0;
clrscr();
printf("\n\n\n Euclid's GCD Algorithm\n\n\n ");
printf(" \n Input first number : ");
scanf("%d",&num1);
m=num1;
printf("\n Input second number :");
scanf("%d",&num2);
n=num2;
if(n>m)
{
// swapping m, n to make m always greater than n
temp=m;
m=n;
n=temp;
}
start:
numerator = m/n;
remainder= m-(numerator*n);
count++;
printf(" \n\n (Step %d) Computing m\\n, m= %d , n= %d ,numerator = %d,
remainder = %d ",count,m,n,numerator,remainder);
getch();
if(remainder==0)
{
printf ("\n\n GCD of %d and %d is %d ",num1,num2,n);
getch();
goto end;
}
m=n;
n=remainder;
goto start;
end:
printf("\n\n Enter 1 to play again : ");
scanf("%d",&choice);
if(choice==1)
{
goto begin;
}
printf("\n\n Thanks for using Euclid's GCD algorithm \n\n aamzillaa at
gmail dot com \n ");
getch();
clrscr();
}
Thursday, October 4, 2007
Bubble Sort
I was studying Bubble sort yesterday. I still don't know how to find
the best-case , average cae , and worst case of the various sorting algoritms.Anyway, this is a small , ugly implementation of bubble sort.
Please note how the number of iterations vary with varying input size...
Bye
AamzillaA
// Bubble Sort Implementation
// AamzillaA
// 3rd Oct, 2007
// ref: Introduction to Algorithms by Cormen, page 38
#include
#include
void main()
{
int a[100];
int i=0,j=0,k=0,temp=0,count=0,array_size=0;
// Inputing the array
clrscr();
printf("\n Bubble sort \n\n " );
printf("\n Input Size of array : ");
scanf("%d",&array_size);
printf("\n\n");
for(k=0;k <=array_size-1 ;k++)
{
printf(" Input a[%d] : " ,k );
scanf("%d",&a[k]);
}
// Printing the array before sorting
printf("\n Iteration %d : ",count);
for(k=0;k <=array_size-1 ;k++)
{
printf(" %d " ,a[k] );
}
//getch();
// Starting Bubble sort algorithm
for (i=0;i<= array_size-1 ;i++)
{
for(j=array_size-1; j >=(i+1) ;j--)
{
if( a[j] > a[j-1] ) // This is the main line in Bubble sort algorithm
{
temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
// Printing temporary results
count++;
printf("\n Iteration %d : ",count);
for(k=0;k <=array_size-1 ;k++)
{
printf(" %d " ,a[k] );
}
//getch();
} // end of inner for loop
printf("\n\n******* i= %d *******\n\n",i);
getch();
} // end of outer for loop
// printing sorted array
printf("\n Sorted array in ascending order using Bubble Sort \n\n\n " );
for(k=0;k <=array_size-1 ;k++)
{
printf(" %d " ,a[k] );
}
printf("\n\n\n Array size : %d \n ",array_size);
printf("\n\n Total number of iterations : %d \n",count);
printf("\n\n\n Thank you for using Bubble Sort - AamzillaA \n\n\n");
getch();
}// end of main
the best-case , average cae , and worst case of the various sorting algoritms.Anyway, this is a small , ugly implementation of bubble sort.
Please note how the number of iterations vary with varying input size...
Bye
AamzillaA
// Bubble Sort Implementation
// AamzillaA
// 3rd Oct, 2007
// ref: Introduction to Algorithms by Cormen, page 38
#include
#include
void main()
{
int a[100];
int i=0,j=0,k=0,temp=0,count=0,array_size=0;
// Inputing the array
clrscr();
printf("\n Bubble sort \n\n " );
printf("\n Input Size of array : ");
scanf("%d",&array_size);
printf("\n\n");
for(k=0;k <=array_size-1 ;k++)
{
printf(" Input a[%d] : " ,k );
scanf("%d",&a[k]);
}
// Printing the array before sorting
printf("\n Iteration %d : ",count);
for(k=0;k <=array_size-1 ;k++)
{
printf(" %d " ,a[k] );
}
//getch();
// Starting Bubble sort algorithm
for (i=0;i<= array_size-1 ;i++)
{
for(j=array_size-1; j >=(i+1) ;j--)
{
if( a[j] > a[j-1] ) // This is the main line in Bubble sort algorithm
{
temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
// Printing temporary results
count++;
printf("\n Iteration %d : ",count);
for(k=0;k <=array_size-1 ;k++)
{
printf(" %d " ,a[k] );
}
//getch();
} // end of inner for loop
printf("\n\n******* i= %d *******\n\n",i);
getch();
} // end of outer for loop
// printing sorted array
printf("\n Sorted array in ascending order using Bubble Sort \n\n\n " );
for(k=0;k <=array_size-1 ;k++)
{
printf(" %d " ,a[k] );
}
printf("\n\n\n Array size : %d \n ",array_size);
printf("\n\n Total number of iterations : %d \n",count);
printf("\n\n\n Thank you for using Bubble Sort - AamzillaA \n\n\n");
getch();
}// end of main
Wednesday, October 3, 2007
Started reading "Introductions to Algorithms - 2nd ed" , by CLRS
week 2\days 10\02-10-07\Tuesday
Today I decided to start reading Cormen. Its 1000 page book. I don't
know how much time it would take to finish it. Anyway since its one of
the most popular books to study algorithm , I decided to spend the day
exploring it a bit. There is a huge online community devoted
Algorithm, I hope to be part of it after reading this book and getting
some knowledge about Algorithm.
Insertion sort
* is an in place algorithm
* best case running time , array already sorted, Θ(n)
* worst case running time, array sorted in reverse order , Θ(n^2)
Merge Sort
* Has better worst case running time than insertion sort.
* Based on divide and conquer
* Worst case running time, nlog(n), obtained by solving recurrence by
using master's theorem.
Growth of functions
O ................. < =
Ω .....................> =
Θ .................... =
o...................... <
ω.................... >
more to follow...
Today I decided to start reading Cormen. Its 1000 page book. I don't
know how much time it would take to finish it. Anyway since its one of
the most popular books to study algorithm , I decided to spend the day
exploring it a bit. There is a huge online community devoted
Algorithm, I hope to be part of it after reading this book and getting
some knowledge about Algorithm.
Insertion sort
* is an in place algorithm
* best case running time , array already sorted, Θ(n)
* worst case running time, array sorted in reverse order , Θ(n^2)
Merge Sort
* Has better worst case running time than insertion sort.
* Based on divide and conquer
* Worst case running time, nlog(n), obtained by solving recurrence by
using master's theorem.
Growth of functions
O ................. < =
Ω .....................> =
Θ .................... =
o...................... <
ω.................... >
more to follow...
My first date with TOC !
Originally written on 27-9-2007Helloo fellow GATE-ians,
Just back after watching "A very long Engagement", a french film about
war and love, on HBO.
Nice movie !!!
I have decided to go through TOC previous question papers today. Not
that i have finished studying Cinderella book, cover -to-cover.I just
want to see what TOC is all about. I just want to be acquainted with
the vocabulary of the subject and wanna get a general look and feel of
it. As I progress through the questions , I intend to note here the
things I come across, this is going to be a very careless and informal
post. So author is not responsible for any damages caused by reading
this post. The main purpose of this post is to serve as a memory aid
for my days effort and I'd be happy if any one of u will also get
benefited by this as a byproduct of my efforts to help myself. Why
simply waste an opportunity to do good, when not much effort is
required.
An online friend has given me a wonderful link to study TOC. If any
one of u are interested in having it, please leave ur mail id as a
comment at the end of this post. I'm really tired of posting links to
my blog at various orkut forums, I expected a lot of people would come
here, and that I would see a lot of comments congratulating my sincere
efforts to spread knowledge. I just see 2 comments. It really feels
bad to expect too much and get so little in return. Anyways, to
anticipate too much recognition for so trivial a job done by me, which
I thought would be of interest to a lot of people, was also foolishnes
from my part. So i have decided to stop posting links in forums for
the time being. Let people who have already visited this page come
back, without any prompting from my part. That would be the only
measure to judge the worth of my efforts to the GATE community at
large. More over, it spares me the ordeal of checking n-times my blog
and my posts to various blog to see whether anyone has congratulated
me for my work. Well, I know, I'm still being too childish at heart..
But nothing gives me a thrill like a word of thanks from some one who
has benefited from me in some way. It makes me so much happy when I
know something what I had done had influenced the life of another
human being in a positive manner. If we don't do any good to others,
isn't our life useless ?
Sorry for the senti stuff guys, but me began the day on the wrong note
today, and I had to get the bitterness out of my system, to keep
believing that life is still beautiful...
Here we go back to more serious discussions on TOC ....
May God bless Dr Eshwar , Dr.Chomsky, Dr.Turing ,Dr. Ullman,
Dr.Hopcroft, Dr. Motwani and all other bright minds who have made it
possible for us to expand the horizons of our minds, by exploring the
depths of Theory of computation.
*****************************
GATE 1986-2000 TOC questions
******************************
The language families and their properties.
1. Finite sets , accepts null set
2. Regular sets, Finite automata, type 3 or regular grammar, lexical analysis
3. Deterministic CFL , Deterministic Push Down Automata, LR(k)
grammar, parsing algorithms
4. CFL , PDA, Type 2 grammar or CFG, Syntax of high level languages ,HLL.
5. CSL , Turing machines that do not halt, Type-1 or CSG, Semantics of HLL
6. Recursive sets, Halting turing machines, Halting C programs
7. Recursively enumerable sets, Finite length C programs, Type 0 or
Unrestricted grammars.
8. Set of all formal languages.
******************************
cfg in the chomsky normal form has two adjacent non-terminals.
The regular sets are closed under practically all operations.
The regular languages cannot do parenthesis matching and the cfls
cannot do type checking
The regular languages cannot do parenthesis matching ant the cfls
cannot do type checking.
The cfls are not closed under intersection.
What is a turing machine ?
Any finite set is regular.
Where is the fig for Q15, G88 ? I didn't understand anything about
this question. It all looks like the math black board of Prof. Charley
in the AXN serial , numb3rs :(. By the way can u believe it ? Today He
actually discussed a logic problem from C.L Liu., the one about 3
boxes and a prize and how ur chances of winning becomes 2/3 from 1/3
if u change ur initial choice. !@#!@# man.... still nothing doing
with the problem. May be I should have a look at it later !!!
Context-free languages and regular languages are both closed under the
operation(s) of Union and Concatenation
What do u mean by context free language ? What context ?
What do u mean by regular language , what does the term regular mean
other than that it is accepted by a FA.
What does the term- X is "closed under the operation" Y means ?
How do we know that a given language is csl or cfl ? What is the test ?
The language {ww|w in (a+b)*} is a csl that is not a cfl but its
complement is a cfl. How ?
What is the difference between union and infinite union , ref: G89CS\Q15A
What is Chomsky Normal Form ? G89CS\Q15B
What is a push down automata ? G90CS\Q3(iv)
What is a recursive set ? What does the term recursion means ?
What is a recursively enumerable set ?
What is type 0 grammar ?
What is CSL ?
What is a right linear grammar ? Why do u say that a right linear
grammar generates a regular set ? /g90q15a
How do u construct a state diagram from a grammer ?
this post is not yet complete ..... more to follow... stay tuned ..
Just back after watching "A very long Engagement", a french film about
war and love, on HBO.
Nice movie !!!
I have decided to go through TOC previous question papers today. Not
that i have finished studying Cinderella book, cover -to-cover.I just
want to see what TOC is all about. I just want to be acquainted with
the vocabulary of the subject and wanna get a general look and feel of
it. As I progress through the questions , I intend to note here the
things I come across, this is going to be a very careless and informal
post. So author is not responsible for any damages caused by reading
this post. The main purpose of this post is to serve as a memory aid
for my days effort and I'd be happy if any one of u will also get
benefited by this as a byproduct of my efforts to help myself. Why
simply waste an opportunity to do good, when not much effort is
required.
An online friend has given me a wonderful link to study TOC. If any
one of u are interested in having it, please leave ur mail id as a
comment at the end of this post. I'm really tired of posting links to
my blog at various orkut forums, I expected a lot of people would come
here, and that I would see a lot of comments congratulating my sincere
efforts to spread knowledge. I just see 2 comments. It really feels
bad to expect too much and get so little in return. Anyways, to
anticipate too much recognition for so trivial a job done by me, which
I thought would be of interest to a lot of people, was also foolishnes
from my part. So i have decided to stop posting links in forums for
the time being. Let people who have already visited this page come
back, without any prompting from my part. That would be the only
measure to judge the worth of my efforts to the GATE community at
large. More over, it spares me the ordeal of checking n-times my blog
and my posts to various blog to see whether anyone has congratulated
me for my work. Well, I know, I'm still being too childish at heart..
But nothing gives me a thrill like a word of thanks from some one who
has benefited from me in some way. It makes me so much happy when I
know something what I had done had influenced the life of another
human being in a positive manner. If we don't do any good to others,
isn't our life useless ?
Sorry for the senti stuff guys, but me began the day on the wrong note
today, and I had to get the bitterness out of my system, to keep
believing that life is still beautiful...
Here we go back to more serious discussions on TOC ....
May God bless Dr Eshwar , Dr.Chomsky, Dr.Turing ,Dr. Ullman,
Dr.Hopcroft, Dr. Motwani and all other bright minds who have made it
possible for us to expand the horizons of our minds, by exploring the
depths of Theory of computation.
*****************************
GATE 1986-2000 TOC questions
******************************
The language families and their properties.
1. Finite sets , accepts null set
2. Regular sets, Finite automata, type 3 or regular grammar, lexical analysis
3. Deterministic CFL , Deterministic Push Down Automata, LR(k)
grammar, parsing algorithms
4. CFL , PDA, Type 2 grammar or CFG, Syntax of high level languages ,HLL.
5. CSL , Turing machines that do not halt, Type-1 or CSG, Semantics of HLL
6. Recursive sets, Halting turing machines, Halting C programs
7. Recursively enumerable sets, Finite length C programs, Type 0 or
Unrestricted grammars.
8. Set of all formal languages.
******************************
cfg in the chomsky normal form has two adjacent non-terminals.
The regular sets are closed under practically all operations.
The regular languages cannot do parenthesis matching and the cfls
cannot do type checking
The regular languages cannot do parenthesis matching ant the cfls
cannot do type checking.
The cfls are not closed under intersection.
What is a turing machine ?
Any finite set is regular.
Where is the fig for Q15, G88 ? I didn't understand anything about
this question. It all looks like the math black board of Prof. Charley
in the AXN serial , numb3rs :(. By the way can u believe it ? Today He
actually discussed a logic problem from C.L Liu., the one about 3
boxes and a prize and how ur chances of winning becomes 2/3 from 1/3
if u change ur initial choice. !@#!@# man.... still nothing doing
with the problem. May be I should have a look at it later !!!
Context-free languages and regular languages are both closed under the
operation(s) of Union and Concatenation
What do u mean by context free language ? What context ?
What do u mean by regular language , what does the term regular mean
other than that it is accepted by a FA.
What does the term- X is "closed under the operation" Y means ?
How do we know that a given language is csl or cfl ? What is the test ?
The language {ww|w in (a+b)*} is a csl that is not a cfl but its
complement is a cfl. How ?
What is the difference between union and infinite union , ref: G89CS\Q15A
What is Chomsky Normal Form ? G89CS\Q15B
What is a push down automata ? G90CS\Q3(iv)
What is a recursive set ? What does the term recursion means ?
What is a recursively enumerable set ?
What is type 0 grammar ?
What is CSL ?
What is a right linear grammar ? Why do u say that a right linear
grammar generates a regular set ? /g90q15a
How do u construct a state diagram from a grammer ?
this post is not yet complete ..... more to follow... stay tuned ..
Gate 2007 CSE Computer Networks Questions Solved.
Hi friends,I am still working on the solutions. Its not complete yet. Any
contributions to find the solutions will be greatly appreciated
AamzillaA
\week 1\days 4\26-09-07\wednesday
/////////////////////////////////////////////////////////////////////////////////////////////////////
GATE2007CSE Question Paper Analysis:
Total Marks for Computer Networks :14
1 mark questions : 2 [ 19(A), 20(C) ]
2 mark questions: 6 [ 65(D),66(D),67(C),68(B),69(C),70(B) ]
-AamzillaA-
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q19\CNW
Q. In Ethernet when Manchester encoding is used , the bit rate is
A) Half the baud rate.
B) Twice the baud rate.
C) Same as the baud rate.
D) None of the above.
ANS:
Suppose u want to transmit 01101 using Manchester
encoding, u first encode each 0 as a 0 to 1 transition , and each one
as a 1 to zero transition.
Bit Stream u want to send : 0 1
1 0 1
Bit Stream after Manchester encoding: 01 10 10
01 10
u see that each bit is represented by 2 signals or 2 bauds, and u see
that change in baud or change in the rate of baud or baud rate is
twice that of bit rate. So bit rate is half that of baud rate in
Manchester encoding.
For every bit either 0 or 1 there will be a transition of the signal
in the middle of the bit duration. So bit rate is half the baud rate.
Well , Baud rate is a measure of the number of times per second a
signal in a communications channel changes state. The state is usually
voltage level, frequency, or phase angle.Bit rate (i.e., bits per
second, abbreviated bps) is a measure of the number of data bits
(digital 0s and 1s) transmitted each second in a digital
communications channel. If simple frequency shift key modulation (FSK)
is used, each baud causes the transmission of just one bit, so the
baud rate is equal to the bit rate.
//////////You can skip to the solution of next question without
reading the following explanation if u are busy///////////////////
Note : Ever wondered how things that I type right now reaches you
traveling miles and miles of kilometers at speeds close to the speed
of light ? Well, ultimately the physical layer in my computer is going
to encode what ever I type into a stream of bits. And the modem sends
each bit through the telephone lines. You most probably don't want to
send the bits just as they are , the bits are encoded into signals.
Which means , each bit is translated into an equivalent form of
representation which might be an amplitude level of a sine wave in
ASK, (Amplitude shift keying) the frequency of the Sine wave in
FSK(Frequency Shift keying) and may be a phase angle in PSK (Phase
shift keying). The signal need not be a form of sine wave always .
It could be even a square wave. But Sine wave is preferred in digital
communication since pure sine wave consists of just one frequency when
u convert it from time domain to frequency domain using Fourier
series. In the case of square wave , instead of a single frequency , u
get a group of frequencies, which makes spectral analysis a little
difficult. A signal can represent either 1 bit, 2 bit, 4 bits, so on
depending on the encoding scheme used. In the case of manchester
encoding a bit is represented as 2 signal changes.
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q20\CNW
Q. Which one of the following use UDP as the transport protocol ?
A) HTTP
B) Telnet
C) DNS
D) SMTP
TCP is a connection oriented protocol, while UDP is a connectionless
protocol. We have all learned this in LKG rt ? UDP is less reliable
than TCP, but is faster. So for things like DNS, u can use UDP to get
faster response. The UDP protocol is transaction oriented, and
delivery and duplicate protection are not guaranteed. Applications
requiring ordered reliable delivery of streams of data should use the
Transmission Control Protocol
Refer RFC 768 to get more details about UDP.
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q65\CNW
Q. There are n stations in a slotted LAN. Each station attempts to
transmit with a probability p in each time slot. What is the
probability that ONLY one station transmits in a given time slot ?
A) np(1-p)n-1
B) (1-p)n-1
C) p(1-p)n-1
D)1-(1-p)n-1
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q66\CNW
Q. In a token ring network the transmission speed is 107 bps and the
propagation speed is 200 meters/m second. The one bit delay in this
network is equivalent to :
A) 500 meters of cable.
B) 200 meters of cable.
C) 20 meters of cable.
D)50 meters of cable.
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q67\CNW
Q. The address of a class B host is to be split into subnets with a
6-bit subnet number. What is the maximum number of subnets and the
maximum number of hosts in each subnet ?
A) 62 Subnets and 262142 hosts
B) 64 Subnets and 262142 hosts
C) 62 Subnets and 1022 hosts
D) 64 Subnets and 1024 hosts
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q68\CNW
Q. The message 11001001 is to be transmitted using CRC polynomial x3
+ 1 to protect it from errors. the message that should be transmitted
is :
A) 11001001000
B) 11001001011
C) 11001010
D)110010010011
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q69\CNW
Q. The distance between two stations M and N is L kilometers. All
frames are K bits long. The propagation delay per kilometer is t
seconds. Let R bits/second be the channel capacity. Assuming that
process delay is negligible, the minimum number of bits for the
sequence number field in a frame of maximum utilization , when sliding
window protocol is used is ;
A) ┌ log2 (2LtR+2K) / K ┐
B)┌ log2 (2LtR) / K ┐
C)┌ log2 (2LtR+K) / K ┐
D)┌ log2 (2LtR+K) / 2K ┐
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q69\CNW
Q.
Match the following.
P. SMTP 1. Application layer.
Q. BGP 2. Transport layer.
R. TCP 3. Data Link Layer.
S. PPP 4. Network Layer.
5. Physical layer.
////////////////////////////////////////////////////////////////////////////////////////////////////
contributions to find the solutions will be greatly appreciated
AamzillaA
\week 1\days 4\26-09-07\wednesday
/////////////////////////////////////////////////////////////////////////////////////////////////////
GATE2007CSE Question Paper Analysis:
Total Marks for Computer Networks :14
1 mark questions : 2 [ 19(A), 20(C) ]
2 mark questions: 6 [ 65(D),66(D),67(C),68(B),69(C),70(B) ]
-AamzillaA-
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q19\CNW
Q. In Ethernet when Manchester encoding is used , the bit rate is
A) Half the baud rate.
B) Twice the baud rate.
C) Same as the baud rate.
D) None of the above.
ANS:
Suppose u want to transmit 01101 using Manchester
encoding, u first encode each 0 as a 0 to 1 transition , and each one
as a 1 to zero transition.
Bit Stream u want to send : 0 1
1 0 1
Bit Stream after Manchester encoding: 01 10 10
01 10
u see that each bit is represented by 2 signals or 2 bauds, and u see
that change in baud or change in the rate of baud or baud rate is
twice that of bit rate. So bit rate is half that of baud rate in
Manchester encoding.
For every bit either 0 or 1 there will be a transition of the signal
in the middle of the bit duration. So bit rate is half the baud rate.
Well , Baud rate is a measure of the number of times per second a
signal in a communications channel changes state. The state is usually
voltage level, frequency, or phase angle.Bit rate (i.e., bits per
second, abbreviated bps) is a measure of the number of data bits
(digital 0s and 1s) transmitted each second in a digital
communications channel. If simple frequency shift key modulation (FSK)
is used, each baud causes the transmission of just one bit, so the
baud rate is equal to the bit rate.
//////////You can skip to the solution of next question without
reading the following explanation if u are busy///////////////////
Note : Ever wondered how things that I type right now reaches you
traveling miles and miles of kilometers at speeds close to the speed
of light ? Well, ultimately the physical layer in my computer is going
to encode what ever I type into a stream of bits. And the modem sends
each bit through the telephone lines. You most probably don't want to
send the bits just as they are , the bits are encoded into signals.
Which means , each bit is translated into an equivalent form of
representation which might be an amplitude level of a sine wave in
ASK, (Amplitude shift keying) the frequency of the Sine wave in
FSK(Frequency Shift keying) and may be a phase angle in PSK (Phase
shift keying). The signal need not be a form of sine wave always .
It could be even a square wave. But Sine wave is preferred in digital
communication since pure sine wave consists of just one frequency when
u convert it from time domain to frequency domain using Fourier
series. In the case of square wave , instead of a single frequency , u
get a group of frequencies, which makes spectral analysis a little
difficult. A signal can represent either 1 bit, 2 bit, 4 bits, so on
depending on the encoding scheme used. In the case of manchester
encoding a bit is represented as 2 signal changes.
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q20\CNW
Q. Which one of the following use UDP as the transport protocol ?
A) HTTP
B) Telnet
C) DNS
D) SMTP
TCP is a connection oriented protocol, while UDP is a connectionless
protocol. We have all learned this in LKG rt ? UDP is less reliable
than TCP, but is faster. So for things like DNS, u can use UDP to get
faster response. The UDP protocol is transaction oriented, and
delivery and duplicate protection are not guaranteed. Applications
requiring ordered reliable delivery of streams of data should use the
Transmission Control Protocol
Refer RFC 768 to get more details about UDP.
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q65\CNW
Q. There are n stations in a slotted LAN. Each station attempts to
transmit with a probability p in each time slot. What is the
probability that ONLY one station transmits in a given time slot ?
A) np(1-p)n-1
B) (1-p)n-1
C) p(1-p)n-1
D)1-(1-p)n-1
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q66\CNW
Q. In a token ring network the transmission speed is 107 bps and the
propagation speed is 200 meters/m second. The one bit delay in this
network is equivalent to :
A) 500 meters of cable.
B) 200 meters of cable.
C) 20 meters of cable.
D)50 meters of cable.
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q67\CNW
Q. The address of a class B host is to be split into subnets with a
6-bit subnet number. What is the maximum number of subnets and the
maximum number of hosts in each subnet ?
A) 62 Subnets and 262142 hosts
B) 64 Subnets and 262142 hosts
C) 62 Subnets and 1022 hosts
D) 64 Subnets and 1024 hosts
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q68\CNW
Q. The message 11001001 is to be transmitted using CRC polynomial x3
+ 1 to protect it from errors. the message that should be transmitted
is :
A) 11001001000
B) 11001001011
C) 11001010
D)110010010011
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q69\CNW
Q. The distance between two stations M and N is L kilometers. All
frames are K bits long. The propagation delay per kilometer is t
seconds. Let R bits/second be the channel capacity. Assuming that
process delay is negligible, the minimum number of bits for the
sequence number field in a frame of maximum utilization , when sliding
window protocol is used is ;
A) ┌ log2 (2LtR+2K) / K ┐
B)┌ log2 (2LtR) / K ┐
C)┌ log2 (2LtR+K) / K ┐
D)┌ log2 (2LtR+K) / 2K ┐
////////////////////////////////////////////////////////////////////////////////////////////////////
G07\CSE\Q69\CNW
Q.
Match the following.
P. SMTP 1. Application layer.
Q. BGP 2. Transport layer.
R. TCP 3. Data Link Layer.
S. PPP 4. Network Layer.
5. Physical layer.
////////////////////////////////////////////////////////////////////////////////////////////////////
Monday, October 1, 2007
October First Depression !!!
Ever since my last post I have been suffering from something calledinformation overload. The rate at which I was getting new online tutorials was
much much higher than the rate at which I could learn and digest them. I feel
now that too much availability of choices or resources will indeed affect your
productivity adversely. Ever since I started my GATE preparation on 23rd
Sep, 2007, the past 3 days where the most pathetic days in which all I had
done was downloading study materials from the net and thinking about what
my strategy should be to tackle GATE.. Still haven't any clue regarding what
would be the optimal way to spend my time till GATE , and also to achieve the
goal of getting a good rank. The thing that bothers me the most is that I have
not yet started reading standard text books in good ernest. All I was
doing last
week was solving previous question papers. The flow got disrupted, after I
came accross a TOC material from the net. I haven't stuied Theory of
Computation yet , and I think it was foolishness from my part to attempt the
question paper right away with out even bothering to learn the basics.
I think it
was that which really discouraged me. I was feeling so miserable at seeing the
questions asked for TOC , and knowing that there is just 4 months remaining
for GATE and that I have not yet started reading Ullman gives me real tension.
I some how reached managed to go through 1987-1989 GATE TOC questions
and it was then I thought I was so exhausted and then left studies and have not
yet. That was on last thursday. Friday, Saturday, Sunday was completely
wasted surfing the net and downloading various tutorials. I was really very
much amazed to find so much material from the MIT site. I don't know
whether any of them would be helpful from GATE prespective, but some
things were really cool. I got some really nice lecture notes to study discrete
maths.
Saw 3-5 movies this weekend. All average. May be I should restrict watching
too much TV for the coming 4 months or so. God knows whether I would be
able to live up to my expectation. The shows I really like these days are Mr.
Bean and Numbers.
And Mock GATE test series was about to begin on 30th sep, Sunday. I was
thinking about whether to join for test series or not for one complete day. I
already have more than enough questions with me in the form of GATE
previous question papers for IT and CS, and also a CS guide from GK
publishers which have a lot of mock GATE papers. I don't know whether I will
ever get enough time atleast to solve all the previous GATE papers completely
within the coming 4 months. I really don't know whether it would have been a
prudent if I had joined the test series , with out finishing the portions. One
complete day will be wasted by going to one test. They are giving 10 tests. So
it takes away 10 days. In 10 days can't I do more work by sitting at home and
solving previous GATE papers or questions from standard text books ?
I had appeared for the free mock GATE given by them, but contrary to my
expectation the number of people taking the exam for Computer Science was
really small. Nothing near the numbers that actually come for the real GATE
exam. So I don't think , that even if one performs well in a test series, it
guarantees success in the real exam, it might even give you a false sense of
confidence.
Another thing to consider was the fees. I was thinking about how many extra
books I can buy for the same amount of money. For 2500 , u could buy atleast
5 very good books of ur choice. Me being an eternal book lover, couldn't make
up my mind whether 2500 would be a good investment writting a test series
rather than buying great books.
But why I wanted to appear for them was to get the look and feel of writing a
GATE exam. Writing 10 model GATE papers could condition ur sub concious
mind , and then one the day of the real exam , you might be feeling very much
relaxed. So for all these reasons, I still plan to take test series
may be , after I
finish studying my portions. May be The months of october and november
should be spend reading the standard text books along with doing problems
from previous GATE papers. As of now, I plan to join the test series from
December onwards. But , if their discussion forum gets hot , I might plan to
join even earlier , not to miss the action , just when it happens.
So another month.... I pray to God that I might be able to cover the entire
GATE syllabus in a coarse manner this month. I still have no idea about
DBMS, TOC, COA, DIG and some portions in Discrete maths. Anyways,
rather than thinking about and getting tensed considering the impact of the
variables of life over which I have no control , I am missing the
oppurtunity to
do useful work upon things over which I have some kind of control. So rather
than looking too much in to the future, may be I should cultivate the habbit of
setting short term goals and concentrate my complete energy to achieveing
themwith in the specified deadline. Some times, doing too much analysis
indeed leads to paralysis. May be for now, I should top thinking and start
doing something...
19 weeks remaining for GATE. I still got enough time to get a good result.
This post was intended to motivate me and to shake off my lethargy and start
preparing for GATE once again. My apologies to anyone other than me who
might have read the above post and felt like it was a complete waste of their
time.
much much higher than the rate at which I could learn and digest them. I feel
now that too much availability of choices or resources will indeed affect your
productivity adversely. Ever since I started my GATE preparation on 23rd
Sep, 2007, the past 3 days where the most pathetic days in which all I had
done was downloading study materials from the net and thinking about what
my strategy should be to tackle GATE.. Still haven't any clue regarding what
would be the optimal way to spend my time till GATE , and also to achieve the
goal of getting a good rank. The thing that bothers me the most is that I have
not yet started reading standard text books in good ernest. All I was
doing last
week was solving previous question papers. The flow got disrupted, after I
came accross a TOC material from the net. I haven't stuied Theory of
Computation yet , and I think it was foolishness from my part to attempt the
question paper right away with out even bothering to learn the basics.
I think it
was that which really discouraged me. I was feeling so miserable at seeing the
questions asked for TOC , and knowing that there is just 4 months remaining
for GATE and that I have not yet started reading Ullman gives me real tension.
I some how reached managed to go through 1987-1989 GATE TOC questions
and it was then I thought I was so exhausted and then left studies and have not
yet. That was on last thursday. Friday, Saturday, Sunday was completely
wasted surfing the net and downloading various tutorials. I was really very
much amazed to find so much material from the MIT site. I don't know
whether any of them would be helpful from GATE prespective, but some
things were really cool. I got some really nice lecture notes to study discrete
maths.
Saw 3-5 movies this weekend. All average. May be I should restrict watching
too much TV for the coming 4 months or so. God knows whether I would be
able to live up to my expectation. The shows I really like these days are Mr.
Bean and Numbers.
And Mock GATE test series was about to begin on 30th sep, Sunday. I was
thinking about whether to join for test series or not for one complete day. I
already have more than enough questions with me in the form of GATE
previous question papers for IT and CS, and also a CS guide from GK
publishers which have a lot of mock GATE papers. I don't know whether I will
ever get enough time atleast to solve all the previous GATE papers completely
within the coming 4 months. I really don't know whether it would have been a
prudent if I had joined the test series , with out finishing the portions. One
complete day will be wasted by going to one test. They are giving 10 tests. So
it takes away 10 days. In 10 days can't I do more work by sitting at home and
solving previous GATE papers or questions from standard text books ?
I had appeared for the free mock GATE given by them, but contrary to my
expectation the number of people taking the exam for Computer Science was
really small. Nothing near the numbers that actually come for the real GATE
exam. So I don't think , that even if one performs well in a test series, it
guarantees success in the real exam, it might even give you a false sense of
confidence.
Another thing to consider was the fees. I was thinking about how many extra
books I can buy for the same amount of money. For 2500 , u could buy atleast
5 very good books of ur choice. Me being an eternal book lover, couldn't make
up my mind whether 2500 would be a good investment writting a test series
rather than buying great books.
But why I wanted to appear for them was to get the look and feel of writing a
GATE exam. Writing 10 model GATE papers could condition ur sub concious
mind , and then one the day of the real exam , you might be feeling very much
relaxed. So for all these reasons, I still plan to take test series
may be , after I
finish studying my portions. May be The months of october and november
should be spend reading the standard text books along with doing problems
from previous GATE papers. As of now, I plan to join the test series from
December onwards. But , if their discussion forum gets hot , I might plan to
join even earlier , not to miss the action , just when it happens.
So another month.... I pray to God that I might be able to cover the entire
GATE syllabus in a coarse manner this month. I still have no idea about
DBMS, TOC, COA, DIG and some portions in Discrete maths. Anyways,
rather than thinking about and getting tensed considering the impact of the
variables of life over which I have no control , I am missing the
oppurtunity to
do useful work upon things over which I have some kind of control. So rather
than looking too much in to the future, may be I should cultivate the habbit of
setting short term goals and concentrate my complete energy to achieveing
themwith in the specified deadline. Some times, doing too much analysis
indeed leads to paralysis. May be for now, I should top thinking and start
doing something...
19 weeks remaining for GATE. I still got enough time to get a good result.
This post was intended to motivate me and to shake off my lethargy and start
preparing for GATE once again. My apologies to anyone other than me who
might have read the above post and felt like it was a complete waste of their
time.
No comments:
Post a Comment