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 fir 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) State the properties of zero in Boolean algebra.
0 + p = p
0 . p = 0
(b) Find the complement of the following Boolean expression using De Morgan’s law:
F(P, Q, R) = P + (Q’ . R)
= P + (Q’ . R)
= P . (Q’ . R)
= P . (Q’ + R’)
= P . (Q + R’)
(c) Find the dual of: (A’ + 0) . (B’ + 1) = A’
(A’ . 1) + (B’ . 0) = A’
(d) State whether the following proposition is a tautology, contradiction or a contingency:
F = (P → Q) ∨ (Q → ~P)
= (P’ + Q) + (Q’ + P’)
= (P’ + P’) + (Q + Q’)
= P’ + 1
= 1 (Tautology)
(e) Study the diagram given below and answer the questions that follow:
(i) Name the basic gate which is represented by the diagram.
OR gate is represented in the diagram.
(ii) What will be the value of X when A = 1 and B = 0?
Output in X will be 1.
Question 2
(a) State the difference between a Binary Tree structure and a Single Linked List.
A binary tree is a non-linear data structure, whereas a single linked list is a linear data structure.
(b) A matrix B[10][20] is stored in the memory with each element requiring 2 bytes of storage. If the base address at B[2][1] is 2140, find the address of B[5][4] when the matrix is stored in Column Major Wise.
Address of [I, J]th element in column-major = B + W[R(J – Lc) + (I – Lr)]
= 2140 + 2[10(4 – 1) + (5 – 2)]
= 2140 + 2[10 × 3 + 3]
= 2140 + 2[30 + 3]
= 2140 + 2[33]
= 2140 + 66
= 2206
(c) Convert the following infix notation to prefix form: (X + Y) / (Z * W / V)
= (+ X Y) / ((* Z W) / V)
= (+ X Y) / (/ * Z W V)
= / + X Y / * Z W V
(d) State the best case and the worst case complexity for bubble sort algorithm.
Best Case: O(N)
Worst Case: O(N2)
(e) What is the significance of the keyword ‘new’ in Java? Mention the areas where it is used.
The ‘new’ keyword is used to allocate space for the object being created in the computer’s memory. It can be used to create an array object, String object or objects of other classes.
Question 3
The following function check() is a part of some class. What will the function check() return when the value of (i) n = 25 and (ii) n = 10. Show the dry run/working.
int check(int n){
if(n <= 1)
return 1;
if(n % 2 == 0)
return 1 + check(n / 2);
else
return 1 + check(n / 2 + 1);
}(i) n = 25
⇒ 1 + check(13)
⇒ 1 + 1 + check(7)
⇒ 1 + 1 + 1 + check(4)
⇒ 1 + 1 + 1 + 1 + check(2)
⇒ 1 + 1 + 1 + 1 + 1 + check(1)
⇒ 1 + 1 + 1 + 1 + 1 + 1
⇒ 6
(ii) n = 10
⇒ 1 + check(5)
⇒ 1 + 1 + check(3)
⇒ 1 + 1 + 1 + check(2)
⇒ 1 + 1 + 1 + 1 + check(1)
⇒ 1 + 1 + 1 + 1 + 1
⇒ 5
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, 1, 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 14).
(i) Reduce the above expression by using 4-variable Karnaugh map, showing the various groups (i.e. octal, quads and pairs).
Octal 1 = A’B’C’D’ + A’B’C’D + A’B’CD + A’B’CD’ + AB’C’D’ + AB’C’D + AB’CD + AB’CD’ = B’
Octal 2 = A’B’C’D’ + A’B’C’D + A’BC’D’ + A’BC’D + ABC’D’ + ABC’D + AB’C’D’ + AB’C’D = C’
Quad 2 = ABC’D’ + ABCD’ + AB’C’D’ + A’BC’D = AD’
Reduced Expression = B’ + C’ + AD’
(ii) Draw the logic gate diagram for the reduced expression. Assume that the variables and their complements are available as inputs.
(b) Given the Boolean function: F(A, B, C, D) = π(3, 4, 6, 9, 11, 12, 13, 14, 15).
(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’ + C’ + D)(A’ + B’ + C + D)(A’ + B’ + C’ + D) = (B’ + D)
Quad 2 = (A’ + B’ + C + D’)(A’ + B’ + C’ + D’)(A’ + B + C + D’)(A’ + B + C’ + D’) = (A’ + D’)
Pair 1 = (A’ + B + C’ + D’)(A + B + C’ + D’) = (B + C’ + D’)
Reduced Expression: (B’ + D)(A + D’)(B + C’ + D’)
(ii) Draw the logic circuit diagram for the reduced expression. Assume that the variables and their complements are available as inputs.
Question 5
(a) Draw the logic circuit diagram for an octal to binary encoder and explain its working when a particular digit is pressed. Also, state the difference between encoders and decoders.
In the above circuit, when the digit 5 is pressed, then the current flows in F2 and F0, so in these gates the output is 1 whereas we have 0 in F1. So the result is 101.
An encoder is a logic circuit that converts decimal/octal/hexadecimal digit into its binary equivalent. A decoder is a logic circuit that converts a binary number into its decimal equivalent.
(b) Draw the circuit of a two input XOR gate with the help of NOR gates.
(c) Convert the following expression to its cardinal SOP form:
F(P, Q, R) = P’Q’R + P’QR + PQ’R’ + PQR’
F(P, Q, R) = Σ(1, 3, 4, 6)
Question 6
(a) A company intends to develop a device to show the high status power load for a household inverter depending on the criteria given below:
• If Air Conditioner and Geyser are on
OR
• If Air Conditioner is off, but Geyser and Refrigerator are on
OR
• If Geyser is off, but Air Conditioner and Water Purifier are on
OR
• When all are on
The inputs are:
| INPUTS | |
|---|---|
| A | Air Conditioner is on |
| G | Geyser is on |
| R | Refrigerator is on |
| W | Water Purifier is on |
(In all the above cases 1 indicates yes and 0 indicates no.)
Draw the truth table for the inputs and outputs given above and write the SOP expression for X(A, G, R, W).
| A | G | R | W | X |
|---|---|---|---|---|
| 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 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
SOP Expression: A’GRW’ + A’GRW + AG’R’W + AG’RW + AGR’W’ + AGR’W + AGRW’ + AGRW
(b) Draw the truth table and derive an SOP expression for sum and carry for a full adder. Also, draw the logic circuit for the carry of a full adder.
| A | B | C | CARRY | SUM |
|---|---|---|---|---|
| 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 |
SOP for Sum = A’B’C + A’BC’ + AB’C’ + ABC
SOP for Carry = A’BC + AB’C + ABC’ + ABC
(c) Simplify the following expression using Boolean laws:
F = [(X’ + Y) . (Y’ + Z)]’ + (X’ + Z)
= [(X’Y’ + X’Z + YY’ + YZ)]’ + (X’ + Z)
= [X’Y’ + X’Z + YZ]’ + (X’ + Z)
= (X’Y’)’ . (X’Z)’ . (YZ)’ + (X’ + Z)
= ((X’)’ + (Y’)’) . ((X’)’ + Z’) . (Y’ + Z’) + X’ + Z
= (X + Y) . (X + Z’) . (Y’ + Z’) + X’ + Z
= (XX + XZ’ + XY + YZ’) . (Y’ + Z’) + X’ + Z
= (X + XZ’ + XY + YZ’)(Y’ + Z’) + X’ + Z
= (XY’ + XZ’ + XY’Z’ + XZ’ + XYZ’) + X’ + Z
= XY’ + XZ’ + XY’Z’ + XYZ’ + X’ + Z
= XY’ + XY’Z’ + XZ’ + YXZ’ + X’ + Z
= XY'(1 + Z’) + XZ'(1 + Y) + X’ + Z
= XY’ + XZ’ + X’ + Z
= X’ + XY’ + Z + XZ’
= X’ + Y’ + Z + X
= 1 + Y’ + Z
= 1
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 program must be written in Java.
Question 7
Convert Class Program
Question 8
BinSearch Class Program
Question 9
Mix Class 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 step-wise. 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
CirQueue Class Program
Question 11
Data Interface and Base Class Program
Question 12
(a) A linked class is formed from the objects of the class Node. The class structure of the Node is given below:
class Node{
int n;
Node next;
}Write an Algorithm or a Method to find the product of the integer numbers from an existing linked list.
The method declaration is as follows:
void productNode(Node str)
void productNode(Node str){
int p = 1;
if(str == null)
p = 0;
while(str != null){
p = p * str.n;
str = str.next;
}
System.out.println("Product = " + p);
}(b) Answer the following questions from the diagram of a Binary Tree given below:
(i) Write the post-order traversal of the left sub-tree of the above structure.
G→I→D→H→F→E→J→B→C→A
(ii) State the degree of the Nodes E and H.
Degree of E = 0
Degree of H = 1
(iii) Mention the external nodes of the right sub-tree.
E and J are the external nodes in the right sub-tree.