ISC Computer Science Theory 2015 Part IV (Solved)

This is the Section C of computer science paper. This section tests your understanding of what you have learnt in Class XII . Always be prepared with a question on stack , methods in linked list , a program to be written using the concept of inheritance (usually the program logic to be implied here is simple) and  implementation of pre / in / post order traversal of binary tree . Here goes the questions asked last year ...

Question 11 :

WordPile is an entity which can hold maximum of 20 characters . Restriction is that characters can be added or removed from only one end . Some of the members of the class are given below :

Class Name :                                                   WordPile
Data Members/ Instance variables :

ch[ ]                                                   : character array to hold character elements 
capacity                                            : Integer variable to store maximum capacity
top                                                     : to point to the index of topmost element

Methods/Member Functions :

WordPile(int cap)          : Constructor to initialise data members capacity to cap and                                               top to -1 and create WordPile.
void pushChar(char v)  : adds character to the top of the WordPile if possible                                                         otherwise outputs a message "Word Pile is full".
char popChar()                 : Returns the deleted character from WordPile if possible .                                                 otherwise returns "//".

a) Specify class WordPile giving details of the constructor and member functions .
The main function and algorithm need not be written .                                               [8]

b) What is the name of the entity described above and state one of it's applications.                                                                                                                                                  [2]


Sol.

public class WordPile
{
  char ch[] = new char[20];
  int capacity, top;
  WordPile(int cap)
  {
    capacity = cap ; 
    top = -1;
    ch = new char[capacity];
   
  }
  
  void pushChar(char v)
  {
    if(top<capacity-1)
    
      ch[++top]=v;
     
    else
      System.out.println("WordPile is full");
    
  }
  char popChar()
  {
    if(top>=0)
      return ch[top--];
    else
      return('/');

  }
}


The entity described above is a stack . 

1) Stack is used for parsing.
2) Stack is used in conversion of an expression to infix or prefix or postfix form .
3) Stack is used in recursive function.
4) Stack is used in calling function.

(Any one of the above can be stated as an expression . Whichever serves your memory right easily go for it)

Question 12 :
A line on a plane can be represented by coordinates of two endpoints p1 and p2 as p1(x1,y1) and p2(x2,y2).
A super class Plane is defined to represent a line and a sub class Circle to find the length of the radius and the area of the circle by using the required data members of super class. Some of the members of both classes are given below 

Class Name                 :                        Plane
Data Members/Instance variables :   

x1                                  : to store x coordinate of first end point
y1                                  : to store y coordinate of first end point

Member Functions/Methods :

Plane(int nx, int ny)   :  parameterized constructor to assign the data members x1=nx ,                                         y1=ny
void Show()                : to display the coordinates 

Class Name                :                  Circle

Data Members/Instance variables :   

x2                                  : to store x coordinate of second end point
y2                                  : to store y coordinate of second end point
radius                           : double variable to store the radius of the circle
area                              : double variable to store the area of the circle 

Member Functions :

Circle(...)                      : parameterized constructor to assign values to data members                                          of both the classes

void findRadius()        : to calculate the length of the radius using the formula 
                                         

                                        assuming that x1, x2, y1 and y2 are the coordinates of two                                               ends of the diameter of a circle .

void findArea()            : to find the area of the circle using formula πr² . The value of                                                pie is 22/7 or 3.14

void Show()                 : to display both the coordinates along with the length of radius                                         and area of the whole circle .

Specify the class Plane giving details of the constructor and void Show(). Using the concept of inheritance specify the class Circle giving details of the constructor , void findRadius() , void findArea() and void Show(). The main function and algorithm need not be written . 

Sol. 

public class Plane
{
  double x1 , y1;
  Plane (double nx , double ny)
   {
       x1=nx;
       y1=ny;
    }
 public void Show()
  {
   System.out.println(" X coordinate is : "+x1);
   System.out.println(" Y coordinate is : "+y1);
    
  }
}

public class Circle extends Plane
{
  double x2 , y2 , radius , area;
  Circle( double nx, double ny, double mx, double my)
  {
    super(nx, ny);
    x2=mx;
    y2=my;
  }
  
  void findRadius()
  {
    radius = (Math.sqrt(Math.pow((x2-x1),2)+Math.pow((y2-y1),2)))/2;
  }
  
  void findArea()
  {
    area = 3.14 * radius * radius;
  }
  
  void Show()
  {
    super.Show();
   System.out.println("Second X coordinate is : "+x2);
   System.out.println("Second Y coordinate is : "+y2);
   System.out.println("First X coordinate is : "+x1);
   System.out.println("First Y coordinate is : "+y1);
    System.out.println("Radius is : "+radius);
   System.out.println("Area is : "+area);
    
  }

}

Question 13  :

a) A linked list is formed from objects of the class
            class Nodes
           {
                int num;
                Nodes next;
            }

Write an algorithm or a method to print the sum of nodes that contain only odd integers of an existing linked list.
The method declaratiion is a s follows :
                                                                    void NodesCount(Nodes starptr)                [4]
Sol.
a. ) Algorithm to print the sum of nodes of odd integers of existing linked list
      1- Start 
       2- Set temporary pointer to start node
       3- Repeat steps 4 and 5 until pointer reaches null. Display the count . Exit.
       4- Check for odd integers and accumulate.
        5- Move pointer to next node
        6- Exit

Function/ Method to print the sum of nodes that only contain odd integers of existing linked list.

void NodesCount(Nodes starptr) 
  {
    Nodes temp = new Nodes(starptr);
    int sum = 0;
    while (temp!=null)
    {
      if(temp.num%2!=0)
      {
        sum = sum+tempp.num;
        temp=temp.next;
      }
     System.out.println("Sum is :"+sum);
    }
    

  }

[You have to write any one of the above. In my opinion the algorithm is simpler and you do not have to pay attention to syntaxes for it. ]
b) i) Give the meaning of the following expressions in Big O notation
                         O(n)
                         O(n²)

   ii) List any two cases to analyse algorithm complexity                            [1+1]

Sol.
i) O(n) gives the complexity of a single loop or condition (like if-else) or expression
   O(n²) gives the complexity of a nested loop that goes through iteration from 1 to n

ii) Best case and worst case complexities analyses algorithm complexity . 



c) Answer the following questions from the binary tree

i) Name the leaf nodes of right sub tree
ii) Write the post order traversal of left sub tree of node B including itself .
iii) State the levle numbers of nodes R and M when the root node is at level 0.
iv) Name the internal nodes of the tree.                                      [1+1+1+1]

Sol. 

i) P and E 
ii) R N M C B
iii) 2
iv) C,M,F,H


Note :

Nothing much to say for this section . In my earlier posts I have suggested you to write the default constructor even if not asked for as a good coding practice . But here you are asked to write only the class definition without the main class i.e. without creating the instance of the class so I have skipped writing the default constructor . Therefore the headers are also missing. Another point to note is in the inheritance question stress is given on the coding to implement the inheritance principle . So in the method for finding the radius you are free to use the math assembly instead of doing it step by step using simple arithmetic procedure. 

ISC Computer Science Theory 2015 Part III (Solved)

Here goes the Group B questions on core Java language. I am sure you know you need to attempt any two questions . Flowcharts , algorithms nothing is required you just have to write the program and that is it. So let's start .

Question 8  :
A class Admission contains the admission numbers of 100 students . Some of the data members / member functions are given below :

Class Name                                                                                                       Admission 

Data member/Instance variable                                      

Adno[] :                                                           Integer array to store admission numbers

Member Functions/Methods :

Admission()               :                                  Constructor to initialize array elements
void fillArray()         :                      to accept elements of array in descending order
int binSearch(int l , int u , int v) : to search for particular admission number                                                                          (v) using binary search and recursive                                                                                      techniques and returns 1 if found otherwise                                                                        returns -1
Specify the class Admission giving details of constructor , fillArray() and binSearch(int,int,int). Define a main function to create an object and call functions accordingly to accomplish the task.


Sol :

import java.util.*;

public class Admission
{
   
    int Adno[] = new int [100];
    Admission()
   {}
   void fillArray()
   {
    Scanner s = new Scanner(System.in);
    System.out.println("enter elements");
    for (int  i = 0 ; i <100 ; i++)
    Adno[i]= s.nextInt();
    }
  
  int binSearch(int l,int u, int v)
  {
     int mid = (l+u)/2 ; 
     if(Adno[mid] == v)
        
        return 1;
     else if(l>u)
        return -1;
      else if (Adno[mid]>v)
        return binSearch(l,mid-1,v);
     else 
         return binSearch(mid+1, u , v);
   }

public static void main(String args[])
 {
    Admission obj = new Admission();
   obj.fillArray();
  System.out.println("Enter value to be searched :");
 Scanner s = new Scanner(System.in);
int v = s.nextInt();
int p = obj.binSearch(0,obj.Adno.length-1,v);
if(p==-1)
System.out.println("Object not found!");
else
System.out.println("Object found");
 }
}

Please note that the above question asks for implementing binary search using recursive technique . If you do not follow this instruction you will be penalized . Otherwise a simple program to write . 

Question 10 :

A class Merger concatenates two positive integers that are greater than 0 and produces a new merged integer.
Example : if the first number is 23 and second is 764 , the new number is 23764.

Some of the members of the class are given below 

CLASS                                                                                                Merger
Data Members/ Instance Variables :                                               

n1                                                         : long integer to store first number 
n2                                                          : long integer to store second number 
mergNum                                            :  long integer to store merged number 

Member Functions :

Merger()                                              : Constructor to initialize data members 
void readnum()                                   : Function to accept values of numbers n1 and n2 
void JoinNum()                                   : To concatenate numbers n1 and n2 to store it in                                                                                  mergNum
void show()                                          : To display the original numbers and merged number with                                                                  appropriate messages .   

Specify the class Merger , giving details of constructor , void readNum() , void JoinNum() and void show() . Define main () function to create an object and call the functions accordingly to enable the task . 

Sol :

import java.util.*;

public class Merger
{
  long n1 , n2 , mergNum;
  Merger(){}
  void readNum()
  {
    Scanner s = new Scanner(System.in);
    System.out.println("Enter First Number:");
    n1 = s.nextLong();
    System.out.println("Enter Second Number");
    n2 = s.nextLong();
  }
  
  void JoinNum()
  {
    if(n1>0 && n2>0)
  {
    String s1 = Long.toString(n1);
    String s2 = Long.toString(n2);
    String s3 = s1 + s2;
    mergNum = Long.valueOf(s3);
  }

  else 
          System.out.println("One or both the numbers are 0 or less than that , concatenation                                                     not possible !");

// It is better to use this if-else loop , since in the question it is mentioned that the class concatenates the string only if it finds out that the numbers are greater than 0 . 
    
  }
  
  void show()
  {
    System.out.println("First Number : "+n1);
    System.out.println("Second Number : "+n2);
    System.out.println("Merged Number : "+mergNum);
    
  }
  
  public static void main(String[] args)
  {
    Merger obj = new Merger();
    obj.readNum();
    obj.JoinNum();
    obj.show();
    
  }
}

Question 10 :

A class TheString accepts a string of a maximum 100 characters with only a blank space between the words . 
Some of the members of the class are given below 
 
Class Name     :                                                                       TheString
Data Member/Instance Variables : 
str                                                     : To store the string 
len                                                     :  integer to store length of string 
wordcount                                        :  integer to store number of words 
cons                                                   : integer to store number of consonants 

Member Functions / Methods 

TheString()                                      : default constructor to initialize data members 
TheString( String ds)                      : parameterized constructor to assign str = ds
void countFreq()                              : to count the number of words and number of consonants                                                                  and store them in wordcount and cons respectively.
void Display()                                   : to display the original string , along with number of words                                                                and number of consonants 

Specify the class TheString giving the details of constructor , countFreq()  , Display() . Define the main function . create an object of the class and call the member functions accordingly to enable the task . 

import java.util.*

public class TheString
{
 String str;
  int len, wordcount, cons;
  TheString(){}
  TheString(String ds)
  {
    str = ds;
    len = str.length();
  }
  void countFreq()
  {
    char c ;
    String str1 = str.toLowerCase(); //lower case conversion simplifies the string handling to find the                                                         consonants. You can change to uppercase also . But semantics will                                                          change a bit to count the consonants.
    for (int i = 0 ; i<len; i++)
    {
      c = str1.charAt(i);
      if(c==32 || i==len-1) // 32 denotes space, || i=len-1 is used to mark the end of string input 
        wordcount++;
      if(c!='a' && c!='e' && c!='i' && c!='o' && c!='u' && c!=32)  //if c!32 is not mentioned blank                                                                                                     spaces will be counted as consonants
      cons++;
     
    }
  }
 
 
 
  void Display()
  {
    System.out.println("Original String : "+str);
    System.out.println("Number of words : "+wordcount);
    System.out.println("Number of consonants : "+cons);
   
  }
 
  public static void main(String[] args)
  {
    TheString obj = new TheString("Today is Republic Day.");
    obj.countFreq();
    obj.Display();
   
  }
}

Synopsis 

Nothing much needs to be mentioned . The first two questions are pretty straight forward and should not consume much time to write . The third one has two points to keep in mind :

 1) To count the number of words , you have to consider the spaces . But what about the sentence that does not end with a space ? So you have to check where the string ends too otherwise you will end up getting a word less than the actual number of words in original string.

2) We usually check if a character is a vowel to count the consonants , but here the string contains spaces , so if we do not mention it in the condition checking not to consider the space as a consonant , the number of spaces present also gets added to the number of consonants. 

So in my opinion in the examination hall you might not get adequate time to think on these points and also you cannot avail yourself of the compiler to find out where you have gone wrong  so it is better to avoid the third program or Question no 10. 

ISC Computer Science Class XII 2015 Theory Part II (Solved)

Question 4
a) Given Boolean Function F(A,B,C,D) = π(0,1,2,3,5,7,8,9,10,11)
        i) Reduce the above expression using 4-variable Karnaugh Map , showing the various groups (i.e. octal , quad and pair)                                                                              [4]
       ii) Draw the logic gate diagram for the reduced expression . Assume that the variables and the complements are available as inputs.                                                             [1]

Sol i)

From the above Karnaugh Map we get a octet (M₀M₁M₂M₃M₈M₉M₁₀M₁₁ ) that gives reduced                                                                                                                                          expression : B
                                The quad (M₁M₃M₅M₇₎  gives expression :A+D'
Therefore, the reduced expression for the Boolean Function is B.(A+D')

ii)

b) Given Boolean Function
                P(A,B,C,D)= ABC'D'+ A'BC'D' + A'BC'D + ABC'D+A'BCD + ABCD
      i) Reduce the above expression using 4-variable Karnaugh Map , showing the various groups (i.e. octal , quad and pair)                                                                              [4]
       ii) Draw the logic gate diagram for the reduced expression . Assume that the variables and the complements are available as inputs.                                                                  [1]

Sol i)

    From the first quad ( m₄m₅m₁₂m₁₃)  we get  :     BC'
    From the second quad (m₅m₇m₁₃m₁₅)we get : BD
   Therefore the reduced expression of the above Boolean Sum of Products expression is : BC'+BD

ii)

Question 5. 
A person is allowed to travel on a reserved coach on train , if he/she satisfies the criteria below

• Person has a valid reservation ticket and a valid ID proof               OR
• The person does not have a valid reservation ticket , but holds a valid pass issued by Railway department with a valid ID proof.                                                     OR
• The person is disabled and holds a valid pass issued by the Railway department along with a valid ID proof.

The inputs are :

Input
R	Person has valid reservation ticket
P	Person holds a valid pass from Railway Department
D	Person has a valid ID proof
H	Person is disabled

 (In all the above cases 1 indicates YES and 0 indicates NO.)

Output : T - Denotes allowed to travel. 1 indicates YES and 0 indicates NO

a) Draw the truth table for the inputs and outputs given . Write the POS expression for T(R,P,D,H). [5]

b) Reduce T(R,P,D,H) using Karnaugh map. Draw the logic gate diagram for the reduced POS using only NOR gates

assuming that the variables and their complements are allowed as inputs.           [5]

Sol, 

a)

R	P	D	H	T
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	1
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

The POS expression for the above truth table is : 

                           T(R,P,D,H) = π(0,1,2,3,4,5,8,9,12,13)

b)  

From the quad (M₀M₁M₂M₃)  : R+P
From the octal (M₀M₁M₄M₅M₈M₉M₁₂M₁₃) : D

Therefore , the reduced POS of T(R,P,D,H) = (R+P).D

Question 6.

a) Draw the truth table and logic diagram for an octal to binary encoder.                                  [4]

Sol.

Octal No.	Truth Table								Output
	D0	D1	D2	D3	D4	D5	D6	D7	a	b	c
0	1	0	0	0	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0	0	0	1
2	0	0	1	0	0	0	0	0	0	1	0
3	0	0	0	1	0	0	0	0	0	1	1
4	0	0	0	0	1	0	0	0	1	0	0
5	0	0	0	0	0	1	0	0	1	0	1
6	0	0	0	0	0	0	1	0	1	1	0
7	0	0	0	0	0	0	0	1	1	1	1

 b) What is Multiplexer? State an application of Multiplexer. Also, draw the logic diagram of 4:1 Multiplexer. [4]

Sol. 

A multiplexer is a combinational circuit that selects binary information from one or many lines and directs it to a single output line.

It is used for bandwidth utilization so finds it's application in data transmission , routing of signal , telephone exchange.

The Logic circuit is as follows;

c) Verify the following expression using Boolean Laws. Also, mention the laws used at each step of simplification.
                         X.Y.Z+X.Y'.Z+X.Y.Z' = X.(Y+Z)                                                       [2]

Sol.
 L.H.S.= X.Y.Z+X.Y'.Z+X.Y.Z'
           =X.Y.Z+X.Y.Z'+X.Y'.Z
           =X.Y.(Z+Z') + X.Y'.Z
           = X.Y+ X.Y'.Z            (Since by Complementary Law Z+Z'=1)
           =X.(Y+Y'Z)
           =X.(Y+Y')(Y+Z)         (Since by Distributive Law A+B.C=(A+B).(A+C))
           =X.(Y+Z)                   (Since by Complementary Law Y+Y'=1)
           = R.H.S.


Question 7:

a) Derive a Boolean expression for the logic circuit given below and reduce the derived expression using Boolean Laws.         [3]

Sol.  

1. A'

2. B'

3. C'

4. A'.B'.C'

5 (A'.B'.C')'

6. (A'.B'.C')'.C

7. X =  (A'.B'.C')'.C+(A'.B'.C')'

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

=( A+B+C).C+(A+B+C)

= A.C+B.C+C.C+A+B+C

= A.C+B.C+C+A+B+C

=(A.C+A) +( B.C+ B) + C

=A+B+C

b) What are universal gates ? Construct a logic circuit using NAND gates only for expression          A.(B+C) .                                                                                                                 [4]

Sol. When any digital system can be implemented by a logic gate , the gate is said to be universal . Eg : NAND gates . 

c) Define Half Adders. Draw circuit diagram and truth table for a Half Adder .    [4]

Sol,

c)  Half Adder is an example of a simple functional digital circuit built from two logic gates . The half adder adds two one-bit binary numbers (A, B) .  The output is the sum of two bits (S) and the carry (C). The truth table of the half adder is as follows 

                            The logic diagram of half adder is given below,

[Note :  You are to solve any three questions from this part . As I have mentioned in a post earlier , it is better to attempt the two questions on Karnaugh Map . Question No 6 involves truth tables , diagrams that are quite time consuming . Question 4 is pretty straight as expected. Question 5 is easy, only you have to be patient while computing the truth table. Questions 7b and 7c are again nothing tricky . Attempt 7a step by step . Write the output for each gate on the diagram of your question paper and you are good to go .]