Answer all questions in Part I (compulsory). And from Part II, choose two questions from Section A, two questions from Section B and two questions from Section C.

## Part I [20 Marks]

**Q1. a) State complementarity law and prove it with the help of a truth table.**

Complementarity laws:

p + p’ = 1

p . p’ = 0

p p' p + p' p . p'

0 1 1 0

1 0 1 0

**b) Show that X ∨ ~(Y ^ X) is a tautology.**

X Y Y ^ X ~(Y ^ X) X ∨ ~(Y ^ X)0 0 0 1 1

0 1 0 1 1

1 0 0 1 1

1 1 1 0 1

**c) Find the dual of YX + X’ + 1 = 1.**

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

**d) Draw the logic circuit of a NAND gate using NOR gates only.**

**e) If A = 1, B = 1, C = 1 and D = 0, then find its:****i) Maxterm**

A’ + B’ + C’ + D**ii) Minterm**

ABCD’

**Q2. a) Define computational complexity. Calculate the complexity using Big-O notation for the following code segment:**

```
for(int k = 0; k < n; k++)
s += k;
```

Computational complexity refers to the measure of an algorithm’s performance. The above code segment has the complexity of O(N).

**b) Differentiate between super class and subclass.**

A class that is inherited by another class is a super class. A class that inherits from another class is a subclass.

**c) Name the file stream classes to:****i) Write data to a file in binary form.**

FileOutputStream class**ii) Read data from a file in text form.**

FileReader class

**d) Convert the following infix notation to postfix notation:****X + (W + E * F) / J**

= X + (W + E F *) / J

= X + (W E F * +) / J

= X + W E F * + J /

= X W E F * + J / +

**e) A 2D array defined as A[4 … 7, -1 … 3] requires 2 word of storage space for each element. If the array is stored in row major form, then calculate the address of A[6, 2], given that the base address is 100.**

Base address = 100.

Width = 2 bytes.

Number of rows = 7 – 4 + 1 = 4.

Number of columns = 3 – (-1) + 1 = 5.

Address[I, J] = B + W[C(I – Lr) + (J – Lc)]

= 100 + 2[5(6 – 4) + (2 – (-1))]

= 100 + 2[5 × 2 + 3]

= 100 + 2[10 + 3]

= 100 + 2 × 13

= 100 + 26

= 126.

**Q3. The following function is a part of some class which computes and sorts an array arr[] in ascending order using the bubble sort technique. There are some places in the code marked by ?1?, ?2?, ?3?, ?4? and ?5?, which must be replaced by a statement/expression so that the function works properly.**

```
void bubbleSort(int arr[]){
int i, j, k, temp;
for(i = 0; ?1?; i++){
for(j = 0; ?2?; j++){
if(arr[j] > ?3?){
temp = arr[j];
?4? = arr[j + 1];
arr[j + 1] = ?5?;
}
}
}
}
```

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

i < arr.length**ii) What is the expression or statement at ?2? ?**

j < arr.length – i – 1**iii) What is the expression or statement at ?3? ?**

arr[j + 1]**iv) What is the expression or statement at ?4? ?**

arr[j]**v) What is the expression or statement at ?5? ?**

temp

## Part II

## Section A [20 Marks]

**Q4. a) Given the boolean function F(A, B, C, D) = ∑(0, 2, 6, 8, 10, 14):****i) Reduce the above expression by using 4-variable K-Map, showing the various groups (i.e. octals, quads and pairs).****ii) Draw the logic gate diagram of the reduced expression. Assume that the variables and their complements are available as inputs.**

Reduced expression: **B’D’ + CD’**

**b) Given the boolean function F(A, B, C, D) = π(0, 1, 3, 5, 6, 7, 10, 14, 15):****i) Reduce the above expression by using a 4-variable K-Map, showing the various groups (i.e. octals, quads and pairs).****ii) Draw the logic gate diagram of the reduced expression. Assume that the variables and their complements are available as inputs.**

Reduced Expression: **(A + B + C)(A’ + C’ + D)(A + D’)(B’ + C’)**

**Q5. a) A Football Association coach analyses the criteria for a win/draw of his team, depending on the following conditions:****i) If the Center and Forward players perform well but the Defenders do not perform well.****OR****ii) If the Goalkeeper and Defenders perform well but the Center players do not perform well.****OR****iii) If all the players perform well.****The inputs are:****C: Center players perform well.****D: Defenders perform well.****F: Forward players perform well.****G: Goalkeeper performs well.****Output:****X: Denotes the win/draw criteria [1 indicates win/draw and 0 indicates defeat in all cases].****Draw the truth table for the inputs and outputs given above and write the POS expression for X(C, D, F, G) using Karnaugh Map.**

C D F G 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 1

0 1 1 0 0

0 1 1 1 1

1 0 0 0 0

1 0 0 1 0

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 1

Reduced Expression: **(C + D)(D’ + G)(C’ + F)**

**b) In the following truth table, X and Y are inputs and B and D are outputs:**

INPUT OUTPUTX Y B D

0 0 0 0

0 1 1 1

1 0 0 1

1 1 0 0

**Answer the following questions:****i) Write the SOP expression for D.****ii) Write the POS expression for B.****iii) Draw the logic diagram for the SOP expression derived for D, using only NAND gates.**

i) SOP Expression: X’Y + XY’

ii) POS Expression: (X + Y)(X’ + Y)(X’ + Y’)

**c) Draw the logic circuit diagram for the following:****F = A(B’ + C) using NOR-to-NOR logic only.**

**Q6. a) Define multiplexer and state one of its uses. Draw the logic gate diagram for 4:1 multiplexer.**

A multiplexer is a combinational circuit that selects binary information from one of many input lines and directs it to a single output line.

It is used in parallel to serial connection.

**b) What is a decoder? Draw the diagram of 2-to-4 decoder.**

A decoder is a circuit which converts a binary number into its equivalent decimal form.

**c) From the logic circuit diagram given below, name the outputs (1), (2) and (3). Finally, derive the boolean expression and simplify it to show that it represents a logic gate. Name and draw the logic gate.**

**i)** X + Y’**ii)** XZ**iii)** XZ(X + Y’)**iv)** Z’ + (X + Y’)XZ

= Z’ + XZ + XY’Z

= Z’ + XZ(1 + Y’)

= Z’ + XZ

= Z’ + X

## Section B [20 Marks]

**Q7. Write a program to enter a sentence. Validate that the sentence ends with either ‘?’ or ‘.’ or ‘!’. Otherwise print error message and end execution. Count the frequency of special words i.e. words that begin and end with the same letter, and also count the frequency of palindromes.****Class name: Special****Instance variables:****s: to store the sentence.****sp: to store the frequency of special words.****palin: to store the frequency of palindromes.****Member functions:****Special(): parameterized constructor to assign user-input str to s, and 0 to sp and palin.****void display(): to display the frequency of special words and palindromes. Print the list of words that are special but not palindromes.****void countSpecial(String): to test whether the argument word begins and ends with the same letter (case-sensitive) and update the counter. Example: “noun”.****void palindrome(String): to test whether the argument word reads the same both ways (case-sensitive). Example: “dad”.****Sample Input:****Dad and mum taught me how to test for a noun.****Output:****FREQUENCY OF SPECIAL WORDS – 4****FREQUENCY OF PALINDROMES – 1****WORDS THAT ARE SPECIAL BUT NOT PALINDROMES:****taught test noun**

```
import java.io.*;
class Special{
private String s;
private int sp;
private int palin;
public Special(String str){
s = str;
sp = 0;
palin = 0;
}
public void display(){
String word = "";
String list = "";
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
if(ch == ' ' || ch == '.' || ch == '!' || ch == '?'){
int x = sp;
countSpecial(word);
int y = palin;
palindrome(word);
if(sp > x && palin == y)
list += word + " ";
word = "";
}
else
word += ch;
}
System.out.println("FREQUENCY OF SPECIAL WORDS - " + sp);
System.out.println("FREQUENCY OF PALINDROMES - " + palin);
System.out.println("WORDS THAT ARE SPECIAL BUT NOT PALINDROMES - \n" + list);
}
public void countSpecial(String w){
boolean p = false;
char a = w.charAt(0);
char b = w.charAt(w.length() - 1);
if(a == b && w.length() > 1)
sp++;
}
public void palindrome(String w){
String rev = "";
for(int i = w.length() - 1; i >= 0; i--)
rev += w.charAt(i);
if(w.equals(rev) && w.length() > 1)
palin++;
}
public static void main(String args[])
throws IOException{
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
System.out.print("Sentence: ");
String str = br.readLine();
str = str.trim();
char ch = str.charAt(str.length() - 1);
if(ch != '.' && ch != '?' && ch != '!'){
System.out.println("Invalid sentence!");
return;
}
Special obj = new Special(str);
obj.display();
}
}
```

**Q8. Design a class named Merge to combine two single-dimensional arrays without sorting.****Class name: Merge****Instance variables:****a[]: integer array.****n: size of the array.****Methods:****Merge(): parameterized constructor to assign a value to n.****void input(): to accept array elements, assuming that the inputs are in ascending order.****void display(): to display the array elements.****Merge combine(Merge): to combine data of the current object and argument in ascending order of magnitude, without duplicates and without sorting.**

```
import java.io.*;
class Merge{
private int a[];
private int n;
private int count;
public Merge(int num){
n = num;
a = new int[n];
count = 0;
}
public void input()throws IOException{
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
for(int i = 0; i < n; i++)
a[i] = Integer.parseInt(br.readLine());
}
public void display(){
for(int i = 0; i < n; i++)
System.out.print(a[i] + "\t");
System.out.println();
}
public Merge combine(Merge p){
Merge t = new Merge(this.n + p.n);
if(this.n < p.n){
int k = 0;
for(int i = 0; i < this.n; i++)
t.a[k++] = this.a[i];
for(int j = 0; j < p.n; j++)
t.a[k++] = p.a[j];
}
else{
int k = 0;
for(int j = 0; j < p.n; j++){
t.a[k++] = p.a[j];
count++;
}
for(int i = 0; i < this.n; i++){
t.a[k++] = this.a[i];
count++;
}
}
for(int i = 0; i < t.n; i++){
for(int j = i + 1; j < t.n; j++){
if(t.a[i] == t.a[j]){
t.n = t.n - 1;
for(int k = j; k < t.n; k++){
t.a[k] = t.a[k + 1];
}
j--;
}
}
}
return t;
}
public static void main(String args[])throws IOException{
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
System.out.print("Array 1 size: ");
int s1 = Integer.parseInt(br.readLine());
Merge obj1 = new Merge(s1);
System.out.println("Enter array 1 elements:");
obj1.input();
System.out.print("Array 2 size: ");
int s2 = Integer.parseInt(br.readLine());
Merge obj2 = new Merge(s2);
System.out.println("Enter array 2 elements:");
obj2.input();
Merge obj3 = obj1.combine(obj2);
obj3.display();
}
}
```

**Q9. Write a program that will allow the user to enter an integer in the range of 0 – 9999 and print it in alphabets.****Example:****INPUT:****1309****OUTPUT:****One thousand three hundred and nine**

```
import java.io.*;
class Words{
public static void main(String args[])
throws IOException{
int th = 0;
int h = 0;
int t = 0;
int ones = 0;
String result = "";
String a[] = {"", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
String b[] = {"", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("N = ");
int n = Integer.parseInt(br.readLine());
int num = n;
if(n == 0){
System.out.println("Zero");
return;
}
if(n < 0 || n > 9999){
System.out.println("Number out of range!");
return;
}
th = n / 1000;
n = n % 1000;
h = n / 100;
n = n % 100;
t = n / 10;
ones = n % 10;
if(th != 0){
result += a[th] + " thousand ";
if(t * 10 + ones == 0 && h != 0)
result += "and ";
}
if(h != 0){
result += a[h] + " hundred ";
}
if((t * 10 + ones > 0) && (h > 0 || th > 0))
result += "and ";
if(t == 1){
result += a[t * 10 + ones] + " ";
}
else if(t > 1){
result += b[t] + " ";
}
if((t > 1 && ones > 0) || (t == 0 && ones > 0)){
result += a[ones];
}
result = Character.toUpperCase(result.charAt(0)) + result.substring(1);
System.out.println(result);
}
}
```

## Section C [10 marks]

**Q10. Write the code for function int toDecimal(long, int) to find and return the decimal equivalent of a binary number.**

```
public static int toDecimal(long b, int p){
if(b == 0L)
return 0;
else{
int d = (int)(b % 10);
int t = d * (int)Math.pow(2, p);
return t + toDecimal(b / 10, p + 1);
}
}
```

**OR**

```
public static int toDec(long b, int p){
int sum = 0;
while(b != 0){
int d = (int)(b % 10);
int t = d * (int)(Math.pow(2, p));
sum += t;
p++;
b /= 10;
}
return sum;
}
```

**Q11. A class named Consumer has the following details:****Instance variables:****n: String to store consumer’s name.****ad: String to store consumer’s address.****num: String to store consumer number.****mtr: long data type to store meter number.****Methods:****Consumer(): parameterized constructor to store consumer details.****void display(): to display consumer details.****Another class named Bill has the following details:****Instance variables:****u: integer to store number of units consumed.****amt: double data type to store bill amount to be paid by the consumer.****Methods:****Bill(): parameterized constructor to assign values to data.****void compute(): calculate the bi-monthly bill as follows:**

UNITS RATE1 - 50 90p per unit + meter rent51 - 125 Rs. 1.20 per unit + meter rent125 - 300 Rs. 2.50 per unit + meter rent301 and above Rs. 3.50 per unit + meter rent

**Meter rent = Rs. 120/-****void display(): to display consumer details, units consumed and bill-amount to be paid by the consumer. Write the code for class Bill using the concept of inheritance.**

```
class Bill extends Consumer{
private int u;
private double amt;
public Bill(String name, String address, String number, long meter, int units){
super(name, address, number, meter);
u = units;
}
public void compute(){
if(u > 0 && u <= 50)
amt = 90.0 / 100 * u + 120;
else if(u > 50 && u <= 125)
amt = 1.20 * u + 120;
else if(u > 125 && u <= 300)
amt = 2.50 * u + 120;
else if(u >300)
amt = 3.50 * u + 120;
}
public void display(){
super.display();
System.out.println("Units consumed: " + u);
System.out.println("Bill amount: Rs. " + amt);
}
}
```

**Q12. a) Define:****i) Complexity:** It refers to the measure of the performance of an algorithm.**ii) Big-O number:** It is used to depict an algorithm’s growth rate.

**b) Write the algorithm to insert an integer as the first node of an existing linked list.**

```
1. N = new Node.
2. if start = NULL then start = N
3. else:
4. ptr = start.
5. N.LINK = ptr.
6. start = N.
```