(a) (i) According to the Principle of duality, the Boolean equation : (A+B').(A+1)=A+B will be equivalent to:
(a) (A'+B).(A'+1)=A'+B
(b) (A.B')+(A.0)=A.B'
(c) (A'.B)+(A'.1)=A'.B
(d) (A'.B)+(A'.0)=A'.B

Solution

(b) (A.B')+(A.0)=A.B'

(ii) When a sequence of OR, NOT, NOR are connected in series, the logic gate obtained is:
(a) AND
(b) NOT
(c) OR
(d) XOR

Solution

(c) OR

(iii) ldempotence Law states that:
(a) X+X=X
(b) X+X'=0
(c) X+X=1
(d) X+X=X

Solution

(a) X+X=X

(iv) Assertion: For proposition ~A => B, its contrapositive is B =>~A
Reason: Contrapositive is the converse of inverse for any proposition.
(a) Both Assertion and Reason are true, and Reason is the correct explanation for the Assertion.
(b) Both Assertion and Reason are true, but Reason is not the correct explanation for the Assertion.
(c) Assertion is true but Reason is false.
(d) Assertion is false but Reason is true.

Solution

(d) Assertion is false but Reason is true.

(v) The complement of the Boolean expression (P'. Q)+ (R . S') is:
(a) (P'+Q).(R'+S)
(b) (P+Q').(R'+S)
(c) (P'+Q).(R+S')
(d) (P+Q').(R+S')

Solution

(b) (P+Q').(R'+S)

(vi) Assertion: Recursive data structure follows the LIFO principle.
Reason: Execution of recursive code follows the concepts of data structure Queue.
(a) Both Assertion and Reason are true, and Reason is the correct explanation for the Assertion.
(b) Both Assertion and Reason are true, but Reason is not the correct explanation for the Assertion.
(c) Assertion is true but Reason is false.
(d) Assertion is false but Reason is true.

Solution

(c) Assertion is true but Reason is false.

(vii) State any one use of interfaces in Java.

Solution

To achieve multiple inheritance

(viii) Write the cardinal form of the maxterm X +Y'+Z

Solution

π(2)

(ix) Write the canonical SOP expression for F (A, B) = A <=>B

Solution

a.b + a'.b'

(x) State any one difference between instance variable and class variable.

Solution

The one difference between the class variable and instance variable is class variables are defined within the class. Instance variables are defined within class methods. Any changes made to the class variable will affect all instances. Any changes made to the instance variable does not affect all instances.

(i) Convert the following infix notation to postfix form.
(P+Q*R-S)/T*U

Solution

= (P + QR* - S) / T*U
=PQR*+S- / T*U
=PQR*+S-T/ * U
= PQR*+S-T/U*

(ii) An array ARR [ -5 .....15,10.....20 ] stores elements in Row Major Wise with each clement requiring 2 bytes of storage. Find the address of ARR[10][15] when the base address is 2500.

Solution

Given:
Base address: 2500
Size of each element = 2 bytes
Number of columns(C) = 20−10+1=11
Row number(i) (for ARR[10][15]) = 10
Column number(j) (for ARR[10][15]) = 15
Address of ARR[10][15] = BA + w[(i-lr)*C +(j-lc)]
Address=2500+[(10+5)×11+(15-10)]×2
Address=2500+[11*15+5]×2
Address=2500+[165+5]x2
Address=2500+170x2
Address=2840

(iii) The following function is a part of some class:
int jolly(int[ ] x, int n, int m)
{
if (n < 0)
return m;
else if(n< x.length)
m = (x[n] >m)? x[n] : m;
return jolly(x, --n, m);
}
(a) What will be the output of jolly() when the value of x[]={6,3,4,7,1} n=4 and m=0?
(b) What function does jolly() perform, apart from recursion?

Solution

(iv) The following function is a part of some class which is used to find the smallest digit present in a number. There are some places in the code marked by ?1?, ?2?, ?3? which must be replaced by an expression / a statement so that the function works correctly.
int small_dig(int n)
{
int min=?1?;
while (n!= 0)
{
int q=n/10;
int r= ?2? * 10;
min= r>min? ?3? :r;
n=q;
}
return min;
}
(a) What is the expression or statement at ?1?
(b) What is the expression or statement at ?2?
(c) What is the expression or statement at ?3?

(i) To be recruited as the Principal in a renowned College, a candidate must satisfy any one of the following criteria:
• The candidate must be a Postgraduate and should either possess a B.Ed. degree or a teaching experience of more than 15 years.
OR
• The candidate must be an employee of the same college with a teaching experience of more than 15 years.
OR
The candidate must be a Postgraduate but not an employee of the same college and should have a teaching experience of more than 15 years.
The inputs are:
P Candidate is a Postgraduate
S Candidate is an employee of the same College
E Candidate has a teaching experience of more than 15 years
B Candidate possesses a B.Ed. degree
(In all the above cases, 1 indicates yes and 0 indicates no)
Output: X Denotes eligibility of a candidate [1 indicates eligibility and O indicates ineligibility in all cases]
Draw the truth table for the inputs and outputs given above and write the SOP expression for X (P, S, E, B).
(ii) Reduce the above expression X (P, S, E, B) by using 4-variable Karnaugh map, showing the various groups (i.e., octal, quads and pairs). Draw the logic gate diagram for the reduced expression. Assume that the variables and their complements are available as inputs.

Solution

(i) (a) Reduce the Boolean function F (A,B,C,D) = π (0, 2, 4, 6, 8, 9, 10, 11, 14) by using 4-variable Karnaugh map, showing the various groups (i.e., octal, quads and pairs).
(b) Draw the logic gate diagram for the reduced expression. Assume that the variables and their complements are available as inputs.
(ii) Verify if the following proposition is a Tautology, Contradiction or a Contingency, using a truth table.
((A => B)^(B => C)) => (A => C)
(iii) Find the complement of the following expression and reduce it by using Boolean laws.
P (P+Q) Q (Q+R')

Solution

(i) How is a decoder different from a multiplexer? Draw the logic circuit for 3:8 decoder (Octal decoder). Which multiplexer can be derived from the Octal decoder?
(ii) Draw the logic gate diagram for 2-input OR gate using NAND gates only. Show the expression at each step.
(iii) Write the canonical form of the cardinal terms, m3 and Ms for F (A, B, C, D).

Solution

A multiplexer is a device which consists of multiple input channels through a single line while decoder consists of multiple inputs passing through multiple outputs. Multiplexer converts inputs from unary codes (initial) to binary codes while decoder converts binary codes to inputs.

Design a class DeciHex to accept a positive integer in decimal number system from the user and display its hexadecimal equivalent

Example 1: Decimal number = 25    Hexadecimal equivalent = 19 
Example 2: Decimal number = 28    Hexadecimal equivalent = 1C 

Some of the members of the class are given below. 
Class name:    DeciHex 
Data members/instance variables: 
num : stores the positive integer 
hexa : string to store the hexadecimal equivalent of num 

Methods / Member functions: 
DeciHex(): constructor to initialise the data members with legal initial values 
void getNum(): to accept a positive integer 
void convert(int n): to find the hexadecimal equivalent of the formal parameter ‘n’ using the recursive technique 
void display(): to display the decimal number and its hexadecimal equivalent by invoking the function convert()  

Specify the class DeciHex giving details of the constructor( ), void getNum( ), 
void convert(int) and void display(). Define a main() function to create an object and call all the functions accordingly to enable the task. 
               

Solution:

import java.util.*;
class DeciHex
{
    int num;
    String hexa;
    DeciHex(){
        num=0;
        hexa="";
    }

    public void getNum()
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the positive number");
        num=sc.nextInt();
    }

    void convert(int n)
    {
        if(n!=0)
        {
            int d=n%16;
            System.out.println(d);
            if(d>10)
            {
                hexa=(char)(d+55)+hexa;
            }
            else
            {
                hexa=d+hexa; 
            }
            convert(n/16);            
        }
    }

    void display()
    {
        System.out.println("Number in Decimal Equivalent="+num);
        convert(num);
        System.out.println("Number in HexaDecimal Equivalent="+hexa);
    }

    public static void main(String []args)
    {
        DeciHex ob=new DeciHex();
        ob.getNum(); 
        ob.display();
    } 
}
     
                                            

A class InsSort contains an array of integers which sorts the elements in a particular order.
Some of the members of the class are given below:
Class name:InsSort
Data members/instance variables:
arr[]:Stores the array element
size:stores the number of elements in the array

Methods/Member functions
InsSort(int s): constructor to intialize size=s
void getArray(): accepts the array elements
void insertionSort(): sorts the elements of the array in descending order using the Insertion Sort technique 
double find(): calculates and return the average of all the odd numbers in the array
void display(); displays the elements of the array in a sorted order along with the average of all the odd numbers in the array by invoking the function find() with an appropriate message

Specify the class InsSort giving giving details of the constructor( ), void getArray,
void insertionSort(), double find() and void display(). Define a main() function to create an object and call all the functions accordingly to enable the task. 
            

    
import java.util.*;
class InsSort
{
    int arr[];
    int size;
    public InsSort(int s)
    {
        size=s;
        arr=new int[size];
    }

    public void getArray()
    {
        Scanner sc = new Scanner(System.in);
        for(int i = 0; i < size; i++)
        {

            System.out.println("Enter the "+i+" element:"); 
            arr[i] = sc.nextInt();
        }
    }

    void insertionSort()
    { int temp,j;
        for (int i = 1; i < size; i++) 
        { 
            temp = arr[i]; 

            j = i - 1; 
            while (j >= 0 && arr[j] > temp) 
            { 
                arr[j + 1] = arr[j]; 
                j = j - 1; 
            } 
            arr[j + 1] = temp; 
        }
    }

    double find()
    { int sum=0,count=0;
        for (int i = 0; i < size; i++) 
        { 
            if(arr[i]%2!=0)
            {
                sum+=arr[i]; 
                count+=1;

            }
        }
        double avg=sum/count;
        return avg;
    }

    void display()
    {
        System.out.println("Original Array is :");  
        for(int i=0; i < size; i++) {  
            System.out.print(arr[i]+ "  ");  
        }
        insertionSort();
        System.out.println("\nAfter Sorting Array is :");
        for(int j=0; j < size; j++) {  
            System.out.print(arr[j]+ "  ");  
        }

        System.out.println("\nAverage of all the odd numbers in the array is="+find());
    }

    public static void main(String []args)
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter the size of elements");
        int s=sc.nextInt();
        InsSort ob=new InsSort(s);
        ob.getArray(); 
        ob.display();
    } 
}
            
                                            

Design a class Coding to perform some string related operations on a word containing alphabets only.
Example:Input: "Java"
Output:Original word: Java
J=74
a=97
v=118
a=97

Lowest ASCII code:74
Highest ASCII code:118
Some of the members of the class are given below. 
Class name: Coding 
Data members/instance variables:
wrd - stores the word
len - stores the length of the word 

Methods / Member functions:
Coding(): constructor to initialise the data
members with legal initial values
void accept(): to accept a word 
void find() : to display all the characters of ‘wrd’ along with their ASCII codes. Also display the lowest ASCII code and the highest ASCII code,in 'wrd'
void show( ) : to display the original word and all the characters of ‘wrd’ along with their
ASCII codes. Also display the lowest ASCII code and the highest ASCII code in ‘wrd’, by invoking the function find().

Specify the class Coding giving details of the constructor( ), void accept( ),
void find( ) and void show( ). Define a main() function to create an object and call all
the functions accordingly to enable the task. 
            

import java.util.*;
public class Coding
{
    String wrd;
    int len;
    public Coding() 
    {
        wrd = "";
        len = 0;
    }

    public void accept() {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the sentence: ");
        wrd = sc.nextLine();
    }

    public void find()
    {   char lowest='z',highest='a';
        for(int i=0;i< wrd.length();i++)
        {
            char ch=wrd.charAt(i);
            System.out.println(ch+"="+(int)ch);
            if(ch< lowest)
            {
                lowest=ch;
            }
            else if(ch>highest)
            {
                highest=ch;
            }
        }
        System.out.println("Highest ASCII Code="+(int)highest);
        System.out.println("Lowest ASCII Code="+(int)lowest);
    }

    public void show() 
    {
        System.out.println("Original Word="+wrd);
        find();
    }

    public static void main(String args[ ])
    {
        Coding obj = new Coding();
        obj.accept();
        obj.show();
    }
}                   
    
            
                                            

CardGame is a game of mental skill, built on the simple premise of adding and removing the cards from the top of the card pile.

Class name : CardGame 

Data members/ instance variables: 
cards[] : array to store integers as cards
cap: to store the maximum capacity of array
top: to store the index of the topmost element of the array 

Methods / Member functions: 
CardGame(int cc): constructor to initialise cap=cc and top=-1 
void addCard(int v): to add the card at the top index if possible,otherwise display the message
“CARD PILE IS FULL”
int drawCard(): to remove and return the card from the top index of the card pile, if any, else return the value -9999
void display(): to display all the cards of card pile 

(i) Specify the class CardGame giving details of the functions void addCard(int) 
and int drawCard(). Assume that the other functions have been defined.
The main() function and algorithm need NOT be written.

(ii) Name the entity described above and state its principle. 

            

class CardGame
{
    int cards[];
    int top;
    int cap;

    // creating a stack
    CardGame(int cc)
    {
        cap=cc;
        top=-1;
        cards=new int[cap];
    }

    //Adding element in the top of stack
    public void addCard(int v)
    {
        if(top ==(cap-1))
            System.out.println("Card PILE IS FULL");

        else{
            System.out.println("Inserting: "+v);
            top=top+1;
            cards[top]=v;
        }
    }

    public int drawCard()
    {
        if(top==-1)
        {
            return -9999;
        }
        else{
            int val=cards[top];
            top=top-1;
            return val;
        }
    }

    public void display()
    {

        for(int i=0;i< top;i++)
        {
            System.out.print(cards[i]+",");    
        }
        System.out.print(cards[top]);
    }

    public static void main(String args[])
    {
        CardGame stack=new CardGame(10);
        // adding element
        stack.addCard('a');
        stack.addCard('b');
        stack.addCard('c');

        // display stack
        System.out.println("Current Cards: ");
        stack.display();

        //remove element
        System.out.println("\n\nDeleting Element");
        int ele=stack.drawCard();
        System.out.println("Element Removed:"+ele);

        // display stack
        System.out.println("Current Cards: ");
        stack.display();

    }
}


            
                                            

A super class EmpSal has been defined of an employee.Define a subclass Overtime to compute the total salary,after adding the overtime amount based on the following criteria.

• If hours are more than 40,then ₹5000 are added to salary as an overtime amount
• If hours are between 30 and 40 (both inclusive),then ₹3000 are added to salary as an overtime amount 
• If hours are less than 30,then the salary remains unchanged 

The details of the members of both the classes are given below. 

Class name: EmpSal

Data members/instance variables:
empnum: to store the name of the employee 
empcode: integer to store the employee code  
salary: to store the salary of the employee in decimal

Methods / Member functions:

EmpSal(...): parameterised constructor to assign values to data members
void show(): to display the details of the employee 


Class name: Overtime
Data members/instance variables:
hours: integer to store overtime in hours
totsal: to store the total salary in decimal 

Methods / Member functions:

Overtime(...): parameterised constructor to assign values to data members of both the classes
void calSal(): calculates the total salary by adding the overtime amount to salary as per the criteria given above
void show(): to display the employee details along with the total salary (salary + overtime amount) 

Assume that the super class EmpSal has been defined. Using the concept of inheritance,
specify the class Overtime giving the details of the constructor (...), void calSal() and
void show().

The super class, main function and algorithm need NOT be written. 
               
            

    
class EmpSal
{
    int empnum,empcode;
    double salary;
    EmpSal(int en,int ecode,double sal)
    {
        empnum=en;
        empcode=ecode;
        salary=sal;
    }

    void show()
    {
        System.out.println("Employee Name"+empnum);
        System.out.println("Employee Code"+empcode);
        System.out.println("Employee Salary"+salary);
    }
}


class Overtime extends EmpSal
{
    int hours;
    double totsal;
    Overtime(int en1,int ecode1,double sal1,int h)
    {
        super(en1,ecode1,sal1);
        hours=h;
        totsal=0.0;
    }
    void calSal()
    {
        if(hours>40)
        {
            totsal=salary+5000;
        }
        
        else if(hours>=30 && hours <=40)
        {
            totsal=salary+3000;
        }
        else if(hours< 30)
        {
            totsal=salary;
        }
    }
    void show()
    {
        super.show();
        calSal();
        System.out.println("Total Salary is="+totsal);
    }
}

                                            

(i) With the help of an example,briefly explain the dominant term in complexity
(ii) Answer the following questions based on the diagram of a Binary Tree given below:

(a) Name the external nodes of the tree.
(b) State the degree of node M and node L. 
(c) Write the post-order traversal of the above tree structure. 
            

Solution:

(b) (i) Imagine you're baking cookies. You have a recipe (your program) that tells you what ingredients you need and what steps to follow.
Now, let's say you want to know how long it will take to bake a batch of cookies. The time it takes depends on a few things, like how many cookies you're making and how fast you can bake them.
In computer science, we're interested in figuring out how long programs take to run, like our cookie-baking recipe. We use something called "complexity" to measure this.
The "dominant term" in complexity is like the main ingredient in your recipe. It's the part that has the biggest impact on how long your program takes to run.
For example, let's say you have a recipe to make sandwiches, and it tells you to put together each sandwich one by one. If you want to make 10 sandwiches, it might take you a certain amount of time. But if you want to make 100 sandwiches, it'll take you much longer because you have to do everything 10 times more.
In computer science terms, if the time it takes to run a program increases linearly with the size of the input (like making sandwiches), we say it has a "linear" complexity. Here, the number of sandwiches is the dominant term because it determines how long it takes to make them.
Understanding the dominant term helps us predict how long our programs will take to run when we give them bigger tasks, just like knowing the main ingredient helps you understand how long it'll take to make a bigger batch of cookies.

(ii) (a) F,I,G,C
(b) M=2    L=1
(c) F,I,M,E,C,L,G,H,A