DEPT:

CSE and Allied Departments

SEMESTER: 5th

SUBEJCT
ESP(CS)-501
CODE:

SUBEJCT
Essential Studies for Professionals - V
NAME:

Section
Text Book Name, Chapte
Module No. No. (if Exercise Nos.
Author, Publisher r No
any)
Computer System 5, 7, 9, 2, 4, 1, 5,
Architecture, 1, 2, 3, 7, 9, 10, 2, 6, 3,
Third Edition , 4 5, 2, 7, 8, 3, 5, 2,
Morris Mano 6, 2, 6, 2
G.K publishers
2, 6, 8, 7, 3, 5, 4,
GATE Computer
Module 1 2, 3, 4 7, 4, 2, 11, 7, 8,
Science
3, 5
Engineering
Computer System
Architecture, 2, 4, 3, 5, 10, 38,
3, 4, 5
Third Edition , 56, 58, 65, 5, 8, 9
Morris Mano
G.K publishers
Module 2 GATE Computer GATE Previous
3
Science Year Questions
Engineering

Computer
1, 2,
Organization and 1, 4 , 5
4,5,6
Module 3 Design, Patterson

Discrete Mathametics
Module 4 U.S. Gupta and G.K
GATE Previous
publishers GATE Year Questions

Page ___ of ____ _______________________________

Signature of HOD
Computer Science
Engineering
Link for Study Material:
Digital Logic:
https://classroom.google.com/c/NjkxNTc5NTMzMDgx/p/NzAxMzcyNDkxMjU3/details
Programming & Data Structures:
https://classroom.google.com/c/NjkxNTc5NTMzMDgx/p/NzAxMjk1MTYxNzE4/details

Computer Organisation & Architecture:

https://classroom.google.com/c/NjkxNTc5NTMzMDgx/p/NzA1MTQzODQ3OTk4/details
Discrete Mathematics:
https://classroom.google.com/c/NjkxNTc5NTMzMDgx/p/NzA1MTQzODY3MzQ1/details

Page ___ of ____ _______________________________

Signature of HOD
SL NO. QUESTION
Why excess 3 code is known as self-complementing
1
code?
2 Find the decimal equivalent for (101101.10101)2
Perform the following conversion: Binary to gray code:
3
Binary: (101011)2.
Perform the following conversion: Decimal (432)10 to
4
BCD code
Perform the following conversion: Decimal (234)10 to
5
Excess 3
6 What is BCD code? Write the full form of EBCDIC.
7 Subtract 10001002 from 10101002 using 2’s Complement method.
8 Find the 2’s complement of 1101001.
9 Perform the BCD addition for (57)10 and (26)10.
10 Find the 9’s & 10’s complement of 6423
11 Convert 62.04 to binary, decimal and hexadecimal
12 Subtract using 1’s complement subtraction: (13)10 - (11)10
13 Subtract using 2’s complement subtraction: (12)10 - (3)10
14 State De-Morgan’s law and verify it with the truth table.
15 Why is Gray code called a unit distance code.
Minimize the expression using k-map method
16
F(A,B,C)= m(1,2,3,5,7)
17 What is prime implicant & essential prime implicant?
Draw the basic block diagram of a 4:1 Multiplexer (with
18
all notations available)
19 Why demultiplexer is also called as a data distributor?
Draw the basic block diagram of a 2 bit magnitude
20
comparator
21 What do you understand by microoperation?
22 Define single precision format with example.
23 Define addressing mode.
24 Differentiate RISC and CISC architecture.
25 The number of bits required to represent 128 different numbers is
Reduce the following expressions using Boolean
1
algebra:(A+B+C) (A+B’+C) (A+B+C’)
Reduce the following expressions using Boolean
2
algebra: XY+XZ+YZ’
Prove the following expressions using Boolean algebra
3
rules/theorem: (A+B) (A+B’) (A’+B) (A’+B’) = 0
Solve using K-map: Y (A,B,C,D) = C’ (A’B’D’+D) +
4
AB’C + D’
. Suppose only one multiplexer and one inverter are allowed to be
5 used to implement any Boolean function of n variables. What is the
minimum size of the multiplexer needed?
6 Let f(w, x, y, z) = ∑ (0, 4, 5, 7, 8, 9, 13, 15).Minimize it.
Consider a Boolean function f(w, x, y, z). Suppose that exactly one of
its inputs is allowed to change at a time. If the function happens to be
true for two input vectors i1 = (w1, x1, y1, z1) and i2 = (w2, x2, y2,
7 z2), we would like the function to remain true as the input changes
from i1 to i2 (i1 and i2 differ in exactly 1 bit position), without
becoming false momentarily. Let f(w, x, y, z) = (5, 7, 11, 12, 13, 15).
Which covers of f will ensure that the required property is satisfied?
Let A = 1111 1010 and B = 0000 1010 be two 8-bit 2’s complement
8
numbers. Their product in 2’s complement is
A 4-bit carry look-ahead adder, which adds two 4-bit numbers, is
designed using AND, OR, NOT, NAND, NOR gates only. Assuming
that all the inputs are available in both complemented and
9
uncomplemented forms and the delay of each gate is one time unit,
what is the overall propagation delay of the adder? Assume that the
carry network has been implemented using two-level AND-OR logic.
A circuit outputs a digit in the form of 4 bits, where 0 is represented
by 0000, 1 by 0001, …, 9 by 1001. A combinational circuit is to be
10 designed which takes these 4 bits as input and output 1 if the digit ≥5,
and 0 otherwise. If only AND, OR and NOT gates are used, what is
the minimum number of gates required?
. Consider a multiplexer with X and Y as data inputs and Z as control
input. Z = 0 selects input X, and Z = 1 selects input Y. What are the
11
connections required to realize the 2-variable Boolean function f = T
+ R, without using any additional hardware?
How many 3-to-8 line decoders with an enable input are needed to
12
construct a 6-to-64 line decoder without using any other logic gates?
How many 32 K × 1 RAM chips are needed to provide a memory
13
capacity of 256 K-bytes?
14 Write short notes on : CLA,ENCODER
15 P is a 16-bit signed integer. The 2’s complement representation of P
is (F87B)16. The 2’s complement representation of 8×P is
What is the minimum number of 2-input NOR gates
required to implement 4-variable function expressed in sum-of-
1
minterms from as f = (0, 2, 5, 7, 8,
10, 13, 15)?
Draw a NAND logic diagram that implements the
2
complement of the following function F(A,B,C,D)= (0,1,2,3,4,8,9,12)
Design a combinational circuit which performs
3 EXCESS-3 code to BCD code conversion using minimum number of
logic gates.
Draw and explain the logic diagram of a half adder
4
using only NOR gates.
Simplify the Boolean function using K-map
5 F (A, B, C, D) =m(4,5,6,7,8)
d (A, B, C, D) = m(11,12,13,14,15)
In a look-ahead carry generator, the carry generate function Gi and
the carry propagate function Pi for inputs Ai and Bi are given by Pi =
Ai ⊕ Bi and Gi = Ai Bi The expressions for the sum bit Si and the
carry bit Ci+1 of the look-ahead carry adder are given by Si = Pi ⊕ Ci
and Ci + 1 = Gi + Pi Ci , where C0 is the input carry. Consider a two-
6
level logic implementation of the look-ahead carry generator. Assume
that all Pi and Gi are available for the carry generator circuit and that
the AND and OR gates can have any number of inputs. The number
of AND gates and OR gates needed to implement the look-ahead
carry generator for a 4-bit adder with S3
If all the flip-flops were reset to 0 at power on, what is the total
number of distinct outputs (states) represented by PQR generated by
7
the counter? . The minimum number of D flip-flops needed to
design a Mod-258 counter is
A RAM chip has a capacity of 1024 words of 8 bits each (1K × 8).
The number of 2 × 4 decoders with enable line needed to construct a
8 16K × 16 RAM from 1K × 8 RAM is? How many 3 × 8 decoders are
needed to construct
4 × 16 decoder?
9 Design a Full Adder circuit using NAND Gate only.
10 Design 4X6 Decoder using 3X8 Decoder
1 Define a binary search tree (BST) and explain its key properties.
Explain the difference between a binary tree and a binary search tree (BST).
2 Provide an example of each.
Discuss the advantages and disadvantages of a singly linked list compared
3 to an array. Provide specific examples for each.
4 Explain the concept of enqueue and dequeue operations in a queue.
#define f(a,b) a+b
#define g(a,b)a*b
main()
{
int m;
m=2*f(3,g(4,5));
printf("\n m is %d", m);
}
5 What is the value of m?
6 How many different types of trees that can be realised are with six nodes?
Consider the following C declaration
struct {
short s [5]
union{
float y;
long z;
}u;
}t;
7 What is the memory requirement for variable t?
Find the maximum number of binary trees that can be formed with three
8 unlabeled nodes.
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an
initially empty binary search tree. The binary search tree uses
the usual ordering on natural numbers. What is the inorder traversal sequence of
the resultant
9 tree?
Find the number of pointers affected for an insertion operation in a doubly
10 linked list.
The function of the given Linked List with the first node as the head is:-
void funx1(struct node* head)
{
if (head == NULL)
return;
funx1 (head -> next) ;
printf (" %d ", head -> data ) ;
11 }
What is the output?
Which algorithms among Insertion Sort, Quick Sort, Heap Sort, and Merge Sort,
can be used to sort a random linked list with minimum time complexity? Explain
12 your answer.
How many stacks are needed to implement a queue? Consider the situation
13 where no other data structure like arrays, linked list is available to you.
Predict the output of:
void main() {
float x=1.1; double y= 1.1;
if(x==y)
printf("I see You");
else
14 printf("I hate You"); }
How many 32K × 1 RAM chips are needed to provide a memory capacity of 256
15 K bytes?
16 Which Data Structure is useful to find Depth First Search on a given graph?
Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that
the weight of the edge (vi, vj) is 2|i−j|. Calculate the weight of a minimum
17 spanning tree of G.
The following sequence of operation is performed on a stack:
PUSH(10), PUSH(20), POP, PUSH(10),
PUSH(20), POP, POP, POP, PUSH(20), POP.
18 Find the sequence of values popped out.
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an
initially empty binary search tree. The binary search tree uses
the usual ordering on natural numbers. Find the inorder traversal sequence of the
resultant
19 tree?
global int i = 100, j = 5;
void P(x) {
int i = 10;
print(x + 10);
i = 200;
j = 20;
print (x);
}
main() {P(i + j);}
20 What will be the values printed by the above program.
What are the advantages of using shared, dynamically linked libraries as opposed
21 to using statically linked libraries?
22 int f(int n)
{
static int i = 1 ;
if (n >= 5) return n;
n = n+i;
i++;
return f(n);
}
What will be the value returned by f(1).
What does the following program print?
#include <stdio.h>
void f (int *p, int * g) {
p = q;
*p = 2;
}
int i = 0, j =1;
int main ( ){
f(&i, & j);
print f ("%d %d ", i, j );
return 0;
23 }
Consider the following recursive C function that takes two
arguments:
unsigned int foo (unsigned int n, unsigned int r) {
if (n>0)
return ((n% r) + foo (n/r, r) ); else
return 0;
}
What is the return value of the function foo when
24 it is called foo(345, 10)?
What is printed by the following C program?
int f(int x, int *py, int **ppz) {
int y, z;
**ppz + = 1; z = **ppz;
*py + = 2; y = *py;
x + = 3;
return x + y + z:
}
void main() {
int c, *b, **a;
c = 4; b = &c; a = &b;
print f("%d", f(c, b, a));
25 }
Let T(n) be the number of different binary
search trees on n distinct elements. Then

Analyze the value of x ?

1
Find the postfix expression for the infix expression
2 A + B * (C + D)/E + F * G.
Postorder traversal of a given binary search tree T
produces the following sequence of keys
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 2. Find the
3 inorder traversal of the tree T?
The following postfix expression with single-digit
operands is evaluated using a stack:
823∧ /23*+51*−
Note that ∧ is the exponentiation operator. Find
the top two elements of the stack after the first *
4 is evaluated.
Analyze the value printed by the following C
program?
#include <stdio.h>
int f(int * a, int n)
{
if (n<= 0)return 0;
else if(*a% 2= = 0)
return * a + f(a
+1,n - 1);
else return * a -
f(a + 1, n - 1);
}
int main( )
{
int a[ ] = {12, 7,
13, 4, 11, 6};
printf("%d",f(a,6));
return 0;
5 }
Analyze the value printed by the following C
program?
# include <stdio.h>
int fun(int n, int * f_p) {
int t, f;
6 if (n <= 1) {
* f_p =1;
return 1;
}
t = fun (n - 1, f_p);
f = t+ * f_p;
* f_p = t;
return f;
}
int main() {
int x = 15;
printf (" % d\ n", fun(5, & x));
return 0;
}
Consider the following C program that attempts
to locate an element x in an array Y[ ] using binary
search. The program is erroneous.
1. f(int Y[10], int x) {
2. int u, j, k;
3. i = 0; j = 9;
4. do {
5. k = (i + j) / 2;
6. if (Y[k] < x) i = k;
else j = k;
7. } while ((Y[k]! = x) &&
(i < j));
8. if (Y [k] == x) print f ("x is in
the array");
9. else print f ("x is not in the
array");
10. }
Analyze where the correction needed in the
7 program to make it work properly.
The preorder traversal of a binary search tree is
15, 10, 12, 11, 20, 18, 16, 19. Evaluate post-order
8 traversal.
9 Write an algorithm to reverse a singly linked list
Write an algorithm to delete an element from a
10 singly linked list if the item available in the list.
Write an algorithm to sort a singly linked list in
descending order. Assume numbers in the list are
11 random.
Suppose a circular queue of capacity (n – 1)
12 elements is implemented with an array of n
elements. Assume that the insertion and deletion
operation are carried out using REAR and FRONT
as array index variables, respectively. Initially,
REAR = FRONT = 0. Write down the algorithm
to detect whether the queue is full and queue
empty.
Write C function takes a simply linked list as input
argument. It modifies the list by moving the last
element to the front of the list and returns the
13 modified list.
Write C function to compute the height of a binary
14 tree rooted at the tree pointer root.
Write C function for enqueue and dequeue
15 operations on queues.
A priority queue is implemented as a max-heap. Initially, it has five elements. The
level-order traversal of the heap is given below:
10, 8, 5, 3, 2. Two new elements `1’ and `7’ are inserted in the heap in that order.
Evaluate the level-order traversal of the heap after the insertion of the elements.
1
The C function takes a simply linked
list as input argument. It modifies the list by
moving the last element to the front of the list
and returns the modified list. Implement the above function.
2
Consider two binary operators ” and `↓’ with the precedence of operator ↓ being
lower than that of the operator . Operator is right associative while
3 operator ↓ is left associative. Evaluate the parse tree for the expression (7↓343↓2).
Consider the following recursive C function that takes two arguments:
unsigned int foo (unsigned int n,
unsigned int r) {
if (n>0) return ((n% r) + foo (n/r, r) );
else return 0;
}
Evaluate the return values of the function foo when it is called foo(345, 10) and
4 foo(513, 2).
Calculate the minimum and maximum number of element comparisons involved in
5 2 way merge sort assuming n is power of 2.
Evaluate how many nodes (apart from s) does the Depth First Search algorithm
discover before discovering t when starting from s.

6
Create an AVL tree by the following elements in Lexicographic order: Jan, Feb,
Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov & Dec. Show balance factors after
7 insertion of each element.
Consider a sequence a of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2.
The following operations are performed on a stack S and a queue Q, both of which
are initially empty.
I: push the elements of a from a0 to a5 in that order into S.
II: enqueue the elements of a from a0 to a5 in that order into Q. III: pop an element
8 from S.
IV: dequeue an element from Q. V: pop an element from S.
VI: dequeue an element from Q.
VII: dequeue an element from Q and push the same element into S. VIII: Repeat
operation VII three times.
IX: pop an element from S. X: pop an element from S.
Show the stack and the queue at each intermediate step.

(a) Consider a binary search tree (BST) containing the following elements: {20, 10,
30, 5, 15, 25, 35}. Draw the BST after inserting all the elements in the given order.
Then, explain the process of finding the minimum and maximum elements in a
BST. (5 marks)

(b) What are AVL trees, and how do they differ from regular binary search trees?
Discuss the rotation operations (left rotation, right rotation, left-right rotation, right-
left rotation) used in AVL trees to maintain balance. Explain how these rotations
help in maintaining the balance property of AVL trees. (5 marks)

9
a) Explain the difference between a min-heap and a max-heap. How are these
structures implemented in an array, and what are the properties that must be
maintained to ensure the integrity of these heaps? (5 marks)

b) A binary min-heap is used to efficiently implement a priority queue. Describe

how the operations of insertion and deletion of the minimum element are
performed in a binary min-heap. Provide the time complexities of these operations.
10 (5 marks)
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
Scanned with CamScanner
1 Explain the ``independent set" of a graph using an example. 4 2 CO4 BL2

2 Explain the ``chromatic number" ( ) of a graph . 4 2 CO4 BL2

3 Explain for a graph using an example. 4 2 CO4 BL2

4 Explain for a graph using an example. 4 2 CO4 BL2

4 5 CO4 BL3
5 Prove that where is the size of the largest independent set.

6 Prove that where represents chromatic polynomial of a graph (Note that denotes a complete 4 5 CO4 BL3
graph with vertices).

7 Prove that where represents chromatic polynomial of the 4 5 CO4 BL3

complete graph with n vertices, i.e., .

8 Prove that the chromatic polynomial of a tree with vertices is . 4 5 CO4 BL3

9 1 2 CO1 BL1
What do you mean by gcd of two numbers?

10 1 2 CO1 BL1
What is the difference between relatively prime numbers and prime numbers?

11 What is the multiplicative inverse of 7 in . 1 2 CO1 BL3

12 1 2 CO1 BL3
List all the primes between 100 and 150.

13 If (mod 5), then (mod 5) 1 2 CO1 BL2

14 1 2 CO1 BL5
If (mod 7), then (mod 7)

15 1 2 CO1 BL1
What do you mean by division algorithm?

16 1 2 CO1 BL3
Express 2940 as product of primes.

17 1 2 CO1 BL2
Prove that square of any odd natural number is of the form 8k+1 .

18 Define Boolean Algebra with example 3 2 CO3 BL1

19 Describe absorption law with example 3 2 CO3 BL2

20 Explain Boolean Function and Expression 3 2 CO3 BL2

21 Describe Idempotent and inverse law with example 3 2 CO3 BL2

22 Analyze briefly the Principle of Duality in Boolean Algebra 3 2 CO3 BL4

5 MARKS QUESTIONS:
1.Solve below:
Out of 200 students 50 take Maths,140 of them take Economics and 24 take both. How many of those not
taken any of the course. 5 CO3,BL3

2.Examine the graphical representation of a bijective function. How can you visually determine if a function is
bijective by looking at its graph? 5 CO5,BL5

3. Interpret that p ↔ q and ¬p ↔ ¬q are logically equivalent 5 CO3, BL3

4. How many reflexive relations are there on a set with n elements? 5 CO1, BL1

5. Demonstrate the basic Boolean identities 5 CO3, Apply

6. Apply Kuratowski's Theorem and its significance in identifying non-planar graphs. How does the theorem
work, and why is it a reliable criterion for determining planarity? 5 CO3, Apply

7. Evaluate x+1=1 using Boolean algebra 5 CO5, Evaluate

8. Evalute the Graph Color Theorem and its connection to planar graphs.

9. How does the theorem relate to coloring the vertices of a planar graph with a minimal number of colors?
5 CO5, Evaluate

10. Evaluate ~(p ∧ q) <-> (p ∨ q) using DNF and CNF 5 CO5, Evaluate
11.Justify (A+B) (A`+C) =AC+AB 5 CO5, Evaluate

12Find the condition for which a 4 digit natural number is divisible by 8. 5 CO5, Evaluate

13. Demonstrate the basic Boolean identities 5 CO3,Apply

14. Prove x+x`y=x+y using Boolean algebra 5 CO3, Apply

15. Explain the ``independent set" of a graph using an example. 5 CO5, Evaluate

10 MARKS QUESTIONS
1. Given A={1,2,3,4}.Consider the following relation on A:
R={(1,1),(2,2),(2,3),(3,2),(4,2),(4,4)}.
a. Verify whether R is reflexive or not?
b. If not find the reflexive closure of R. 10 CO3,Apply

2.A. Write the converse, inverse and contrapositive of the following statements-
1. You will qualify GATE only if you work hard.
2.If you are intelligent, then you will pass the exam
B. Discuss the significance of Cartesian product of two sets with a real life example. 10 CO2,
Understand

3. Determine the nature of propositions: [ (p ˅ q) ˄ ( ¬ p ˄ ¬ q ) ]

Differentiate Commutative law and Associative law 10 CO4, Analyze

Or
Given A={1,2,3,4}.Consider the following relation on A:
R={(1,1),(2,2),(2,3),(3,2),(4,2),(4,4)}.
a. Verify whether R is reflexive or not?
b. If not find the reflexive closure of R. 5 CO3,
Apply

4.A.Show that (p ⋀q) →(p →q) is a tautology

B.Let f∶ R→R be defined by f(x)=2x-3
Show that f is bijective and hence find f^(-1) . 10 CO5, Evaluate

5.A.Analyze briefly the Principle of Duality in Boolean Algebra with example.

B.Consider a set A={a,b,c} and the relation R defined on A by R={(a,a),(a,b),(b,c),(c,c)}.
a. Verify whether R is symmetric or not?
b. If not find the symmetric closure of R. 10 CO4, Analyze

6.A.Evaluate x+1=1 using Boolean algebra

B.Discuss the significance of Cartesian product of two sets with a real life example. 10 CO5,
Evaluate

7.A.Prove that the chromatic polynomial of a tree with 𝑛 vertices is 𝑃(𝐺; 𝑡) = 𝑡(𝑡 − 1)n–1
B.Compute the chromatic polynomial of the following graph: 10 CO5, Evaluate

7.A.Calculate the chromatic polynomial of a cycle with 4 vertices. 10 CO3, Evaluate

B.Find the chromatic number of the following graph:

8.A.For a simple connected graph 𝐺 with 𝑛 vertices, prove that χ(G)= 𝑛 if and only if 𝐺 = 𝐾n
B.For a simple connected graph 𝐺, with at least two vertices, prove that χ(G)=2 if and only if 𝐺 is
bipartite. 10 CO5, Evaluate
9.A. You are given a graph below: Find
the followings:
i. All paths from V1 to V4
ii. All trails from V1 to V4

B. Derive the incident matrix for the following graphs: 10 CO3, Evaluate
10.A.
I. Draw a simple graph having four vertices each of degree 2.
II. Draw a connected graph with 3 vertices and 4 edges.
III. Find the minimum number of connected components of a simple graph with 16 vertices and
10 edges.

B. Draw two graphs which are not isomorphic. Give reasons.

11.A.If a simple regular graph has vertices 𝑛 and 12 edges, find all possible values of 𝑛.
B.Draw a directed graph where the in-degree and out-degree of each vertex are the same.
39. Does the set of elements {0,2,4,6,8} form a field with respect to addition and
multiplication modulo 10?
40. Using Chinese remainder theorem solve the following simultaneous linear congruences
𝑥 ≣ 1(𝑚𝑜𝑑 2)
𝑥 ≣ 2(𝑚𝑜𝑑 3)
𝑥 ≣ 3(𝑚𝑜𝑑 5)
𝑥 ≣ 4(𝑚𝑜𝑑 11)
41. Apply Euclidean Algorithm to find the GCD of 1001 and 1331. Also find the integers 𝑥, 𝑦
such that GCD of 1001 and 1331 can be represented as 1001𝑥 + 1331𝑦
42. 𝐴= {collection of all integers which gives 2 as a remainder when divided by 3}
𝐵= {collection of all integers which gives 3 as a remainder when divided by 5}
𝐶= {collection of all integers which gives 4 as a remainder when divided by 11}.
Then 𝐴 ⋂ 𝐵 ⋂ 𝐶 = {collection of all integers which gives 𝑃 as a remainder when divided by 165}.
Find 𝑃
43.
a. Prove that there are infinitely many primes.
b. If 𝑛 > 1 be a composite integer then there exists a prime 𝑃 such that divides 𝑛 and

𝑃 ≤ √𝑛
44. What do you mean by a countable and uncountable set? Justify with examples.
45. Let X= {1,2,3,4}. Then determine whether or not the relation below is a function from X into X. f=
{(2,3), (1,4), (2,1), (3,2), (4,4)}
46. Let the functions f and g be defined by 𝑓(𝑥) = 2𝑥 + 1 and 𝑔(𝑥) = 𝑥2 − 2
Find the formula defining composition function 𝑓 ● 𝑔
47. Let 𝑓 ∶ ℝ → ℝ be defined by 𝑓(𝑥) = 2𝑥 − 3. Show that f is bijective and hence find 𝑓–1
48. Consider a set A={a,b,c} and the relation R defined on A by R={(a,a),(a,b),(b,c),(c,c)}.
a. Verify whether R is symmetric or not?
b. If not find the symmetric closure of R.
49. Discuss the significance of Cartesian product of two sets with a real-life example. 50.
a. Define equivalence relation.
b. Show that the relation {𝑥𝑅𝑦 ∶ 4|𝑥 − 𝑦, 𝑥, 𝑦 ∊ 𝕫} is an equivalence relation on 𝕫
c. Hence deduce the equivalence class of [0], [1], [2] and [3].
51. Let 𝐴 = {1, 2, 3, 4, … , 9} and let ~ be a relation on 𝐴 × 𝐴 defined by (𝑎, 𝑏) ~ (𝑐, 𝑑) if
𝑎 + 𝑑 = 𝑏 + 𝑐. Then
a. Prove that ~ is an equivalence relation.
b. Find [(2,5)], i.e., the equivalence class of (2,5).
52. Describe Idempotent and inverse law with example
53. Differentiate Commutative law and Associative law