COMPUTER SCIENCE

Paper-l (THEORY) Three hours

(Candidates arc allowed additional 15 minutes for only reading the paper.

They must NOT start writing during this time.)

Answer all questions in Part 1 (compulsory) and seven questions from Part II. choosing three questions from Section-A, two questions from Section-B and two questions from Section-Co 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

Answer all questions.

While answering questions in this Part, indicate briefly your working and reasoning, wherever required

QUestion 1

~ (b)

State the two Absorption laws. Verify anyone of them using truth table. Reduce the following expression:

F(A,B,C) = I (0,1,2,3,4,5,6,7)

Also find the complement of the reduced expression.

Name the logic gate for the following circuit diagram and write its truth table.

A B

(d) Using truth table, verify whether the following is true or false:

(p => q) = (q => p)

c.v If A=l, B=O, C=1 and D=1 find its:

ED Maxterm (i4 Minterm

This Paper consists of 9 printed pages and one blank page.

1211-868 A NS

Turnover

© Copyright reserved.

[2] [2]

[2]

[2]

[2]

flj)ocs

Quesyhn 2

~ How can we override a method in inheritance?

[2]

(b) A square matrix A[m x m] is stored in the memory with each element requiring [2] 2 bytes of storage. If the base address A[IJ[IJ is 1098 and the address at A [4J[5] is

1144, determine the order of the matrix A[ m x m J when the matrix is stored Column Major wise.

~ What is Big 0 notation? [2]

(d) What is an exception? [2]

~ Convert the following infix expression to its postfix form: [2]

a+b*c-d/e

~tion3

(a)

The following is a part of some class. What will be the output of the function mymethod( ) when the value of counter is equal to 3? Show the dry run / working.

void mymethod(int counter)

[5]

if ( counter = = 0 ) System.out.println(" ");

else

System.out.println("Hdlo"+counter); mymethod(- -counter) ; System.out.println(" "+counter);

... /The following ~nction is a part of some class which computes and returns the greatest ~ common divisor of any two numbers. There are some places in the code marked by ?1?, ?2?, ?3?, ?4? and ?5? which must be replaced by statement/expression so that the function works correctly.

int gcd(int a, int b) {

int r; while(?1?) {

r=?2?; b=?3?; a=?4?;

} if(a==O)

return ?5?; else

return -1;

2

1211-868 A NS

§ What is the expression or statement at ?1?

~ What is the expression or statement at ?2?

V

~ What is the expression or statement at ?3?

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

11] [1] IIJ 11] [1]

PART - II

Answer seven questions in (hi; part, choosing three questions from Section A, two from Section B and two from Section C.

SECTION -A Answer any three questions.

~tion4 .

~State the principle of Duality. Give the dual of the following:

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

W Reduce the Boolean expressions to their simplest forms:

/f~ ~C.D)'+ A} + A + C.D + A.B ~ A.{B+C(A.B+A.C) '}

fy using a truth table if: (AOBOC)' =A$B$C

[31

[4]

[3]

~n5

(~ven F( P, Q, R, S) = n( t. 3, 6, 7; <J, ri.rz, 13, 14, is) [5]

Reduce the above expression by using/our variable Karnaughs Map. Draw the logic

gate diagram of the reduced expression using NOR gate only.

~en F(A, B,C,D)=AB C D+A13 CI>+ A BC D,+AB CD+ABCD+AB c n, [5] Reduce the above expression by using/our variable Kamaugh's Map. Draw the logic

gate diagram of the reduced expression using NAND gate only.

Question 6

(a) Show with the help of a logic diagram how a NAND gate is equivalent to an OR gate. [3]

(b) Verify if the following is valid: [31

(a=> b) A (a=> c) = a=>(bl\ c)

(c) What is a Decoder? Draw the truth table and logic circuit diagram for a 2 to 4 Decoder. [4]

3

1211-868 A NS

Turn over

__qile'stiQn 7

_(a~hat is a Full Adder? Draw the truth table for a Full adder. Also derive SOP expression

" f~e Full Adder and draw its logic circuit.

~tate how a Decoder is differe~t from a Multiplexer. Also state one use of each. ~Convert the following cardinal expression into its canonical form and reduce it using

Boolean laws:

[4)

[3) [3)

F(L,M,O,P) = 1t (0,2,8,10)

SECTION -B

Answer any two questions.

Each program should be written in such a way that it clearly depicts the logic a/the problem.

This can be achieved by using mnemonic names and comments in the program. (Flowcharts and Algorithms are not required.)

~8

The programs must be written in Java.

Input a sentence from the user and count the number of times, the words "an" and "and" are [10J present in the sentence. Design a class Frequency using the description given below:

Class name

Frequency

Data Members / variables: text

countand

stores the sentence

to store the frequency of the word Hand"

countan

to store the frequency of the word "an" stores the length of the string

len

Member functions/methods:

Frequency( )

void accept(String n)

constructor to initialize the instance

. variables

to assign n to text, where the value of the parameter n should be in lower case.

to count the frequency of "and" to count the frequency of "an"

to display the number of "and" and "an" with appropriate messages.

Specify the class Frequency giving details of the constructor( ), void accept(String), void checkandfreq( ), void checkanfreq( ) and void display( ). Also define the maine ) function to create an object and call methods accordingly to enable the task.

void checkandfreq( )

void checkanfreq( void display( )

4

1211-868 A NS

_gu'estion 9

A class DeciDct has been defined to convert a decimal number into its equivalent octal number. Some of the members of the class are given below:

Class name

DecsOct

Data Members I instance variables:

1Il

stores the decimal number

oct

stores the octal equivalent number

Member functions:

DeciOct( )

constructor to initialize the data members n=O, oct = o.

void getnum(int nn )

assign nn to n

void deci_ oct( )

calculates the octal equivalent of 'n' and stores it in oct using the recursive technique

void show()

displays the decimal number 'n', calls the function deci _ oct( and displays its octal equivalent.

f5if- Specify the class J1eciDct, giving details of the constructor( ), void gemumnnt), [8)

void deci_oct() andvoid showt ), Also define a main() function to create an object

and call the functions accordingly to enable the task.

cb) State any two disadvantages of using recursion. [2)

5

1211-868 A NS

Turn over

Question 10

You are given a sequence of N integers, which are called as pseudo arithmetic sequences [10) (sequences that are in arithmetic progression).

Sequence ofN integers: 2, 5, 6, 8, 9, 12

We observe that 2 + 12 = 5 + 9 = 6 + 8 = 14.

The sum of the above sequence can be calculated as 14 x 3 = 42.

For sequence containing an odd number of elements the rule is to double the middle element, for example 2,5,7,9, 12

= 2 + 12 = 5 + 9 = 7 + 7 = 14.

14 x 3 = 42 [middle element = 7]

A class Pseudoarithmetic determines whether a given sequence is a pseudo-arithmetic sequence.

The details of the class are given below:

Class name

Pseudoarnhmetic

Data Members / instance variables:

n

to store the size of the sequence

integer array to store the sequence of numbers

store the status

store the sum of sequence of numbers store the sum of the two numbers

a [I

ans, flag sum

Member functions:

Pseudoarithmetic( )

default constructor

void accept( int nn )

to assign nn to n and to create an integer array. Fill in the elements of the array.

return true if the sequence is a pseudo-arithmetic sequence otherwise returns false

boolean check( )

Specify the class Pseudoarithmetic, giving the details of the constructor( ), void accept(int) and boolean check(). Also define a maine ) function to create an object and call the member functions accordingly to enable the task.

6

1211-868 A NS

SECTION -C

Answer any two questions.

Each Program / Algorithm should be written in such a way that it clearly depicts the logic of the problem step wise. This can also be achieved by using pseudo codes.

(Flowcharts are not required).

;':"0.11

A super class Record has been defined to store the names and ranks of 50 students. Define a sub-class Rank to find the highestrank along with the name. The details of both classes are given below:

The programs must he written in Java.

The Algorithm must be written in general/standard form.

[10]

Class name

Record

Data Members / instance variables: name] ]

rnk] ]

Member functions:

Record( )

void readvalues( ) void display( )

to store the names of students to store the ranks of students

Class name

constructor to initialize data members to store the names and ranks

displays the names and the corresponding ranks

Rank

Data members (instance variables: index

integer to store the index of the topmost rank

Member functions:

Rank( )

constructor to invoke the base' class constructor and to initialize index = 0

void highest( ) finds the index/location of the topmost rank and stores it in index without sorting the array.

void display( ) displays the names and ranks along with

the name having the topmost rank.

Specify the class Record giving details of the constructor( ), void readvalues( ) and void display( }. Using the concept of inheritance, specify the class Rank giving details of constructor(), void highest( ) and void display( }.

THE MAIN() FUNCTION AND ALGORITHM NEED NOT BE WRITTEN.

7

Turn over ~ 'D~(:S

1211-868 A NS

~tion12

Stack is a kind of data structure which can store elements with the restriction that an element can be added or removed from the top only.

The details of the class Stack is given below:

Class name

Stack

Data Members / instance variables:

st[ I

the array to hold the names

the maximum capacity of the string array the index of the topmost element of the stack

to count the number of elements of the stack

size

top

ctr

Member functions:

Stack( )

default constructor

Stack(int cap)

constructor to initialize size = cap and top= -1

to push a name into the stack. If the stack is full, display the message "OVERFLOW"

void pushname(String n)

String popname( )

removes a name from the top of the stack and returns it. If the stack is empty, display the message "UNDERFLOW"

Display the elements of the tad.

void display( )

)!0- Specify class Stack giving details of the constructors(), void pushname (String n), [8]

~ String popname( ) and void display().

THE MAIN( ) FUNCTION AND ALGORITHM NEED NOT BE WRITTEN.

(byunder what Principle does the above entity work? <:!uestion 13

(a) A linked list is formed from the objects of the class, class Node

{

int info; Node link;

Write an algorithm OR a Method for deleting a node from a linked list. The method declaration is given below:

void deletenode (Node start)

8

1211-868 A NS

[2]

[4)

'lJocs

(b) Distinguish between worst-case and best case complexity of an algorithm. (c) Answer the following from the diagram of a Binary Tree given below:

[2]

(i) Write the Postorder tree traversal

(ii) Name the Leaves of the tree

(iii) Height of the tree

(iv) Root of the tree

[I] [I] [I] [I]

9

1211-868 A NS