One Stop GATE Forum: 1999 paper

Message

    Q1.2 : no. of binary relations on set of n elements : ? 

I think, binary mappings are n^2, so relations are 2^ (n^2) 
plz tell me if m correct 

Q 1.13: arrange n numbers in array so that all negative numbers are before all positive numbers. Whts the worst case exchanges? 

I think ths goes as follows: let i = fisrt index, j = last index 
compare i th and j th elemet: 
in proper order, decrement j 
in reverse order, exchange and increment i 

bt m nt able to figure out worst case? 
Is ths right way of doing? 

Q 1.15.. plz refer fig in paper, i got A i.e. 0 articulation points 

Q 2.3 : L is a set given to be with R as reflexive, anti-symetric and transitive, Also, L has LUB and GLB for every pair in it. 
It means , L is Poset as well as lattice.. correct? 

Q 2.16.. plz explain me how to solve such prblms : 
No. of full and half adders reqd for adding 2 16 bit numbers : ?? 
8 HA, 8 FA 
1 HA , 15 FA 
16 HA, 0 FA 
4 HA 12 FA 
????? 

plzzzzzzzzz help 

Author	Message
manju Senior Member Joined: 20Feb2007 Online Status: Offline Posts: 221	Topic: 1999 paper Posted: 22Feb2007 at 2:21pm
	Q1.2 : no. of binary relations on set of n elements : ? I think, binary mappings are n^2, so relations are 2^ (n^2) plz tell me if m correct Q 1.13: arrange n numbers in array so that all negative numbers are before all positive numbers. Whts the worst case exchanges? I think ths goes as follows: let i = fisrt index, j = last index compare i th and j th elemet: in proper order, decrement j in reverse order, exchange and increment i bt m nt able to figure out worst case? Is ths right way of doing? Q 1.15.. plz refer fig in paper, i got A i.e. 0 articulation points Q 2.3 : L is a set given to be with R as reflexive, anti-symetric and transitive, Also, L has LUB and GLB for every pair in it. It means , L is Poset as well as lattice.. correct? Q 2.16.. plz explain me how to solve such prblms : No. of full and half adders reqd for adding 2 16 bit numbers : ?? 8 HA, 8 FA 1 HA , 15 FA 16 HA, 0 FA 4 HA 12 FA ????? plzzzzzzzzz help Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged

balu Senior Member Joined: 20Feb2007 Online Status: Offline Posts: 236	Posted: 22Feb2007 at 2:23pm
	1.2. u r right.its 2^(n^2) 1.13. i also dont know d worst case.will it be all negatives at the end or alternating +ve and -ve values? 1.15.nodes 2,3,5 are the articulation pts.hence ans is 3 2.16. 15FA and one HA.half adder doesnt require a carry in which is equivalent to an FA with C0=0 2.5 i think arbitrary gotos shudnt b there..(b) is the only option wich satisfies that.
	IP Logged


One Stop GATE Forum : GATE Technical Discussions : GATE CS