ISC 2010 COMPUTER SCIENCE PAPER 1 THEORY Question 1.

a) If X=ABC + ABC + ABC + ABC then find the value of X when A=1; B=0; C=1 b) Verify if, !"# +$)=" %$) u&in' truth table! () )raw the lo'i( (ir(uit of *+, u&in' *A*) 'ate only! d) Convert the followin' fun(tion into it& Canoni(al -u./+f01rodu(t& for.2 3"X,4,5)= 6"0,1,7,8) e) -how that the dual of $, + $, + $, i& e9ual to the (o.1le.ent of $, + $" , + ,) [ 2 x 5 = 10 Question 2. a) -tate the differen(e between an interfa(e and a (la&&! b) Convert the followin' infi: notation to 1o&tfi: notation! " A+B) ; C < ") +=) () A (hara(ter array B>8?>@? ha& a ba&e addre&& 10A@ at 0,0! Cal(ulate the addre&& at B>B?>C? if the array i& &tored Colu.n DaEor wi&e! =a(h (hara(ter re9uire& B byte& of &tora'e! d) -tate the u&e of e:(e1tion handlin'! *a.e the two ty1e& of e:(e1tion&! e) i) Fhat i& the wor&t/(a&e (o.1le:ity of the followin' (ode &e'.ent 2 for"int i=0;iG*;i++) H -e9uen(e of &tate.ent& I for"int E=0;EGD;E++) H -e9uen(e of &tate.ent& I ii) Jow would the (o.1le:ity (han'e if the &e(ond loo1 went to * in&tead of DK [ 2 x 5 = 10

Question !. a) Lhe followin' fun(tion nu.ber&"int) and nu.ber&1"int) are a 1art of &o.e (la&&! An&wer the 9ue&tion& 'iven below &howin' the dry run;worMin'2 1ubli( void nu.ber&"int n) H if"nN0) H -y&te.!out!1rint"n+O P); nu.ber&"n/B); -y&te.!out!1rint"n+O P); I I 1ubli( -trin' nu.ber&1"int n) H If"nG=0) return PO; return"nu.ber&"n/1)+n+O P; I Fhat will be the out1ut of the fun(tion nu.ber&"int n) when n=7K [2 i) ii) Fhat will the fun(tion nu.ber&1"int n) return when n=@K [2 iii) -tate in one line what i& the fun(tion nu.ber&1"int) doin' a1art fro. re(ur&ionK [1 b) Lhe followin' fun(tion i& a 1art of &o.e (la&&! It &ort& the array a>? in a&(endin' order u&in' in&ertion &ort te(hni9ue! Lhere are &o.e 1la(e& in the (ode .arMed by K1K, KBK, KCK, KAK, K7K whi(h .u&t be re1la(ed by e:1re&&ion; &tate.ent &o that the fun(tion worM& (orre(tly! void in&ert&ort"int a>?) H int .= K1K; int b,I,t; for"i=KBK;iG.;i++) H t=a>i?; b=i/1; while"KCKN=0 QQ tGa>b?) H a>b+1?= a>b?; KAK; I K7K=t; I I Fhat i& the e:1re&&ion or &tate.ent at K1K [1 i) ii) Fhat i& the e:1re&&ion or &tate.ent at KBK [1 iii) Fhat i& the e:1re&&ion or &tate.ent at KCK [1 iv) Fhat i& the e:1re&&ion or &tate.ent at KAK [1 v) Fhat i& the e:1re&&ion or &tate.ent at K7K [1

P"#t II Se$tion A An&wer any three 9ue&tion& Question %. a) Riven 3" ,$,,,-)= 6"0,B,7,8,S,10,11,1C,1A,17) ,edu(e the above e:1re&&ion by u&in' A/ variable T/Da1, &howin' the variou& 'rou1& " i) i!e! o(tal&, 9uad& and 1air&)! ii) )raw the lo'i( 'ate dia'ra. of the redu(ed e:1re&&ion u&in' *A*) 'ate only! b) Riven 3"A,B,C,))= "A+B+C+))!"A+B+C+))!"A+B+C+))!"A+B+C+))!"A+B+C+))!"A+B+C+))!"A+B+C+))!"A+B+C+ )) i) ,edu(e the above e:1re&&ion by u&in' A/ variable T/Da1, &howin' the variou& 'rou1& " i!e! o(tal&, 9uad& and 1air&)! ii) )raw the lo'i( 'ate dia'ra. of the redu(ed e:1re&&ion u&in' *+, 'ate only! [ 5 x 2 =10

Question 5. A 'overn.ent in&titution intend& to award a .edal to a 1er&on who 9ualifie& any one of the followin' (riteria2 Lhe 1er&on &hould have been an Indian (itiUen and had lo&t hi&;her life in a war but ha& not (o.1leted B7 year& of &ervi(e! +, Lhe 1er&on .u&t be an Indian (itiUen and ha& &erved the nation for a (ontinuou& 1eriod of B7 year& or .ore but ha& not lo&t hi&;her life in a war! +, Lhe 1er&on i& not an Indian (itiUen but ha& taMen a(tive 1art in a(tivitie& for the u1lift.ent of the nation! Lhe in1ut& are2 I* VLA B C ) +ut1ut X

Lhe 1er&on i&;wa& an Indian (itiUen Ja& a (ontinuou& &ervi(e of .ore than B7 year& Wo&t hi&;her life in a war LaMen 1art in a(tivitie& for u1lift.ent of the nation

)enote& eli'ible for .edal > 1 indi(ate& 4=- ad 0 indi(ate& *+ in all (a&e&?

a) )raw the truth table for the in1ut& and out1ut& 'iven above and write the +- e:1re&&ion for X"A,B,C,))!! b) ,edu(e X"A,B,C,)) u&in' Tarnau'h& .a1! )raw the lo'i( 'ate dia'ra. for the redu(ed +- e:1re&&ion for X"A,B,C,)) u&in' A*) and +, 'ate! 4ou .ay u&e 'ate& with two or .ore in1ut&! A&&u.e that the variable and their (o.1le.ent& are available a& in1ut&! [ 5 x 2 = 10

Question &. a) Fhat are Da:ter.&K Convert the followin' fun(tion a& a rodu(t of Da:ter.&2 3" ,$,,)= " +$)!" +,) b) -tate whether the followin' e:1re&&ion i& a Lautolo'y or Contradi(tion with the hel1 of a truth table2 "XX5)! >"X%4)!"4%5)? () Fhat i& a Dulti1le:erK )raw the truth table and lo'i( dia'ra. of a S21 .ulti1le:er! [ 2'!'5=10 Question (. a) )raw the (ir(uit dia'ra. for a C to S de(oder! b) )raw the truth table for a half adder! Al&o derive a +- e:1re&&ion for the half adder and draw it& lo'i( (ir(uit! () -i.1lify the followin' e:1re&&ion and al&o draw the (ir(uit for the redu(ed e:1re&&ion! > -how the &te1 wi&e worMin' alon' with the law& u&ed!? 3= X! "4+5!"X!4 +X!5)) [!'!'%=10

Se$tion ) An&wer any B 9ue&tion&! =a(h 1ro'ra. &hould be written in &u(h a way that it (learly de1i(t& the lo'i( of the 1roble.! Lhi& (an be a(hieved by u&in' .ne.oni( na.e& and (o..ent& in the 1ro'ra.! Question *. Lhe (o/ordinate& of a 1oint on a two/di.en&ional 1lane (an be re1re&ented by ":,y) with : a& the : (o/ordinate and y a& the y (o/ordinate! Lhe (o/ordinate& of .id1oint of two 1oint& 1":1,y1) and B":B,yB) (an be (al(ulated a& ":,y) where2 :=:1+:B;B, y=y1+yB;B )e&i'n a (la&& oint with the followin' detail&2 Cla&& na.e 2 oint )ata .e.ber& : 2 &tore& the : (o/ordinate y 2 &tore& the y (o/ordinate De.ber fun(tion&2 oint") 2 (on&tru(tor to initialiUe :=0 and y=0 void read oint") 2 a((e1t& the (o/ordinate& : and y of a 1oint oint .id1oint" oint A, oint B)2 (al(ulate& and return& the .id1oint of the two 1oint& A and B! void di&1lay1oint") 2 di&1lay& the (o/ordinate& of a 1oint -1e(ify the (la&& oint 'ivin' detail& of the (on&tru(tor" ), .e.ber fun(tion& void read oint"), oint .id1oint" oint, oint) and void di&1lay1oint") alon' with the .ain fun(tion to (reate an obEe(t and (all the fun(tion& a((ordin'ly to (al(ulate the .id1oint between any two 'iven 1oint&! [ 10 A

Question +. In1ut a word in u11er(a&e and (he(M for the 1o&ition of the fir&t o((urrin' vowel and 1erfor. the followin' o1eration! i) Ford& that be'in with a vowel are (on(atenated with P4O ! 3or e:a.1le, =V,+ = be(o.e& =V,+ =4! ii) Ford& that (ontain a vowel in between &hould have the fir&t 1art fro. the 1o&ition of the vowel till end, followed by the 1art of the &trin' fro. be'innin' till 1o&ition of the vowel and i& (on(atenated by PCO! 3or e:a.1le ,+Y=CL be(o.e& +Y=CL ,C! iii) Ford& whi(h do not (ontain a vowel are (on(atenated with P*O! 3or e:a.1le, -T4 be(o.e& -T4*! )e&i'n a (la&& ,earran'e u&in' the de&(ri1tion of the data .e.ber& and .e.ber fun(tion& 'iven below2 Cla&& na.e )ata .e.ber& L:t C:t len De.ber fun(tion& ,earran'e") void readword") void (onvert") void di&1lay") 2 2 2 2 2 2 2 2 ,earran'e to &tore a word to &tore the rearran'ed word to &tore the len'th of the word (on&tru(tor to initialiUe the in&tan(e variable& to a((e1t the word in1ut in V =,CA-= (onvert& the word into it& (han'ed for. and &tore& it in &trin' L:t di&1lay& the ori'inal and the (han'ed word

-1e(ify the (la&& ,earran'e 'ivin' the detail& of the (on&tru(tor"), void readword"), void (onvert") and void di&1lay")! )efine a .ain fun(tion to (reate an obEe(t and (all the fun(tion a((ordin'ly to enable the ta&M! [ 10 Question 10. )e&i'n a (la&& Chan'e to 1erfor. &trin' related o1eration&! Lhe detail& of the (la&& are 'iven below2 Cla&& na.e 2 Chan'e )ata .e.ber& &tr 2 &tore& the word new&tr 2 &tore& the (han'ed word len 2 &tore& the len'th of the word De.ber fun(tion& Chan'e") 2 default (on&tru(tor void in1utword") 2 to a((e1t a word (har (a&e(onvert"(har (h) 2 (onvert& the (a&e of the (hara(ter and return& it void re((han'e"int) 2 e:tra(t& (hara(ter& u&in' re(ur&ive te(hni9ue and (han'e& it& (a&e u&in' (a&e(onvert") and for.& a new word void di&1lay") 2 di&1lay& both the word&

a) -1e(ify the (la&& Chan'e, 'ivin' detail& of the (on&tru(tor"), .e.ber fun(tion& void in1utword"), (har (a&e(onvert"(har (h), void re((han'e"int) and void di&1lay")! )efine the .ain fun(tion to (reate an obEe(t and (all the fun(tion& a((ordin'ly to enable the above (han'e in the 'iven word! [* b) )ifferentiate between finite and infinite re(ur&ion! [2 Se$tion C Ans,e# "n- 2 .uestions! =a(h 1ro'ra.;al'orith. &hould be written in &u(h a way that it (learly de1i(t& the lo'i( of the 1roble. &te1 wi&e! Lhi& (an al&o be a(hieved by u&in' 1&eudo (ode&! "3low(hart& are not re9uired) T/e 0#o1#"2s 2ust 3e ,#itten in 4"5". T/e "61o#it/2 2ust 3e ,#itten in 1ene#"6 st"n7"#7 8o#2 ,/e#e5e# #e.ui#e7.

Question 11. A &u1er (la&& ForMer ha& been defined to &tore the detail& of a worMer! )efine a &ub (la&& Fa'e& to (o.1ute the .onthly wa'e& for the worMer! Lhe detail& of both the (la&&e& are 'iven below2 Cla&& na.e 2 ForMer )ata .e.ber& 2 *a.e 2 to &tore the na.e of the worMer Ba&i( 2 to &tore the ba&i( 1ay in de(i.al De.ber fun(tion& ForMer"Z!) 2 1ara.eteriUed (on&tru(tor to a&&i'n value& to the in&tan(e variable& void di&1lay") 2 di&1lay worMer detail& (la&& na.e )ata .e.ber& hr& rate wa'e De.ber fun(tion& Fa'e&"Z!) double overti.e" ) void di&1lay") 2 2 2 2 2 2 2 Fa'e& &tore& the hour& worMed &tore& rate 1er hour &tore& the overall wa'e of the worMer 1ara.eteriUed (on&tru(tor to a&&i'n value& to the in&tan(e variable& of both (la&&e& (al(ulate& and return& the overti.e a.ount a& "hour& < rate ) (al(ulate& the wa'e u&in' the for.ula wa'e=overti.e a.ount +ba&i( 1ay and di&1lay& it alon' with other detail&

-1e(ify the (la&& ForMer 'ivin' detail& of the (on&tru(tor") and void di&1lay")! V&in' the (on(e1t of inheritan(e, &1e(ify the (la&& Fa'e& 'ivin' detail& of the (on&tru(tor"), double overti.e") and void di&1lay")! Lhe .ain fun(tion need not be written! [ 10

Question 12. )efine a (la&& ,e1eat whi(h allow& the u&er to add ele.ent& fro. one end "rear) and re.ove ele.ent& fro. one end "rear) and re.ove ele.ent& fro. the other end "front) only! Lhe followin' detail& of the (la&& ,e1eat are 'iven below2 Cla&& na.e 2 ,e1eat )ata .e.ber& &t>? 2 an array to hold a .a:i.u. of 100 inte'er ele.ent& (a1 2 &tore& the (a1a(ity of the array f 2 to 1oint to the inde: of the front r 2 to 1oint to the inde: of the rear De.ber fun(tion& ,e1eat"int .) 2 (on&tru(tor to initialiUe the data .e.ber& (a1=., f=0, r=0 and to (reate the inte'er array void 1u&hvalue"int v) 2 to add inte'er& fro. the rear inde: if 1o&&ible el&e di&1lay the .e&&a'e PoverflowO int 1o1value") 2 to re.ove and return ele.ent fro. the front, if array i& e.1ty then return /[[[[ void di&1") 2 di&1lay& the ele.ent& 1re&ent in the li&t a) -1e(ify the (la&& ,e1eat 'ivin' detail& of the (on&tru(tor"int), .e.ber fun(tion void 1u&hvalue"int), int 1o1value") and void di&1")! Lhe .ain fun(tion need not be written! b) Fhat i& the (o..on na.e of the entity de&(ribed aboveK () +n what 1rin(i1le doe& thi& entity worMK

[* [1 [1

Question 1!. a) A linMed li&t i& for.ed fro. the obEe(t& of the (la&&, (la&& Wi&t*ode& H int ite.; Wi&t*ode& ne:t; I Frite a .ethod +, an al'orith. to (o.1ute and return the &u. of all inte'er& ite.& &tored in the linMed li&t! Lhe .ethod de(laration i& &1e(ified below2 int li&t&u."Wi&t*ode& &tart); b) Fhat i& Bi' \+ notationK -tate it& &i'nifi(an(e! () An&wer the followin' fro. the dia'ra. of a Binary tree 'iven below2

i) ii) iii) iv)

*a.e the 1arent node of =! Frite the 1o&torder tree traver&al! Frite the internal node& of the tree! -tate the level of the root of the tree!

[1 [1 [1 [1