ISC 2003

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
The trigonometric function sec(x) can be computed as sec(x)=1/cos(x) where x is in radians and(0<=x<=PI/2). The trigonometric function cos(x) can be computed by the following infinite series:
cos(x) = 1 - x2/2 + x4/4 - x6/6………… x is in radians and (0<=x<=PI/2)
A class called MyMath has been defined to calculate the trigonometric functions. Some of the functions/methods in MyMath are shown below:

 Class name MyMath x angle in radians Members functions/methods: MyMath(double nx) constructor to assign x = nx. double abs(double y) calculates and returns absolute value of y. Y=y when y>=0, Y=-y when y<0 double cos() calculates and returns the value of cos() correct to 7 places after the decimal using the infinite series given above when x is within the range otherwise it returns an error value of 9999999.9. double cos() calculates and returns the value of sec() by using the value of cos(). (remember when x is in radians and 0<=x<=PI/2 then 1>=cos()>=0)

Specify the class MyMath giving the details of the constructor MyMath(double nx), double abs(double y), double cos(), double sec() only. You do not need to write the main function.

 #include #include #include class MyMath {   public:     double x;   MyMath(double nx)   {     x=nx;   }   double abs(double y);   double cos();   double sec(); }; double MyMath::abs(double y) {   if(y>=0)     return(y);   else     return(y); } double MyMath::cos() {   double cos=1;   double f=1,k;   for(int i=1;i<50;i++)   {     for(f=1,k=1;k<=i*2;k++)       f*=k;     cos+=pow(-1,i)*pow(x,i*2)/f;   }   return(cos); } double MyMath::sec() {   return(1/cos()); }

Question 10
A class called Date has been defined to handle Date related functions, i.e. finding the future date n days after the current date.
e.g., Date 32 days after 01-01 will be 02-02.
Finding the number of days between the current date and date on which a project ends. Example : if a project started on 01-01 and finished on 02-02, the number of days would be 32. You may assume that all the dates are in the year 2003 only and are valid dates. To make these calculations easy each date can be converted to its equivalent date number. Date number is the number of days between 1st January (01-01)
and the given date (dd-mm).
Example :
Date(dd-mm) dateNumber
01-01         1
20-01         20
02-02         33
03-03         62
----          ---
31-12         365
some of the functions/methods in Date are shown below :

 Class name Date Data Member dd-day mm-month Members functions/methods: date (int nd,int nm) constructor to initialize dd = nd, mm=nm int dateTodateNumber() returns the date Number equivalent to the current Date object. Date dateNumberToDate (int dn) returns the Date equivalent to the given dateNumber dn Date futureDate(int n) returns the Date that occurs n days after the current Date object. You may assume that the future date will be in the year 2003 only.

Specify the class Date giving the details of the constructor Date(int nd, int nm), int dateTodateNumber(), Date dateNumberToDate(int dn), Date futureDate(int n). You may assume that the other functions/methods are written for you. You do not need to write the main function.

 #include #include class date {   public:     int dd,mm;     date(int nd, int nm)     {       dd=nd;       mm=nm;     }     int datetodatenumber();     date datenumbertodate(int dn);     date futuredate(int n); }; int date::datetodatenumber() {   int d=1,m=1,dn=0;   int mon[]={0,31,28,31,30,31,30,31,31,30,31,30,31};   while(d!=dd || m!=mm)   {     d++; dn++;     if(d>mon[m])     {       d=1;       m++;     }   }   return(dn); } date date::datenumbertodate(int dn) {   date t(0,0);   int m[]={0,31,28,31,30,31,30,31,31,30,31,30,31};   t.dd=1, t.mm=1;   while(dn>0)   {     t.dd++; dn--;     if(t.dd>m[t.mm])     {       t.dd=1;       t.mm++;     }   }   return(t); } date date::futuredate(int n) {   date t(0,0);   int x=datetodatenumber()+n;   t=datenumbertodate(x);   return(t); }

Question 11
Class MyArray contains any array of n integer (n <= 100) that are already arranged in ascending order. The subscripts of the array elements vary from 0 to n-1. Some of the member functions of MyArray are given below:

 Class name MyArray arr n - an array of a integers.  - size of the array. Members functions/methods: MyArray() constructor to initialize n = nm and the void readArray() array arr reads n integers that are arranged in ascending order. void displayArray() displays n number of integers from array arr. int binarySearch(int value) searches for the value in the array using the binary search technique. It returns the subscript of the array element if the value is found, otherwise it returns -999.

(a) Specify the class MyArray giving the details of the void displayArray() and int binarySearch(int value) only. You may assume that the other functions/methods are written for you. You do not need to write the main function.                                                             
(b) What change would be necessary in the method/function int binarySearch
(int value)
only if the given array was arranged in descending order? 
(c) When will binary search technique fail to work?                   

 #include #include #define MAX 100 class MyArray {   private:     int arr[MAX];     int n;   public:     MyArray(int nm)     {       n=nm;     }     void readArray();     void displayArray();     int binarySearch(int value); }; void MyArray::displayArray() {   cout<<"Displaying the Array"<=l && f==0)   {     mid=(l+h)/2;     if(arr[mid]>value)       h=mid-1;     else if(arr[mid]

Question 12
You are given a piece of text that contains words, blank spaces and tabs only. A Word is defined as a group of contiguous non blank characters.
A White Space is a tab ('\t') or a blank space (' ').
e.g.,
Text                 No of Words         No of White Spaces
"         "                 0                         10
"This is beautiful"         3                         15
" blessed"                  1                         0
A class Text is designed to handle text related operations. Some functions of class Text are as follows :

 Class name Text txt - to store the given string. You may assume that it has 200 characters at most. Members functions/methods: Text() constructor void readText() reads the given string from the input. char charA(int i) returns the character at position i of the string. int length() returns the length of the string. int noOfWhite Spaces() returns the total number of white spaces in the text. int noOfWords() returns the number of words in the text.

Specify the class Text giving the details of int noOfWhiteSpaces() and int noOfWords() only. You may assume that the other functions/methods are written for you. You do not need to write the main function.

 #include #include #include #include #define MAX 200 class text {   private:     char txt[MAX];   public:   text ()   {     strcat(txt,"");   }   void readtext();   char charat(int i);   int length();   int noofwhitespaces();   int noofwords(); }t; int text::noofwhitespaces() {   for(int i=0,w=0;txt[i]!='\0';i++)   {     if(txt[i]==' ')       w++;   }   return(w); } int text::noofwords() {   return(t.noofwhitespaces()+1); }

Question 13
A set is a collection in which there is no duplication of elements. S=(1,6,9,24) is a set of 4 integer elements. An array of integers may be used to represent a set. You may assume that there will be a maximum of 50 elements in the set. Following are some member functions of the class set.

 Class name Set Data members/instance variables: arr - an array of integers to store the elements of the set. n - an integer to store the total number of elements in the set. Members functions/methods: Set(int nn) constructer to initialize n=nn and the array arr void readElements() reads the elements of the set. void displayElements() displays the elements of the set. int getSize( ) returns n, the number of elements in the set int has(int ele) returns 1 if ele belongs to the current set object and 0 otherwise. Set intersection(Set d) returns the intersection of set object d and the current set object i.e., the set containing the elements that are present in both the sets Set unions(Set d) returns the union of set object d and the current set object i.e., the set containing the elements that are present in both the sets

Specify the class Set giving the details of the functions int has(int ele), Set intersection(Set d), Set union(Set d). You may assume that the other functions/methods are written for you. You do not need
to write the main function.

 #include #include #define MAX 100 class sets {   private:     int arr[MAX],n;   public:     sets(int nn)     {       n=nn;       arr[nn]=0;     }     void readElements();     void displayElements();     int getsize()     {       cout<<"Enter size of SET : "; cin>>n;       return(n);     }     int has(int ele);     sets intersection(sets d);     sets unionofsets(sets d); }; sets sets::intersection(sets d) {   sets comm(50);   comm.n=0;   for(int i=0;i

Question 14
A financial Institution has only two kinds of Accounts, Simple and Compound.

The class Account has two protected attributes Account Number (a positive integer) and Principle (a double precision real number to store the money deposited initially).

The interest for a Simple Account is calculated by using the Simple Interest formula: SI=PRT/100, where SI=Simple Interest, P=Principle, R=Rate of Interest per annum, T=Time in year.

The interest for a Compound Account is calculated by using the Compound Interest formula. CI=P[1+R/100]T - P, where CI=Compound Interest, P=Principle, R=Rate of Interest per annum, T=Time in year.

Rate and Time for two types of account may vary. Model the above situation by defining classes Account, Simple and Compound, where Simple and Compound are derived classes from class Account.

Write appropriate constructors for passing various attributes for the three classes. Write the function double interest() that calculates the appropriate interest and return the interest for the classes Simple and Compound. Also write the function display() for the three classes which print out all the attributes values as.

Account Number:

Principle:

Rate:

Time:

Interest:

with each attribute on a single line. Make sure that each display() function is correctly placed in the appropriate class. You do not need to write the main function.

 #include #include #include class account {   protected:     int account_number;     double principal;   public:   account()   {     principal=0.0;   }   void getdata()   {     cout<<"\n Enter principal amount=";     cin>>principal;     cout<<"\n Enter account number:";     cin>>account_number;   }   void display()   {     cout<<"\n The Account number="<

=*=*=*=*=*=