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[5][4] is stored in the memory with each element requiring 4 bytes of storage. If the base address of A[0][0] is 3000. determine the location of A[3][2] 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 [00]C'D' [01]C'D [11]CD [10]CD' [00]A'B' 1 0 1 1 3 1 2 [01]A'B 4 5 7 1 6 [11]AB 12 13 15 14 [10]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 [00]C+D [01]C+D' [11]C'+D' [10]C'+D [00]A+B 0 1 0 3 0 2 [01]A+B' 0 4 5 0 7 6 [11]A'+B' 0 12 13 15 14 [10]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 [00]C+D [01]C+D' [11]C'+D' [10]C'+D [00]A+B 0 1 0 3 0 2 [01]A+B' 0 4 5 0 7 6 [11]A'+B' 0 12 13 15 14 [10]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.

Sin(x) can be computed by the following infinite series:

x - x3 + x5 - x7 + .....    x is in radians and (0 <= x <= PI/2)

3!   5!   7!

A class called Trig has been defined to calculate the trigonometric functions. Some of the functions/ methods in Trig are shown below:
 Class name: Trig Data members x Members functions/methods: Trig() constructor double abs(double x) calculates and returns the absolute value of x, x=x when x>0 x=-x when x<0 double sin(double x) calculated and returns the value of sin (x) correct to 5 places after the decimal using the infinite series above.

(a) specify the class Trig giving the details of the constructor, double abs(double x), double sin(double x) only. You do not need to write the main function. [8]

(b) What care do you need to take while designing double sin(double x)? [2]

 #include #include #include class trig {   public:     double x;     trig()     {       x=0;     }     double abs(double x);     double sin(double x); }; double trig::abs(double x) {   if(x>=0)     return(x);   else     return(-x); } double trig::sin(double x) {   double sine=0;   double f=1.0,j=1.0,n,k;   cout<<"enter n:"; cin>>n;   for(int i=0;i

Question 10.

We want to design a calculator that calculates with integers. Some of the functions/methods of the class calculator are shown below:

 Class Name calculator Data members/ instance variables result Members functions/methods calculator() constructor enterfirst(int x) to enter the first number (first operand) showresult() to display the result. add(int X) to add the arguments to the result. sub(int x) to subtract the argument from the result. multiply(int x) to multiply the argument from the result. divide(int x) to divide the result by the argument. clear() to allow the result to be cleared to 0.

(a) Specify the class calculator giving the details of the constructor and enterfirst(int x), add(int x), sub(int x), multiply(int x), divide(int x), clear(). Mention the return type of each member function/method. You do not need to write the main function. [8]

(b) What special care would you take while designing this class. [2]

 #include #include class calculator {   private:     float result;   public:     calculator()     {       result=0.0;     }     void enterfirst(int x)     {       result=x;     }     void showresult()     {       cout<<"The Result is : "<

Question 11.

Class sorter contains an array of 100 integers. Some of the member functions/ methods of Sorter are given below:

 Class name Sorter Data members/instance an array Variables of 100 integers. Members function/methods: Sorter() constructor void readlist() to input 100 integers. void displaylist() to display the list if Sorted integers. int indexofmin(int startindex) return the index Subscript of the smallest integer in the array, between the startindex and the last index. void selectionsort() sorts the array in Ascending order using The selection sort Algorithm.

Specify the class sorter giving the details of the constructor and the functions void displaylist(), int indexofmin(int starindex), void selectionsort(). You may assume the function are written for you. You do not need to write the main function.

 #include #include #define MAX 100 class sorter {   private:     int a[MAX];   public:     sorter()     {       for(int i=0;i<10;i++)         a[i]=0;     }     void readlist();     void displaylist();     int indexofmin(int startindex);     void selectionsort(); }; void sorter::displaylist() {   for(int i=0;i<10;i++)     cout<a[i])     {       temp=a[i];       pos=i;     }   }   return(pos); } void sorter::selectionsort() {   int temp,pos,i;   for(i=0;i<10;i++)   {     pos=indexofmin(i);     temp=a[i];     a[i]=a[pos];     a[pos]=temp;   } }

Question 12

Your computer science teacher is trying to analyze the performance of the class in the previous exam. She has a class called performance. Which contains the marks of 600 students in the class. These are not sorted. She wants to find two quantities.
Mode - The most frequently occurring mark in the class. If two or more marks occur equally frequently then the highest of these marks is the mode.
Mode frequently - Frequency at mode.
You can make the following assumptions:
(i) The class has 600 students.
(ii) The maximum marks anyone can get are 100 and the minimum is 0.
(iii) All student marks are whole numbers.
(iv) You are not allowed to sort the marks.
Some of the member functions/methods of the Performance are given below.

 Class name Performance Data members/instance mark[] an integers Variables array to store the Marks of 600 students. Mode to store the Mode freqatmode to The frequency at mode. Member functions/methods: Performance() costructor Void readmarks() for reading the marks into the array. int getmode() for returning the mode. Void calcmodeandFrequency() a single function that calculates both mode and frequency at mode.

(a) specify the class performance giving the details of the constructor, int getmode(), int get freqatmode(), void calcmodeandfrequency() only. You may assume that the other functions are written for you. You do not write the main function.
(b) What care do you need to take while designing void calcmodeandfrequency()?

 #include #include #define MAX 10 class performance {   private:     int mark[MAX],mode,freqatmode;   public:     performance();     void readmark();     int getmode()     {       return(mode);     }     int getfreqatmode()     {       return(freqatmode);     }     void calcmodeandfrequency(); }; performance::performance() {   for(int i=0;ifreqatmode && mode<=mark[i])     {       freqatmode=f;       mode=mark[i];     }   } }

Question 13.

A manager of a Internet Service provider company wants to analyze the system usage from the log records to find the utilization of the system. He wants to know: For how long did the each user the system?

When the user want to use the system he must login to the system (starttime e.g. 12:30) and after finishing the works he must log out off the system (endtime e.g. 18:10). The time format is the 24 hour system hours and minutes.

You may also assume that the data is valid and a user will login for less then 24 hours. you my assume that the user will login only once in 24 hours. If the endtime (e.g. 2:30) is less then the starttime (e.g. 19:20) it means that the user logged in over the night.

A class called Time has been defined to calculate the time related functions. some of the function/methods in the Time are shown below.

 Class name Time Data members/instance hh Hours mm Minutes Member functions/methods: Time() constructor void readtime() to read time as 24 hours mode as hh mm void disptimeansi() to display time in 24 hour mode as hh mm int timetominutes(time) to find total number of minutes in hh mm void minutestotime(int) to convert total number of minutes into hh mm void diff(time endtime, time starttime) to difference between endtime and starttime in hour minutes.

(a) specify the class Time giving the details of the constructor, int timetominutes(Time), void minutestotime(int), void diff(Time endtime, Time starttime) only. You may assume that the other functions are written for you. You do not write the main function.
(b) What care do you need to take while designing void diff(Time endtime, Time starttime)?

 #include #include class times {   private:     int hh,mm;   public:     times(){ hh=0; mm=0; }     int times::timetominutes(times t)     {       int total;       total=(t.hh*60)+t.mm;       return(total);     }     void times::minutestotime(int total)     {       hh=(total/60);       mm=total-(hh*60);     }     void times::diff(times starttime, times endtime)     {       int diff;       diff = timetominutes(endtime) - timetominutes(starttime);       diff=(diff<0)?diff+24*60:diff;       minutestotime(diff);     } };

Question 14

You are given a string with English sentences as data. you have to read it and output it formatting it to that each sentence is on a new line with no leading blanks. A sentence is recognize by the following pattern: full stop, followed by a space, followed by a Capital alphabets. Note that just a full stop by itself does not indicate a sentence since the full stop may be the part of a decimal number.

A class Format has been defined for this purpose with the following methods/functions:

 Class name Format Data members/instance str to store the given string. len length of the given string. Member functions/methods: Format() constructor void readstring() reads the given string from the input. void charat(int index) returns the character at position index of the string. void writechar(char c) writes a single character to the output. void writenewline() writes the new line character to the output. int isuppper(char c) return 1 if c is upper case character and 0 otherwise. int isendofsentance(str,int i) returns 1 if the end of a sentence has been reached at the character position i in the string str and 0 otherwise. void formatstr() using the method isendofsentence() formats and output the given string in such a way that each sentence is on a new line with no leading blanks.

(a) specify the class Format giving the details of the isendofsentance(str,int i), void formatstr() only. You may assume that the other functions are written for you. You do not write the main function.
(b) What care do you need to take while designing isendofsentance(str,int i)?

(c) What care do you to take while designing void formatstr()?

 #include #include #include #include #define MAX 500 class format {   public:     char str[MAX];     int len;     int format::isendofsentence(char str[], int i)     {       if(charat(i)=='.' && charat(i+1)==' ' && isupperc(str[i+2])==1)         return(1);       else         return(0);     }     void format::formatstr()     {       for(int j=0;str[j]!='\0';j++)       {         writechar(charat(j));         if(isendofsentence(str,j)==1)         {           writenewline();           j++;         }       }    } };

=*=*=*=*=*=