ISC 2005

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

Answer all questions.

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

Question 1. [10]

(a) State the distributive Law? Verify it using the truth table?

Ans: Distributive Law:

(i) p+qr=(p+q)(p+r)

(ii) p.(q+r)=p.q+p.r

Truth Table

p	q	r	qr	p+qr	p+q	p+r	(p+q)(p+r)
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

(b) What is the canonical form of Boolean Expression? State the two types of canonical form.

Ans: A canonical form of a Boolean Expression is the logical sum of some minterms or logical product of some maxterms. The two types of canonical forms are: (i) Sum of product (SOP) form. (ii) Product of Sum (POS) form.

(d) What is the application of Boolean Algebra in Computer Science.

Ans: Boolean Algebra plays a vital role in Today's technological advancement, in logic of circuits for designing and simplifying circuits. In Boolean Algebra the variables can take up only two values '0' and '1' and hence it is compatible with Binary Arithmetic used in simplifying the designing of computer hardware.

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

AB' + A'BC' + (AC)' + BC

Ans: A' + A'BC' + (AC)' + BC

AB' + A'BC' + A' + C' + BC [ (AC)' = A' + C' ]

AB' + A'(1+BC') + C' + BC

AB'+A'+C'+BC [ 1 + X = 1]

(A+A')(A'+B')+(C'+B)(C'+C)

A'+B'+C'+B

A'+1+C' [B+B'=1]

Question 2. [10]

(a) What is Data Structure? What are the different types of Data Structure?

Ans: Data structure is representation of the logical relationship existing between individuals elements of data. In other words, A data structure is a way of organizing all data items that consider not only the elements but also their relationship to each other. Different types of data structures are: Arrays, Stack, Queue, LinK List, Tree etc.

(b) With a suitable example state the difference between runtime and syntax error.

Ans: A syntax error occurs when the grammatical rule is violated of a programming language. e.g. not using semicolon(;) at the end of line.
A run time error occurs during the execution of the programs. e.g. overflow of stacks, infinite loops.

Ans: Applications of Stack:
(1) Reversing a String.
(2) Conversion of infix expression to postfix expression.
(3) Stack frames.
(4) Implementing recursion.
(5) As a temporary memory area.

(d) Convert the following into postfix: (A+B/C)+B-C*D+C

Ans: ABC/+BC*-+C+

(e) An array ARR[10][5] is stored in memory with each element required 2 bytes of storage. If the element ARR[0][0] is stored at the location 1250, Calculate the location of ARR[5][6] when the array is stored row major wise.

Ans: a[i][j]=B+W(n(i-L1)+(j-L2)
Given B=1250, W=2 bytes, i=5, j=3, L1=0, L2=0, U1=9, U2=4, n=5
arr[5][3]=1250+2(5(5-0)+(3-0)
=1250+2(25+3)
=1250+56
=1306

Question 3.

(a) What will be the values stored in array ar[] after the following program is executed. [5]

void main()

{

int i,j=1;

int dividend=2;

int N=30;

int ar[]={2,0,0,0,0,0,0,0,0,0};

while(dividend<=N)

{

for(int i=2;i<dividend;i++)

{

if(dividend%i==0)

{

break;

}

if(i==dividend-1)

{

ar[j++]=dividend;

}

dividend++;

}

Ans: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

(b) The following function is a function of some class. It computes the quotient and remainder of a division.

void quotientrem()

{

int dividend = 13, divisor = 2, quo = ?1?;

int rem;

while(dividend>=?2?)

{

dividend -= ?3?;

rem = ?4?;

quo = ?5?;

}

rem = dividend + divisor;

}

(i) What is the expression/value at ?1? [1]

(ii) What is the expression/value at ?2? [1]

(iii) What is the expression/value at ?3? [1]

(iv) What is the expression/value at ?4? [1]

(v) What is the expression/value at ?5? [1]

(i) -1 (ii) 0 (iii) divisor (iv) 0 (v) quo+1

PART II

Answer seven questions in this Part, choosing three questions from Section A and four from Section B.

SECTION A

Answer any three questions.

Question 4.

(a) Given the Boolean function F(A,B,C,D) = E(0,1,2,4,5,7,11,13,15)

Using Karnought'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. [5]

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

Quad 1 is m0+m1+m4+m5

Quad 2 is m5+m7+m13+m15

Quad 3 is m3+m7+m15+m11

Reduce Expression for Quad 1 is A'C'

Reduce Expression for Quad 2 is BD

Reduce Expression for Quad 3 is CD

Final SOP expression is A'C'+BD+CD

Your Ad Here

(b) Now given X(A,B,C,D) = II(2,3,4,7,9,10,11,12)

Use Karnought's map to reduce this function X 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. [5]

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

Quad is m3+m2+m11+m10

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')

Your Ad Here

Question 5.

The Past Pupil Association of R. K. University Computer Science Department is organizing a reunion function at the campus. The invitation card is to be issued to a person if -

The Person is an ex-student of the department and had passed out in 1995.

The Person is not an ex-student of the same department and had passed out in 1995 and has made a contribution of Rs. 1000.

The inputs are:

E: The person is ex-student of the department.

U: The person is not ex-student of the department, but a student of the same university.

P: the person passed out in 1995.

S: The person contribute Rs. 1000.

[1 indicates yes 0 indicates no in all the cases]

I: Denotes the invitation card is issued. [1 indicates yes 0 indicates no]

(a) Draw the truth tables for the inputs and outputs given above and write the SOP expression for I(E,U,P,S) [5]

Ans: SOP of I(E,U,P,S)

E	U	P	S	I
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	1
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

EU\PS	[00] P'S'	[01]P'S	[11] PS	[10] PS'
[00] E'U'	0	1	3	2
[01] E'U	4	5	1 7	6
[11] EU	12	13	1 15	1 14
[10] EU'	8	9	1 11	1 10

1 Quad (m10,m11+m14+m15)

1 pair (m7+m15)

Simplified Expression for Quad is EP

Simplified Expression for Pair is UPS

So final Reduced Expression is EP+UPS

Your Ad Here

(b) Reduce I(E,U,P,S) using Karnaugh's Map. Draw the logic gate diagram for the reduced SOP expression for I(E,U,P,S) using AND & OR gates. You may use gates with two or more inputs. Assume that variables and their compliments are available as input. [5]

Question 6.

(a) What is an encoder? State its application [2]

(b) Draw the truth table and logic circuit diagram for converting a decimal number to binary. Explain the working principle with an example. [6]

Question 7.

(a) State the difference between half adder and full adder circuit. [2]

(b) Draw the truth table and logic gate diagram of a full adder. [5]

	Full adder circuit diagram A + B + CarryIn = Sum + CarryOut A full adder is a logical circuit that performs an addition operation on three binary digits. The full adder produces a sum and carry value, which are both binary digits. It can be combined with other full adders (see below) or work on its own.
$\text{[math]}$ $C_o = (A \cdot B) + (C_i \cdot (A \oplus B)) = (A \cdot B) + (B \cdot C_i) + (C_i \cdot A)$

Questions 8.

(a) Prove that F(A,B,C)=II(2,3,4,7)=E(0,1,5,6) [3]

(b) State the dual form of the following XY'(Y'Z+X+X'Z') [3]

(d) Using NOR gates only draw a logic diagram to construct NAND gate. [2]

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.

sum= 1 + x + x³ + x⁵ + .......... + x^2n-1

1! 2! 3! n!

A class seriessum has been defined to calculate sum of the above series. Some of the members of the class are given below.

Class name	seriessum
Data member	x (integer), n (integer), sum(double)
Members functions/methods:
seriessum()	constructor.
int factorial(int)	claculate and returns factorial of n(n!) where n!=1x2x3x4.......xn
double term(int p,int q)	calculate and returns the value of p/q! by making use of factorial(int)
void accept()	input the value of member data x,n
void displaysum()	display the value of member data sum.
double calsum()	calculates the sum of the given series using the appropriate data and other member function.

(a) Specify the class serisesum giving the details of the constructors, int factorial(int), double term(int,int), void displaysum(). You may assume that other member functions are written for you. You do not need to write the main function.

(b) What care do you need to take while designing double term(int,int)

#include<iostream.h>
#include<conio.h>
#include<math.h>
class seriessum
{
private:
    int x,n;
    double sum;
public:
    seriessum()
    {
      sum=1.0;
    }
    int factorial(int n)
    {
      int f=1;
      for(int i=1;i<=n;i++)
      {
        f=f*i;
      }
      return(f);
    }
    double term(int p,int q)
    {
      p=pow(x,p);
      q=factorial(q);
      double c=(double) p/q;
      return(c);
    }
    void accept()
    {
      cout<<"enter x= ";
      cin>>x;
      cout<<"enter n= ";
      cin>>n;
    }
    void displaysum()
    {
      cout<<" sum = "<<sum;
    }
    double calsum()
    {
      int i;
      for(i=1;i<=n;i++)
      {
        sum=sum+term(2*i-1,i);
      }
      return(sum);
    }
};

Question 10.

A class indexarray contains the employee code of 100 employees. Some of the member functions/data members are given below.

Class name	indexarray
Data members	arr[] - integer
Functions/methods:
indexarray()	constructor the code to 0.
void fillarray()	to input the code in the arr[].
void sortarr()	to sort the array variable using selection sort technique.
int binarysearch(int[],int)	to search and return 1 if the employee code is found in the array object otherwise return 0.

Specify the class indexarray giving details of the constructors, void sortarr(), int binarysearch(int[],int). You may assume that other functions are written for you and you do not need to write the main function.

#include <iostream.h>
#include <conio.h>
#define MAX 100
class indexarray
{
private:
    int arr[MAX];
public:
    indexarray()
    {
      for(int i=0;i<10;i++)
        arr[i]=0;
    }
    void fillarray()
    {
      for(int i=0;i<10;i++)
      {
        cout<<"Enter Code : ";
        cin>>arr[i];
      }
    }
    void sortarray()
    {
      int small,pos,i,j;
      for(i=0;i<10;i++)
      {
        small=arr[i];
        pos=i;
        for(j=i+1;i<10;i++)
        {
          if(a[j]<small)
          {
            small=a[j];
            pos=j;
          }
        }
        int k=a[i];
        a[i]=a[pos];
        a[pos]=k;
      }
    }
    int binarysearch(int a[],int x)
    {
      int m,l=0; h=9;
      char ans='n';
      while(h>=l && ans=='n')
      {
        m=(l+h)/2;
        if(a[m]>x)
          h=m-1;
        else
          if(a[m]<x)
            l=m+1;
          else
          {
            ans='y';
            break;
          }
      }
      if(ans=='y')
        return(1);
      else
        return(0);
    }
};

Questions 11.

A class quad contains the following data member and member functions to find the roots of a quadratic equation.

Class name:	quad
Data members/instance variables:
a,b,c	of float data type.
x1,x2	of float data type.
Members functions/methods:
quad(float,float,float)	constructor to assign values to the data members.
float discriminant()	to return the discriminant[b²-4ac]
void root_equal()	to display the root if both are equal.
void imag()	to display the roots, if roots are imaginary.
void root_real()	to display the two real, unequal roots.
void root()	to call other appropriate functions to find the solution of the problem.

If ax²+bx+c=0 is the quadratic equation, then if

b²-4ac > 0 - roots are real, unequal

Where,

x1 = -b + `/(b² - 4ac)

x2 = -b - `/(b² - 4ac)

If b²- 4ac = 0 - roots are real, equal

x1 = x2 = -b/2a

If b² - 4ac < 0 - roots are imaginary

Specify the class quad giving the details of the functions quad(float,float,float). float discriminant(), void root_equal(), void root_real(), void root(). You may assume that other functions are written for you. You do not need to write the main function.

#include<iostream.h>
#include<conio.h>
#include<math.h>
class quad
{
private:
    float a,b,c,x1,x2;
public:
    quad(float x,float y,float z)
    {
      a=x;b=y;c=z;
    }
    float discriminant()
    {
      return((b*b)-(4*a*c));
    }
    void root_equal()
    {
      cout<<"roots are equal : "<<endl;
      x1=x2=-b/2*a;
      cout<<x1<<" "<<x2;
    }
    void imag()
    {
      cout<<"roots are imaginary"<<endl;
    }
    void root_real()
    {
      cout<<"roots are real : ";
      x1=(-b+pow(discriminant(),0.5))/(2*a);
      x2=(-b-pow(discriminant(),0.5))/(2*a);
      cout<<x1<<" "<<x2;
    }
};

Questions 12.

A class recursion has been defined to find the Fibonacci series upto a limit. Some of the members of the class are given below.

Class name	recursion
Data members/instance variables:
a,b,c,limit	all integer type.
Members functions/methods:
recursion()	constructor to assign a,b,c with the appropriate values.
void input()	to accept the limit of the series.
int fib(int n)	to return the nth Fibonacci term using recursive technique.
void generate_fibseries()	to generate Fibonacci series upto the given given limit.

(a) Specify the class recursion giving the details of the constructor, int fib(), void generate_fibseries(). You may assume other functions are written for you and you need not write the main function. [8]

(b) Why recursive functions result into slower execution of the program?[2]

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
class recursion
{
private:
    int a,b,c,lim;
public:
    recursion()
    {
      a=1;b=1;c=0;
    }
    void input()
    {
      cout<<"Enter Limit:";
      cin>>lim;
    }
    int fibo(int n)
    {
      if(n==1)
        return(a);
      else
      {
        c=a+b;
        a=b;
        b=c;
        return(fibo(n-1));
      }
    }
    void generate_fibseries()
    {
      for(int i=1;i<=lim;i++)
      {
        recursion::recursion();
        cout<<fibo(i)<<endl;
      }
    }
};

Question 13.

A class iscscores defines the scores of a candidates in six subjects and another class bestfour defines the best four subjects.

The details of both the classes are given below.

Class Name	iscscores
Data Member/Instance variable
int number[6][2]	to contain marks for six subjects and subject code[numeric]
Member Functions/Methods
iscscores()	constructor to accept the marks.
int point()	to return the point in each subjects according to the following: Marks>=90 1 point 80-89 2 points 70-79 3 points 60-69 4 points 50-59 5 points 40-49 6 points ------------- accordingly
Class Name	bestfour
Member Functions/Methods
void bestsubjects()	to display the total points and best four subjects codes using the concept of inheritance.

Specify the details of both the classes using the concept of inheritance. Specify the details of the constructor iscscores(), and functions int point(), void bestsubjects(). Other functions are written for you and you need not write the main function.

#include <iostream.h>
#include <conio.h>
#include <math.h>
class iscscores
{
public:
    int numbers[6][2];
    iscscores()
    {
      for(int i=0;i<6;i++)
      {
        cout<<"Enter Subject Code : ";
        cin>>numbers[i][0];
        cout<<"Enter Marks :";
        cin>>numbers[i][1];
      }
    }
    int point(int i)
    {
      int point;
      if(numbers[i][1]>=90)
        point=1;
      if(numbers[i][1]>=80 && numbers[i][1]<=89)
        point=2;
      if(numbers[i][1]>=70 && numbers[i][1]<=79)
        point=3;
      if(numbers[i][1]>=60 && numbers[i][1]<=69)
        point=4;
      if(numbers[i][1]>=50 && numbers[i][1]<=59)
        point=5;
      if(numbers[i][1]>=40 && numbers[i][1]<=49)
        point=6;
      if(numbers[i][1]>=30 && numbers[i][1]<=39)
        point=7;
      if(numbers[i][1]>=20 && numbers[i][1]<=29)
        point=8;
      if(numbers[i][1]>=10 && numbers[i][1]<=19)
        point=9;
      if(numbers[i][1]<=9)
        point=10;
      return(point);
    }
};
class bestfour : public iscscores
{
public:
void bestsubjects()
{
    int points[6][2],totpoints=0,i,j;
    // calculating points for each subject
    for(i=0;i<6;i++)
    {
      points[i][0]=numbers[i][0];
      points[i][1]=iscscores::point(i);
      totpoints+=points[i][1];
    }
    // sort the array
    for(i=0;i<5;i++)
    {
      for(j=i+1;j<6;j++)
      {
        if(points[i][1]>points[j][1])
        {
          int t=points[i][1];
          points[i][1]=points[j][1];
          points[j][1]=t;
          t=points[i][0];
          points[i][0]=points[j][0];
          points[j][0]=t;
        }
      }
    }
    // display the Best four subjects and total points
    cout<<"Total Points : "<<totpoints<<endl;
    cout<<"Best of four Subject Code is : "<<endl;
    for(i=0;i<4;i++)
      cout<<"Code: "<<points[i][0]<<"\t Point: "<<points[i][1]<<endl;
}
};

Question 14.

A class stringop is designed to handle string related operations. Some members of the class are given below.

Class Name	stringop
Data members/instance variables
txt	to store the given string of maximum length 100
Member functions/methods
stringop()	constructor
void readstring()	to accept the string
char caseconvert(int,int)	to convert the letter to other case
void circulardecode()	to decode the string by replacing ecah letter by converting it to opposite case and then by the next character in a circular way. Hence "AbZ" will be decoded as "bCa".

Specify the class stringop giving the details of the char caseconvert(int) and void circulardecode() only. You may assume that other functions are written for you. You do not need to write the main().

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<string.h>
class stringop
{
char txt[100];
public:
    void readstring();
    void circulardecode();
    char caseconvert(int);
    void display();
};
void stringop:: readstring()
{
cout<<"enter a string";
cin>>txt;
}
void stringop::display()
{
cout<<txt;
}
char stringop:: caseconvert(int c)
{
if(c>=65 && c<=90)
    c=c+32;
else
    c=c-32;
return((char)c);
}
void stringop:: circulardecode()
{
int i;
for(i=0; i<strlen(txt); i++)
{
    txt[i]=caseconvert(txt[i]);
    if(txt[i]!=90 && txt[i]!=122)
    {
      txt[i]=txt[i]+1;
    }
    else
    {
      if(txt[i]==90)
        txt[i]=65;
      else
        txt[i]=97;
    }
}
}

=*=*=*=*=*=