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

Answer all questions

Q-1. [5X1=5]

a)Statethedualforthefollowingexpression

(A’+B. 1). ((A’B+c).D)+A’B

b)Draw the logic digram for the following expression:

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

c)Write the complement of the following.

F(p,q,r)=pq’r+q(p’r’+pr’)

d)Find the dual of XOR gare and POS expression of XOR gate. Check if they are equal or not.

e) Convert the following expression into its canonical form.

F(X,Y,Z)=∑(1,2,7)

Q-2. [5X2=10]

a. AtwodimensionalarraydefinedasA[M][N]is stored in memory in row major arrangement with each of its elements occupying 2 bytesofstoragespace. If the address of the locations A[3][4] and a[1][1] are 226 amd 200 respectively and total bytes required for the array is 100 bytes, find the value of M and N.

b. Differentiate LIFOandFIFO.

c. Convert the following infix expression to postfix.

(A+B)*(C-d)^3+E/F

d. What is an abstract class? How do they differ from normal class?

e. What is Big O notation? What is its significance in computational complexity?

Q 3.A number can be reduced to one digit number by using the following rule Input a number and then multiply each digit of that number. This process is to be repeated until the product is reduced to one digit. The number of times digits need to be multiplied to reach one digit is called the persistence of the number. Fill the blanks with the correct code.[5]

For example 8648326(persistence 3)

341122(persistence 2)

intcomputepersistence(intn)

{

intm=n, count=0,mul=1;

while(m>0)

{

mul*=**; …1
m=m/10;
if(**) …2

{

m=mul;

mul=

*; ….3*

**; …4**

}

}

return; …5

}

}

return

*__*}

Part II

Answer six questions in this part, choosing two questions from Section A, two from B and twofrom Section C.

Section A

Answer any two questions

Q4. [2X5=10]

a)GivenF(A,B,C,D)=∑(0,5,7,8,10,12,13,14,15)

Reduce the above expression by using 4- variable-map(SOP), showing the various groups (octal, quads, pairs)[4]

Draw the logic gate diagram of the reduced expression. Assume that the variable and their complements are available as input. [1]

b) Given F(X,Y,Z,W)=π(2,3,5,7,8,12,14)

Reduce the above expression by using 4- variable-map(POS), showing the various groups (octal, quads, pairs)[4]

Draw the logic gate diagram of the reduced expression. Assume that the variable and their

complements are available as input.[1]

Q-5

a. Drawthetruth tablewith a 3 input combination which outputs 1 if there are odd number of 0’s.

Also derive an SOP expression for the output. Reduce the expression using Karnaught Map. [5]

b. What is an adder? Explain half adder. Draw the circuit and truth table. [3]

c. How is compound proposition different from the simple proposition? [2]

Q 6.

a. What is XNOR gate> Verify the complement of XNOR is XOR or not? [3]

b. Draw the diagram and truth table to execute the decimal numbers (2,3,5,7,8) and briefly explain the working. [5]

c. Draw the diagram of 4:1 multiplexer [2]

Section B

Answerany2questions.

Eachprogram shouldbewritteninsuchawaythatitclearly depicts thelogicof the problem. This canbeachievedby using mnemonicnamesand commentsin the program.

Q-7

Q-8

Q-9.

Section C

Answerany2questions.

Eachprogram/algorithm shouldbewritteninsuchawaythatitclearly depicts thelogicof the problem stepwise. This canalsobeachievedby using commentin the program andmnemonic namesorpseudocodesforalgorithms.

(Flowchartsare notrequired)

Theprogramsmustbewritten in Java.

Thealgorithmmustbewritten in generalstandard formwhereverrequired/specified.

Q 10.

A dequeue enables the user to add and remove integers from both the ends i.e. front and rear. Define a class Dequeue with the following details:

Class name :Dequeue

Data members

ele[] : array to hold integer elements.

cap : stores the maximum capacity of the array.

front : to point the index of the front.

rear : to point the index of the rear.

Memberfunctions

Dequeue(intmax) : constructor to initialize the data member cap=max, front=rear=0 and create the integer array.

void pushfront(intv) : to add integers from the front index, if possible else display the message(“full from front”).

intpopfront() : to remove and return element from front. If array is empty thenreturn-999.

voidpushrear(intv) : to add integers from the front index if possible else display the message(“full from rear”).

intpoprear() : to remove and return elements from rear. If the array is empty then return-999.

Specify the class Dequeue giving details only of the constructor(int),void pushfront(int) and intpoprear(). Assume that other functions have been defined.The main function need not be written. [5]

Q 11.An interface BankAccount is defined with a method calcInterest(), which returns the interest of the implementing Bank account.

Create the classes Simple and Compound which implements the interface BankAccount. These classes have attributes to hold the principal, time and rate of interest.

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

Interface name: BankAccount

Member functions:

doublecalcInterest(): return the interest calculated

Class name: Simple

Data members:

pri: to hold the principal amount

rate: to hold the reate of interest

time: to hold the time

Member functions:

Simple(int p, int r, int t): Parameterized constructor

doublecalcInterest():to calculate the simple interest using formula p*r*t/100

Class name: Compound

Data members:

pri: to hold the principal amount

rate: to hold the reate of interest

time: to hold the time

Member functions:

Compound(int p, int r, int t): Parameterized constructor

doublecalcInterest():to calculate the simple interest using formula p*(1+rate/100)time-p

Assume that the Interface BankAccount has been defined. Using the concept of inheritance, specify the classes Simple and Compound giving details of their constructors and calcInterest() respectively. No need to write the Interface and main method. [5]

Q 12.

a. Write down the algorithm/ method code for the following operations in a linked list. Insert a node at the end of the linked list.

The class structure is as following

class Node

{

Int num;

Node next;

}

The prototype of the function is void add(Node start, int s)

b. From the given binary tree , answer the following question.

- Print all the sibling pairs of the tree.
- State the size of the tree.
- Print the post order traversal.

` `