**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) State the Commutative law and prove it with the help of a truth table.

p + q = q + p

p . q = q . p

p | q | p + q | q + p | p . q | q . p |
---|---|---|---|---|---|

0 | 0 | 0 | 0 | 0 | 0 |

0 | 1 | 1 | 1 | 0 | 0 |

1 | 0 | 1 | 1 | 0 | 0 |

1 | 1 | 1 | 1 | 1 | 1 |

(b) Convert the following expression into its canonical POS form:

F(X, Y, Z) = (X + Y’) . (Y’ + Z)

= (X + Y’ + ZZ’) . (XX’ + Y’ + Z)

= (X + Y’ + Z) . (X + Y’ + Z’) . (X + Y’ + Z) . (X’ + Y’ + Z)

= (X + Y’ + Z) . (X + Y’ + Z’) . (X’ + Y’ + Z)

(c) Find the dual of:

(A’ + B) . (1 + B’) = A’ + B

(A’ . B) + (0 . B’) = A’ . B

(d) Verify the following proposition with the help of a truth table:

(P ∧ Q) ∨ (P ∧ ~Q) = P

p | q | ~q | p . q | p . ~q | (p . q) + (p . ~q) |
---|---|---|---|---|---|

0 | 0 | 1 | 0 | 0 | 0 |

0 | 1 | 0 | 0 | 0 | 0 |

1 | 0 | 1 | 0 | 1 | 1 |

1 | 1 | 0 | 1 | 0 | 1 |

(e) If F(A, B, C) = A'(BC’ + B’C), then find F’.

F’ = (A . (BC’ + B’C))’

= (A’)’ + (BC’ + B’C)’

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

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

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

= A + B’B + B’C’ + BC + CC’

= A + B’C’ + BC

**Question 2**

(a) What are Wrapper classes? Give any two examples.

A wrapper class is used to wrap a primitive data type value in an object. Examples: Integer class, Double class.

(b) A matrix A[m][m] is stored in the memory with each element requiring 4 bytes of storage. If the base address at A[1][1] is 1500 and the address of A[4][5] is 1608, determine the order of the matrix when it is stored in Column Major Wise.

Address of [I, J]^{th} element in column-major = B + W[R(J – L_{c}) + (I – L_{r})]

⇒ 1608 = 1500 + 4[m(5 – 1) + (4 – 1)]

⇒ 1608 = 1500 + 4[m(4) + 3]

⇒ 1608 = 1500 + 16m + 12

⇒ 1608 = 1512 + 16m

⇒ 16m = 96

⇒ m = 6.

(c) Convert the following infix notation to postfix form:

A + (B – C * (D / E) * F)

= A + (B – C * (D E /) * F)

= A + (B – (C D E / *) * F)

= A + (B – (C D E / * F *))

= A + (B C D E / * F * -)

= A B C D E / * F * – +

(d) Define Big ‘O’ notation. State the two factors which determine the complexity of an algorithm.

The Big ‘O’ notation is used to depict an algorithm’s growth rate. The two factors that determine the complexity of an algorithm are: time and space.

(e) What is exceptional handling? Also, state the purpose of finally block in a try catch statement.

The way of handling run-time errors in a program is known as exception handling. The finally block is used execute certain piece of code even when exceptions occur in a program.

**Question 3**

The following is a function of some class which checks if a positive integer is a Palindrome number by returning true or false. (A number is said to be palindrome if the reverse of the number is equal to the original number.) The function does not use modulus (%) operator to extract digit. There are some places in the code marked by ? 1 ?, ? 2 ?, ? 3 ?, ? 4 ?, ? 5 ? which may be replaced by a statement/expression so that the function works properly.

```
boolean palindromeNum(int n){
int rev = ? 1 ?;
int num = n;
while(num > 0){
int f = num / 10;
int s = ? 2 ?;
int digit = num - ? 3 ?;
rev = ? 4 ? + digit;
num /= ? 5 ?;
}
if(rev == n)
return true;
else
return false;
}
```

(i) What is the statement or expression at ? 1 ?

0

(ii) What is the statement or expression at ? 2 ?

f * 10

(iii) What is the statement or expression at ? 3 ?

s

(iv) What is the statement or expression at ? 4 ?

rev * 10

(v) What is the statement or expression at ? 5 ?

10

**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, 4, 8, 9, 10, 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’BC’D’ + ABC’D’ + AB’C’D’ = C’D’

Quad 2 = ABC’D’ + ABC’D + AB’C’D’ + AB’C’D = AC’

Quad 3 = A’B’C’D’ + A’B’CD’ + AB’C’D’ + AB’CD’ = B’D’

Reduced SOP Expression = C’D’ + AC’ + B’D’

(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, 5, 6, 7, 10, 11, 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) = (A + B’)

Quad 2 = (A + B + C’ + D’)(A + B’ + C’ + D’)(A’ + B’ + C’ + D’)(A’ + B + C’ + D’) = (C’ + D’)

Quad 3 = (A’ + B’ + C’ + D’)(A’ + B’ + C’ + D)(A’ + B + C’ + D’)(A’ + B + C’ + D) = (A’ + C’)

Reduced POS Expression = (A + B’)(C’ + D’)(A’ + C’)

(ii) Draw the logic gate diagram for the reduced expression. Assume that the variables and their complements are available as inputs.

**Question 5**

(a) A training institute intends to give scholarships to its students as per the criteria given below:

- The student has excellent academic record but is financially weak.

OR - The student does not have an excellent academic record and belongs to a backward class.

OR - The student does not have an excellent academic record and is physically impaired.

The inputs are:

INPUTS | |
---|---|

A | Has excellent academic record |

F | Financially sound |

C | Belongs to a backward class |

I | Is physically impaired |

(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 SOP expression for X(A, F, C, I).

A | F | C | I | X |
---|---|---|---|---|

0 | 0 | 0 | 0 | 0 |

0 | 0 | 0 | 1 | 1 |

0 | 0 | 1 | 0 | 1 |

0 | 0 | 1 | 1 | 1 |

0 | 1 | 0 | 0 | 0 |

0 | 1 | 0 | 1 | 1 |

0 | 1 | 1 | 0 | 1 |

0 | 1 | 1 | 1 | 1 |

1 | 0 | 0 | 0 | 1 |

1 | 0 | 0 | 1 | 1 |

1 | 0 | 1 | 0 | 1 |

1 | 0 | 1 | 1 | 1 |

1 | 1 | 0 | 0 | 0 |

1 | 1 | 0 | 1 | 0 |

1 | 1 | 1 | 0 | 0 |

1 | 1 | 1 | 1 | 0 |

SOP Expression: A’F’C’I + A’F’CI’ + A’F’CI + A’FC’I + A’FCI’ + A’FCI + AF’C’I’ + AF’C’I + AF’CI’ + AF’CI

(b) Using the truth table, state whether the following proposition is a tautology, contingency or a contradiction:

~(A ∧ B) ∨ (~A ⇒ B)

A | B | AB | ~(AB) | ~A | ~A→B | ~(AB) + (~A→B) |
---|---|---|---|---|---|---|

0 | 0 | 0 | 1 | 1 | 0 | 1 |

0 | 1 | 0 | 1 | 1 | 1 | 1 |

1 | 0 | 0 | 1 | 0 | 1 | 1 |

1 | 1 | 1 | 0 | 0 | 1 | 1 |

Tautology

(c) Simplify the following expression, using Boolean laws:

A . (A’ + B) . C . (A + B)

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

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

= ABC(A + B)

= ABC + ABC

= ABC

**Question 6**

(a) What is an encoder? Draw the encoder circuit to convert A – F hexadecimal numbers in binary. State an application of a multiplexer.

The logic circuit that converts signals of one type to another is called an encoder.

The encoder circuit to convert A to F hexadecimal numbers in binary:

(b) Differentiate between half adder and full adder. Draw the logic circuit diagram for a full adder.

A half adder is a logic circuit that adds two bits.

A full adder is a logic circuit that adds three bits.

The logic circuit of a full adder:

(c) Using only NAND gates, draw the logic circuit diagram for A’ + B.

**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**

Perfect Number Program

**Question 8**

Check for Equal Matrices Program

**Question 9**

Words with Capital Letters 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**

Number and Series Inheritance Program

**Question 11**

Register class Stack 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 n;
Node link;
}
```

Write an algorithm or a method to search for a number from an existing linked list.

The method declaration is as follows:

`void findNode(Node str, int b)`

```
void findNode(Node str, int b){
if(str == null)
System.out.println(b + " not found.");
else if(str.n == b)
System.out.println(b + " found.");
else
findNode(str.link, b);
}
```

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

(i) Write the in-order traversal of the above tree structure.

G, E, H, C, A, B, F, D

(ii) State the height of the tree, if the root is at level 0 (zero).

Height = 3

(iii) List the leaf nodes of the tree.

G, H, F