COMPUTER SCIENCE
PAPER 1
(THEORY)
(Maximum Marks: 70)
(Time allowed: Three hours)
(Candidates are allowed additional 15 minutes for only reading the paper. They must not start writing during this time.)
Answer all questions in Part I (compulsory) and six questions from Part II, choosing two questions from Section A, two from Section B and two from Section C. All working, including rough work, should be done on the same sheet as the rest of the answer. The intended marks for questions or parts of questions are given in brackets [ ].

PART I (20 Marks)
Answer all questions.
While answering questions in this part, indicate briefly your working and reasoning, wherever required.

Question 1
(a) Name and draw the logic gate represented by the following truth table, where A and B are inputs and X is the output.

XOR Gate

(b) Write the canonical POS expression of: F(P, Q) = Π(0, 2)
(P + Q)(P’ + Q)
(c) Find the dual of: X . Y + X . Y’ = X + 0
(X + Y) . (X + Y’) = X . 1
(d) If F(A, B, C) = A’ . B’ . C’ + A’ . B . C’ then find F’ using De Morgan’s Law.
A’ . B’ . C’ + A’ . B . C’
= A’ . B’ . C’ . A’ . B . C’
=(A + B + C) . (A + B’ + C)
= A + AB’ + AC + AB + BC + AC + B’C + C
= A(1 + B’) + AC + AB + BC + AC + C(1 + B’)
= A + AC + AB + BC + C
= A(1 + C) + AB + C(1 + B)
= A + AB + C
= A(1 + B) + C
= A + C
(e) If A = “It is cloudy” and B = “It is raining”, then write the proposition for:
(i) Contrapositive
B’ → A’ (If it is not raining then it is not cloudy.)
(ii) Converse
B → A (If it is raining then it is cloudy.)

Question 2
(a) What is an interface? How is it different from a class?
An interface defines a protocol of behavior. The aim of interface in Java is to dictate common behavior among objects from diverse classes.
It is different from a class because an interface only consists of abstract methods and constants, whereas this is not the case with a class.
(b) A matrix arr[-4..6, 3..8] is stored in the memory with each element requiring 4 bytes of storage. If the base address is 1430, find the address of arr[3][6] when the matrix is stored in Row Major Wise.
Number of columns, C = 8 – 3 + 1 = 6.
Address of [I, J]^th element in row-major = B + W[C(I – L_r) + (J – L_c)]
⇒ Address of ARR[3][6] = 1430 + 4[6(3 – (-4)) + (6 – 3)]
⇒ Address of ARR[3][6] = 1430 + 4[6(3 + 4) + 3]
⇒ Address of ARR[3][6] = 1430 + 4[6(7) + 3]
⇒ Address of ARR[3][6] = 1430 + 4[42 + 3]
⇒ Address of ARR[3][6] = 1430 + 4[45]
⇒ Address of ARR[3][6] = 1430 + 180
⇒ Address of ARR[3][6] = 1610.
(c) Convert the following infix notation to postfix form:
(A + B * C) – (E * F / H) + J
= (A + B C *) – ((E F *) / H) + J
= (A B C * +) – (E F * H /) + J
= (A B C * + E F * H / -) + J
= A B C * + E F * H / – J +
(d) Compare the two complexities O(n²) and O(2ⁿ) and state which is better and why?
Among O(n²) and O(2ⁿ), O(n²) is better than O(2ⁿ) because as the value of n increases, the value of O(2ⁿ) becomes much higher when compared to O(n²).
(e) State the difference between internal nodes and external nodes of a binary tree structure.
The nodes with at least one child are the internal nodes, whereas the nodes without any child are the external nodes.

Question 3
The following function mystery() is a part of some class. What will the function mystery() return when the value of num = 43629, x = 3 and y = 4 respectively? Show the dry run/working.

int mystery(int num, int x, int y){
    if(num < 10)
        return num;
    else{
        int z = num % 10;
        if(z % 2 == 0)
            return z * x + mystery(num / 10, x, y);
        else
            return z * y + mystery(num / 10, x, y);
    }
}

num = 43629
x = 3
y = 4
z = 9
9 * 4 + mystery(4362, 3, 4)
= 36 + 2 * 3 + mystery(436, 3, 4)
= 42 + 6 * 3 + mystery(43, 3, 4)
= 60 + 3 * 4 + mystery(4, 3, 4)
= 72 + 4
= 76

PART II (50 Marks)
Answer six questions in this part , choosing two questions from Section A, two from Section B and two from Section C.
SECTION A
Answer any two questions.

Question 4
(a) Given the Boolean function F(A, B, C, D) = ∑(0, 2, 3, 4, 5, 8, 10, 11, 12, 13).
(i) Reduce the above expression by using 4-variable Karnaugh map, showing the various groups (i.e. octal, quads and pairs).

Quad 1 = A’B’C’D’ + A’B’CD’ + AB’C’D’ + AB’CD’ = B’D’
Quad 2 = A’BC’D’ + A’BC’D + ABC’D’ + ABC’D = BC’
Quad 3 = A’B’CD + A’B’CD’ + AB’CD + AB’CD’ = B’C
Reduced Expression: B’D’ + BC’ + B’C
(ii) Draw the logic gate diagram for the reduced expression using only NAND gates. Assume that the variables and their complements are available as inputs.

(b) Given the Boolean function F(P, Q, R, S) = π(0, 1, 2, 8, 9, 11, 13, 15).
(i) Reduce the above expression by using 4-variable Karnaugh map, showing the various groups (i.e. octal, quads and pairs).

Quad 1 = (P + Q + R + S)(P + Q + R + S’)(P’ + Q + R + S)(P’ + Q + R + S’) = (Q + R)
Quad 2 = (P’ + Q’ + R + S’)(P’ + Q’ + R’ + S’)(P’ + Q + R + S’)(P’ + Q + R’ + S’) = (P’ + S’)
Pair 1 = (P + Q + R + S)(P + Q + R’ + S) = (P + Q + S)
Reduced expression = (Q + R)(P’ + S’)(P + Q + S)
(ii) Draw the logic gate diagram for the reduced expression using only NOR gates. Assume that the variables and their complements are available as inputs.

Question 5
(a) How is a decoder different from a multiplexer? Write the truth table and draw the logic circuit diagram for a 3-to-8 decoder and explain its working.
A decoder is a circuit which converts a binary number into its equivalent decimal form.
A multiplexer is a circuit that selects binary information from one of many input lines and directs it to a single output line.

(b) From the logic circuit diagram given below, derive the boolean expression and simplify it to show that it represents a logic gate. Name and draw the logic gate.

(X + Y) . X . Z
= XZ + XYZ
= XZ(1 + Y)
= XZ

(c) Using a truth table, state whether the following proposition is a Tautology, Contradiction or Contingency.
~(P ⇒ Q) ⇔ (~P ∨ Q)

Contradiction

Question 6
(a) The owner of a company pays bonus to his salesmen as per the criteria given below:

• If the salesman works overtime for more than 4 hours but does not work on off days/holidays.
  OR
• If the salesman works when festival sales are on and updates showroom arrangements.
  OR
• If the salesman works on an off day/holiday when the festival sales are on.

The inputs are:

(In all the above cases 1 indicates yes and 0 indicates no.)
Output: X [1 indicates yes, 0 indicates no for all cases]
Draw the truth table for the inputs and outputs given above and write the POS expression for X(O, F, H, U).

POS Expression: (O + F + H + U)(O + F + H + U’)(O + F + H’ + U)(O + F + H’ + U’)(O + F’ + H + U)(O’ + F + H’ + U)(O’ + F + H’ + U’)
(b) What is a half adder? Write the truth table and derive an SOP expression for sum and carry for a half adder.
A half adder is a logic circuit that adds two bits.
Sum SOP Expression = A’B + AB’
Carry SOP Expression = AB

(c) Simplify the following expression, using Boolean laws:
(X + Z) . (X . Y + Y . Z’) + X . Z + Y
= XY + XYZ’ + XYZ + 0 + XZ + Y
= XY(1 + Z’) + XZ(Y + 1) + Y
= XY + XZ + Y
= Y(X + 1) + XZ
= Y + XZ

Section B
Answer any two 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.
(Flowcharts and Algorithms are not required.)
The programs must be written in Java.

Question 7
Armstrong Number Program

Question 8
Matrix Reverse Program

Question 9
Rearrange Vowels and Consonants Program

Section C
Answer any two questions.
Each program should be written in such a way that it clearly depicts the logic of the problem stepwise. This can be achieved by using comments in the program and mnemonic names or pseudo codes for algorithms.
The programs must be written in Java and the algorithms must be written in general/standard form, wherever required/specified.
(Flowcharts are not required.)

Question 10
Record and Highest Class Inheritance Program

Question 11
Diary Class Queue Program

Question 12
(a) A linked list is formed from the objects of the class Node. The class structure of the Node is given below:

class Node
    int num;
    Node next;
}

Write an algorithm or a method to find and display the sum of even integers from an existing linked list.
The method declaration is as follows:
void sumEvenNode(Node str)

void sumEvenNode(Node str){
    if(str == null)
        return 0;
    else if(str.num % 2 == 0)
        return str.num + sumEvenNode(str.next);
    else
        return sumEvenNode(str.next);
}

(b) Answer the following questions from the diagram of a Binary Tree given below:

(i) Write the pre-order traversal of the above tree structure.
A → E → G → I → C → H → B → D → F
(ii) State the size of the tree.
Size means number of nodes in a binary tree.
Thus, size = 9.
(iii) Name the siblings of the nodes E and G.
Sibling of E = B
Sibling of G = C