ISC 2004

COMPUTER SCIENCE

PAPER-I

(THEORY)

(Three hours)

(Candidates are allowed additional 15 minutes for only reading the paper. They must not start writing during this time)

------------------------------------------------------------------

Answer all Question in Part I (compulsory) and seven questions from Part II, choosing three questions from Sections A and four questions from

Section B. All working, including rough work, should be done on the same sheet as the rest of the answer. The intended marks for questions or for parts of questions are given in brackets[].

------------------------------------------------------------------

PART I

while answering questions in this part indicate briefly your working reasoning wherever required.

Question 1.

(a) Using Boolean Algebra show that the dual of exclusive OR is equivalent to the complement of exclusive OR.

(b) Show that A + A.B =A+B using the truth table.

(c) Define maxterm and minterm of a Boolean expression. What is the relation between them (show it by example).

(d) What types of mulitivibrators are used for clock generators in digital computer system? why are clocks needed in a digital computer system?

(e) Reduce the following to its simplest form using laws of Boolean Algebra. At each step state clearly the law used for simplifications.

C.D + A + A + C.D + A.B

Question 2.

(a) Show how a NAND gate can be used to simulate the function of NOT, AND & OR gates.

(b) State the principle of duality. Give an example.

(c) Convert the following infix expression to its postfix form.

(P-Q)/(R*(S-T)+U)

(d) What do you understand by status flags? Name any two status flags.

(e) An array A is stored in the memory with each element requiring 4 bytes of storage. If the base address of A is 3000. determine the location of A when the array is stored row major wise.

Question 3.

(a) The function trial () is member function/method of some class.

void trial()

{

int  item[] = {0,1,4,9,16};

for (int j = 0, k = 0 ; j < 4 ;  j++ , k++)

{

if (item [k] < item[k+1])

{

int a = item[k] ;

item [k] = item[k+1];

item[k+1] = a;

}

}

}

(i) State the final value of j, k at the end of the function.

(ii) What are the values stored in the array item[] after this function is executed?

(iii) In one line say what is being done by the function trial() state the technique used.

 (i)   value of j is 4 and k is 4 (ii)  the value stored in array item[] is     1 4 9 16 0 (iii) the descending order sorting is done by the function trial(), the technique used is bubble sort.

(b) The following function is a past of a some class. it computes x raised to the power n. Here x is the base and n is the power. There are five places in the code marked by ?1? , ?2? , ?3?, ?4? ?5?  that must be replaced by expressions so that the program works correctly.

double integralpower (double x, int n)

{

int inverse = 0;

double result = 1.0;

if (n == 0)

return ?1?;

else if (n < 0)

{

inverse = 1;

n = ?2?

}

for (int i = 1; ?3?; i++)

{

double temp = ?4? ;

result = ?5? ;

}

return  result ;

}

(i) What is the expression or statement at ?1?

(ii) What is the expression or statement at ?2?

(iii) What is the expression or statement at ?3?

(iv) What is the expression or statement at ?4?

(v) What is the expression or statement at ?5?

 (i) 1    (ii) -n    (iii) i<=n    (iv) (inverse==0)?x:1/x;  (v) result*temp;

PART II

Answer seven questions in this part choosing three questions A and four

question from Section B.

SECTION A

Answer any three question from this Section.

Question 4.

(a) Given the Boolean function F (A,B,C,D)= E(0,1,2,6,8,9 10) using Karnaugh's map to reduce this function F. using the  given SOP form. Draw logic gate diagram for the reduce SOP form. You may use gates with more than two inputs. Assume that variable and their complements are available as inputs.

 AB\CD C'D' C'D CD CD' A'B' 1 0 1 1 3 1 2 A'B 4 5 7 1 6 AB 12 13 15 14 AB' 1 8 1 9 11 1 10

Pair 1 is m2+m6

Reduce Expression for Quad 1 is B'C'

Reduce Expression for Quad 2 is B'D'

Reduce Expression for Pair 1 is A'CD'

Final SOP expression is B'C'+B'D'+A'CD'

(b) Now given G (A,B,C,D)=II(3,4,5,11,12,13,14,15) use Karnaugh's map to reduce this function D using the given POS form. Draw logic gate diagram for the reduced POS form. You may use gates with more than two inputs. Assume that variables and their complements are available as inputs.

 AB\CD C+D C+D' C'+D' C'+D A+B 0 1 0 3 0 2 A+B' 0 4 5 0 7 6 A'+B' 0 12 13 15 14 A'+B 8 0 9 0 11 0 10

Pair 1 is m3+m7

Pair 2 is m4+m12

Pair 3 is m9+m11

Reduce Expression for Quad is B+C'

Reduce Expression for Pair 1 is A+C'+D'

Reduce Expression for Pair 2 is B'+C+D

Reduce Expression for Pair 3 is A'+B+D'

Final SOP expression is (B+C').(A+C'+D').(B'+C+D).(A'+B+D')

Question 5.

A given the Boolean function: F(A,B,C,D,) = E(1,3,7,9,11,15)

(a) Use Karnaugh's map to reduce the function.

Draw the logic diagram for the reduced SOP expression using the Basic NOT, AND, OR gates. You may use gates with more than two inputs. Assume that variables and their complements are available as inputs.

 AB\CD C+D C+D' C'+D' C'+D A+B 0 1 0 3 0 2 A+B' 0 4 5 0 7 6 A'+B' 0 12 13 15 14 A'+B 8 0 9 0 11 0 10

Pair 1 is m3+m7

Pair 2 is m4+m12

Pair 3 is m9+m11

Reduce Expression for Quad is B+C'

Reduce Expression for Pair 1 is A+C'+D'

Reduce Expression for Pair 2 is B'+C+D

Reduce Expression for Pair 3 is A'+B+D'

Final SOP expression is (B+C').(A+C'+D').(B'+C+D).(A'+B+D')

(b) Now implements the circuits in (a) using the NAND gates only. Show relevant reasoning at each step. You may use with more than two inputs.

Question 6.

A full adder is a combinational circuit adds 3 bits taking into account that I may have been carried by a lower significant stage. Following is the truth table for the full adder. It has 3 inputs: X, Y and Z. it has two outputs C  and S.

INPUTS                             OUTPUTS.

Addend(X)    Augend(Y)    Previous carry(Z)    Carry(c)        Sum(s)

0             0            0                    0              0

0             0            1                    0              1

0             1            0                    0              1

0             1            1                    1              0

1             0            0                    0              1

1             0            1                    1              0

1             1            0                    1              0

1             1            1                    1              1

(a) Write the SOP expressions for sum (s) and carry (c)

(b) Reduce the SOP expressions for sum and carry using Karnought's map. if possible.

(c) Draw the logic gate circuit for the reduced expressions for sum and carry if it can be reduced. otherwise draw the logic gate circuit for the original expressions using AND, OR gates. you may use gates with more than two inputs. Assume that variables and their complements are available as inputs.

Question 7.

(a) What do you understand by a Multiplexer? State any one application of a multiplexer circuit.

(b) Draw the logic diagram and function table for 4x1 Multiplexer and explain its working.

(c) Differentiate between mono-stable and bi-stable mulitivibrators. Where are they used?

Questions 8.

(a) What is meant by instruction cycle of CPU ? Name its two components.

(b) Explain what happens during the instruction cycle. State clearly the function of the registers: PC, IR in this process.

(c) How are decoders different from encoders? Where are they used?

SECTION B

Answer only four questions. Each program should be written in such a way that it clearly depicts the logic of the problem. This can be achieved by using mnemonic names and comments in the program. (Flow charts and Algorithms are not  required).

(The program must by written in C++ OR Java)

Question 9.

A class called Number has been defined to find the frequency of each present in it and the sum of the digits and to display the results. Some of the members of the class Number are given below:

 Class name Number. Data member num - long integer type. Members functions/methods: Number() constructor to assign 0 to num. Number(long n) constructor to assign n to num. void digitFrequency() to find the frequency of each digits and to display it. int sumDigits() to return the sum of the digits of the number.

Specify the class Number giving the details of the two constructors and functions void digitFrequency() and int sumDigits(). You do not need to write the main function.

 #include #include class number {   public:     long int num;     number ()     {       num=0;     }     number(long n)     {       num=n;     }     void digitFrequency();     int sumDigits(); }; void number::digitFrequency() {   int r,i;   static int a;   long int n=num;   while(n>0)   {     r=n%10;     a[r]=a[r]+1;     n=n/10;   }   for(i=0;i<10;i++)     if(a[i]!=0)       cout<<"Number of times "<0)   {     r=n%10;     sum+=r;     n=n/10;   }   return(sum); }

Question 10.

A class D2Point defines the coordinates of a point in a plane while another class D3Point defines the coordinates of a point in space. The details of both the classes are given below:

 Class name D2Point Data members double x, y To store the x and y coordinates. Functions/methods: D2Point() constructor to assign 0 to x,y D2Point(double nx, double ny) constructor to assign nx to x and ny to y. double distance2d(D2Point b) to return the distance between the point b and the current point in a plane. Class name D3Point. Data members double z. To store the z coordinate. Functions/methods: D3Point() constructor to assign 0 to z. D3Point(double nz) constructor to assign nz to z. double distance3d(D3point b) to return the distance between the point b and the current point in space.

if x1,y1,z1 x2 y2 z2 be the coordinates of the two points then the distance between the points in a plane is given by the formula:

'/(x2-x1)2 + (y2-y1)2

and the distance between the points in space is given by the formula.

'/(x2-x1)2 + (y2-y1)2 + (z2-z1)2

Specify the class D2point giving the details of the two constructors and function double distance2d(D2Point b). Using the concept of inheritance specify the class D3Point giving the details of the two constructors and function double distance3d(D3Point b). You do not need to write the main function.

 #include #include #include class d2point {   public:     double x,y;     d2point()     {       x=0.0;       y=0.0;     }     d2point(double nx,double ny)     {       x=nx;       y=ny;     }     double dist2d(d2point b)     {       double tot,k;       k=pow((x-b.x),2.0)+pow((y-b.y),2.0);       tot=pow(k,0.5);       return(tot);     } }; class d3point:public d2point {   public:     double z;     d3point()     {       z=0.0;     }     d3point(double nz)     {       double nx,ny;       cin>>nx>>ny;       d2point::d2point(nx,ny);       z=nz;     }     double dist3d(d3point b)     {       double tot1,k1;       k1=pow((x-b.x),2.0)+pow((y-b.y),2.0)+pow((z-b.z),2.0);       tot1=pow(k1,0.5);       return(tot1);     } };

Questions 11.

Class ChaArray contains an array of n characters (n<=100). You may assume that the array contains only the letters of the English alphabet. Some of the members functions/methods of ChaArray are given below.

 Class name: ChaArray. Data members/instance variables: Char ch[] an array of characters int  size the size of array of characters. Members functions/methods: ChaArray() constructor to assign to initialize instance variables to null. ChaArray(char c[]) constructor to assign characters array c to the instance variable. void displayArray () to display the list of n characters. void move( ) to move all the upper case letter to the right side of the array and the lower case letters to the left side of array without using any standard sorting technique e.g. input : t D f s X v d      output: t d f s v X D

Specify the class ChaArray giving the details of the two constructors and the functions void displayArray() and void move() only. You do not need to write the main function.

 #include #include #include #include #include class chaArray {   char ch;   int size;   public:     chaArray()     {       strcpy(ch,"");       size=strlen(ch);     }     chaArray(char c)     {       strcpy(ch,c);       size=strlen(ch);     }     void displayarray();     void move(); }; void chaArray::displayarray() {   for(int i=0;ch[i]!=NULL;i++)     cout<

Questions 12.

Class Employee contains the following members.

 Class name Employee Data members/instance variables: empname to store the name of employee int empcode to store the employee code. double basicpay to store the basic pay of the employee. Members functions/methods: Employee() constructor to initialize all data members/instance variables to null or 0. Employee(....) constructor to assign name, employee code and basic salary to data member/instance variable. double salaryCal() to compute and return the total salary of the employee.

The salary is calculated according to the following rules:

Salary = Basic Pay + HRA + DA

HRA = 30% of Basic Pay

DA = 40% of Basic Pay

If the employee code for the employee is <=15 then a special allowance will be added if the salary is <=15000. The special allowance will be 20% of the salary (Basic + DA + HRA) and the minimum amount for special allowance will be Rs. 2500.

If the employee code is >15 then the special allowance will be Rs. 1000. hence the total salary for the employee will be calculated as Total Salary = Salary + Special Allowance.

Specify the employee class giving the details of the two constructors and the function double salarycal() only. you do not need to worry write the main function.

 #include #include #include #include class employee {   private:     char empname;     int empcode;     double basicpay;   public:     employee()     {       strcpy(empname,"");       empcode=0;       basicpay=0.0;     }     employee(int code,char nam,double pay)     {       strcpy(empname,nam);       empcode=code;       basicpay=pay;     }     double salarycal(); }; double employee::salarycal() {   double hra=0.3 * basicpay;   double da=0.4 * basicpay;   double salary=basicpay+hra+da;   if(empcode<=15)   {if(salary<=15000)      {if((0.2 * basicpay)<2500)         salary+=2500;       else         salary+=0.2 * basicpay;   }}   else     salary+=1000;   return(salary); }

Question 13.

Strange is an entity which can hold at the most 20 integers. The strange restriction is that an integer can only be added from the top or removed from the top. This is like a pile of China plates where we added a plate to the pile from the top and remove a plate from the top only. Define the class Strange with the following details.

 Class Name Strange Data Member/Instance variable int ele[] The array to hold the integers element. int capacity The maximum capacity of the integer array. int top To point to the index  of the topmost element. Member Functions/Methods Strange(int cap) constructor to initialize the data capacity=cap, top=-1 and create the integer array. void pushItem(int value) adds the integer value to the top of Strange if possible, otherwise output a message "Strange is full, Cannot push Item". int popItem() removes the integer from the top of Strange and return it if Strange is not empty, otherwise output a message "Strange is empty. Returning -9999" and returns -9999.

(a) Specify the class Strange giving the details of the constructor and the functions void pustItem(int value) and int popItem() only. You do not need to write the main function. 

(b) What is the common name of the entity describe above? 

(c) State one of its application. 

 #include #include #include #include #define MAX 100 class strange {   private:     int ele[MAX],capacity,top;   public:     strange(int cap)     {       capacity=cap;       top=-1;     }     void pushitem(int);     void popitem();     void display(); }; void strange::pushitem(int value) {   if(top==capacity-1)   {     cout<<"overflow";     exit(1);   }   else   {     top++;     ele[top]=value;   } } void strange::popitem() {   if(top==-1)   {     cout<<"underflow";     exit(1);   }   else   {     cout<<"Element Pop : "<

Question 14.

There is class Ascending that contains integers that are already arranged in ascending order. Some of the member functions/methods of Ascending are given below.

 Class Name Ascending Data members/instance variables int al[] an array of integers sorted in ascending order. int size number of integers in the array. Member functions/methods Ascending(int n) constructor to create an Ascending list of size n. void diaplayList() to display the list of integer Ascending merge(Ascending al) to merge the Ascending list al with the current ascending list object and return a third ascending list which is also in ascending order.

Important: While generating the final Ascending list both the original Ascending lists must be scanned only once. Element common to the two lists should appear only once in the third Ascending list.

Specify the class Ascending giving details of the function void displayList() and Ascending merge(Ascending al) only. You may assume that the other functions are written for you. You do not need to write main function.

 #include #include #define MAX 100 class ascending {   private:     int al[MAX],size;   public:     ascending(int n)     {       size=n;     }     void readlist();     void displaylist();     ascending merge(ascending); }; void ascending::displaylist() {   for(int i=0;i

=*=*=*=*=*=