From a group of 7 men and 6 women, five persons are to be selected to form a committee so that at least 3 men are there on the committee. In how many ways can it be done?

Suppose repetitions are permitted: i) How many ways three-digit no. can be formed from six digits 2,3,4,5,7 and 9? ii) How many are multiple of 10? iii) How many are even?

What is the coefficient of x09 in the expansion of (2–x)19?

Five pencils and 5 pens are to be arranged in a row. In how many ways they can be arranged if i) All pencils must be arranged together ii) No two pencils should be kept together and iii) One pen and one pencil must be arranged together?

Find the number of permutations that can be made out of the letters i) Mississippi ii) Assassination

How many automobile license plates can be made if each plate contains two different letters followed by three different digits. Solve the problem if the first digit can not be zero.

Find the shortest path between a - z for the given graph using Dijkstra’s algorithm

Explain the terms adjacency matrix and incidence matrix.

Define the following terms with suitable example. i) Factor of graph ii) Weighted Graph iii) Bipartite graph

Draw all isomorphic graphs on vertices 2 and 3, also draw all non-iso-morphic graphs on 2,3 and 4 vertices.

Explain Edge connectivity and Vertex Connectivity with suitable example.

Is it possible to construct a graph with 12 nodes such that 2 of the nodes have degree 3 and the remaining have degree 4.

Construct a binary tree from given inorder and preorder traversals: Inorder : b d f h k m p t v m Preorder : b f d k h v w t m

Define following terms i) Forest ii) Fundamental cutsets iii) Game tree

Use Kruskal’s algorithm to find the minimum spanning tree for the connected weighted graph G as shown in fig. below

Find maximum flow in the transport network using labeling procedure. Determine the corresponding min-cut.

Construct an optimal binary tree for the set of weights as {8,9,10,11,13,15,22}. Find the weight of an optimal tree. Also assign the prefix codes and write the code words.

What is Minimum Spanning tree? Explain briefly steps involved in finding MST in Prim’s Algorithm?

Define with examples: i) Groupoid ii) Semigroup iii) Monoid iv) Abelian group. v) Subgroup

Let (A,x) be monoid such that for every x∈A, x * x = e wheree is the identity element. Show that (A,*) is an abelian group.

Define with examples: i) Properties of binary operation ii) Ring with unity iii) Fields. iv) Integral Domain

Find the number of codes generated by the given check matric H. Also find all code words.

From a group of 7 men and 6 women, five persons are to be selected to from a committee so that at least 3 men are there on the committee. In how many ways can it be done?

How many 3-digit numbers can be formed from the digits 2,3,5,6,7 and 9, which are divisible by 5 and none of the digits is repeated?

How many 6-digit odd numbers greater than 6,00,000 can be formed from the digits 5,6,7,8,9, and 0 i) If repetition is allowed. ii) If repitition is not allowed

In how many different ways can the letters of the word ‘OPTICAL’ be arranged so that the vowels always come together

If a committee has eight members. i) How many way can the committee members be seated in a row? ii) How many way can the committee select a president, vice-precident and secretary

In a certain country, the car number plate is formed by 4 digits from the digits 1,2,3,4,5,6,7,8 and 9 followed by 3 letters from the alphabet. How many number plates can be formed if neither the digits nor the letters are repeated?

Show that the following graphs are isomorphic

List and explain the necessary and sufficient conditions for Hamiltonian and eulerian path with suitable examples.

Define the graph Kn and Kmn

Use dijkstras algorithm to find the shortes path between A and Z in figure.

Draw a complete bipartite graph on 2 and 4 vertices K2,4 and 2 and 3 vertices K2,3.

Under What condition Km,n will have eulerian circuit

Define following terms i) Level of a tree ii) Height of a tree iii) Fundamental circuit

Use labeling procedure to find a maximum flow in the transport network given in the following figure. Determine the corresponding minimum cut.

Construct Minimal spanning tree for the following graphs using prims algorithm

Define following terms i) Forest ii) Fundamental cutsets iii) Game tree

Construct Minimal spanning tree of the following graphs using kruskals algorithm

Construct an optimal tree for 10,11,14,21,16,18 using Huffman conding

Define: i) Cyclic group ii) Abelian group iii) Cosets

Let {0,1,2,....n-1} Zn. Constract the multiplication table for n=6. Is (Zn,*) an abelian group. Where* is a binary operation on Zn such that a*b = remainder of a*b divided by n

Let (A,*) be a group, show that (A,*) is an abelian group iff a2 * b2 = (a*b)2

Define: i) Group codes ii) Subgroup iii) Integral domain

Let (A,*) be an algebraic system where * is a binary operation such that for any a,b, belongs to A, a*b=a i) Show that * is an associated operation ii) Can * ever be a communtative operation?

Prove that the set Z of all integers with binary operation * defined by a* b = a+b+1 such that for all a,b belonging to Z is an abelian group

The company has 10 members on its board of directors. In how many ways can they elect a president, a vice president, a secretary and treasure.

Find eighth term in the expansion of (x+y)13

A box contains 6 white and 5 black balls. Find number of ways 4 balls can be drawn from the box if i) Two must be white ii) All of them must have same colour

In how many ways can word the ‘HOLIDAY’ be arranged such that the letter I will always come to left of letter L.

In how many ways can one distribute 10 apples among 4 children

Use Binomial theorem to expand (X4+2)3

Is it possible to draw a simple graph with 4 vertices and 7 edges. Justify?

Define following terms with example. i) Complete graph ii) Regular graph iii) Bipartite graph iv) Complete bipartitie graph v) Paths and circuits

The graphs G and H with vertex sets V(G) and V(H), are drawn below. Determine whether or not G and H drawn below are isomorphic. If they are isomorphic, give a function g: V(G)-> V(H) that defines the isomorphism. If they are not explain why they are not.

Determine which if the graph below represents Eulerian circuit, Eulerian path, Hamiltonian circuit and Hamiltonian Path. Justify your answer

A connected planar graph has nine vertices with degree 2,2,2,3,3,3,4,4,5 Find i) number of edges ii) number of faces iii) construct two such graphs

Explain the following statement with example “Every graph with chromatic number 2 is bipartite graph”

Construct Huffman tree. A 5 B 6 C 6 D 11 E 20

Explain i) Cutset ii) Tree properties iii) Prefix code

Give the stepwise construction of minimum spanning tree using Prims algorithm for the following graph. Obtain the total cost of minimum spanning tree.

Using the labelling procedure to find maximum flow in the transport network in the following figure. Determine the corresponding minimum cut.

Define with example. i) Level and height of a tree. ii) Binary search tree. iii) Spanning tree

Construct binary search tree by inserting integers in order 50,15,62,5,20,58,91,3,8,37,60,24 Find i) No of internal nodes ii) leaf nodes

Let R = {0,60,120,180,240,300} and* binary operation so that for a and b in R, a*b is overall angular rotation corresponding to successive rotations by a and by b. show that (R,*) is a group.

Following is the incomplete operation table of 4-element group. Complete the last two rows. * e a b c e e a b c a a b c e b c

Explain Algebraic system and properties of binary operations.

Explain the following terms with examples i) Ring with unity ii) Integral domain iii) Field

Consider the set Q of rational numbers and let a*b be the operation defined by a*b=a+b-ab i) Find 3*4 ii) 2*(-5), iii) 7*(1/2) Is (Q,*)a semigroup? Is it commutative?

Show that (Zn) is Abelian group

How many bit strings of length 8 bits can be constructed which will either start with ‘1’ or end with ‘00’?

In how many ways can 6 Boys and 2 Girls be seating in a row such that i) 2 Girls are seating together ii) 2 Girls are not seating together.

How many bit strings can be formed of length 10 bits which contains? i) at least four 1’s ii) at most four 1’s?

How many bit strings of length 10 can be formed which will contain either 5 consecutive 0s or 5 consecutive 1s?

A zip code contains 6 digits. How many different zip codes can be made with the digits 0-9 if. i) No digit is used more than once. ii) The first digit is not ‘0’

Use the Binomial theorem to expand (3a-2b)6

Find shortest path from vertex ‘0’ to vertex ‘4’ using Dijkstra’s algorithm.

Explain with example: i) Bipartite Graph ii) Connected Graphs

What is Graph isomorphism? Which of the following graphs are isomorphic? Justify your answer.

Find shortest path from vertex ‘O’ to Vertex ‘T’ using Dijkstra’s algorithm.

Explain with suitable example: i) Euler path & Euler circuit ii) Hamilton path & Hamilton circuit.

What is planar Graph? A simple planar graph G contains 20 vertices and degree of each vertex is 3. Determine the number of regions in planar graph G?

For the following graph find different cut set and identify the max flow in given network?

Find the optimal prefix code for the given characters with the frequency of occurrences as below. Character Frequency A 10 E 15 I 12 O 3 U 4 S 13 T 1

Find minimum Spanning tree using prims algorithm.

Construct Binary search Tree: 21, 28, 14,18,11, 32, 25, 23, 37, 27, 5, 15, 19, 30, 12, 26

For the following transport network find the maximum flow using max flow min cut theorem.

Find minimum spanning tree using Kruskals Algorithm.

Let Z4={0,1,2,3} and ‘R’ be the relation under operation ‘+’ defined as a+b=a+b : if (a+b)<4 a+b=a+b–4 : if (a+b)≤4 Where a,b ∈ Z4 Determine Algebraic System (Z4,+) is abellian group or not?

Explain: i) Integral domain ii) Field

Let A={0,1,2,3} and ‘R’ be the relation under operation ‘’ defined as a b=a,b%4. Determine algebraic system (A, ) is monoid or not?

Let Zn={0,1,2,3,...n-1} Consider ‘R’ relation under operation ‘+’ defined as “addition Modulo 5” and operation ‘*’ defined as “ multiplication modulo 5”. Does the Algebraic system. (Z5,+,*) forms Ring”?

Explain the following properties of Algebraic structure with example i) Identity ii) Inverse

Consider ‘R’ be the relation under binary operation ‘*’ on a set Z. Does the algebraic system (Z,*) is Abelian Group?

Let U = {1, 2, 3, ........., 10}, A = {2, 4, 6, 8, 10}, B = {1, 3, 5, 7, 9, 10} Find: i) (A  B)' ii) (A  B)' iii) (B)' iv) (B–A)'

Let p be “Mark is Rich” and q be “Mark is happy” write each of following in symbolic form i) Mark is poor but happy ii) Mark is neither rich nor happy iii) Mark is either rich or happy iv) Mark is Rich and not happy

Explain terms Tautology and Contradiction in truth table with an example.

By using mathematical induction show that 1+2+3+.....+n = n(n+1)/2 for all natural number values of n.

Explain following terms with example. i) Symmetric difference between set ii) Union of set iii) Intersection of Set iv) Subset of a Set

A college Records gives following information : 119 students enrolled in Introductory computer science, 96 of them took data structures, 53 took foundations, 39 took assembly language, 31 took both foundation and Assembly language, 32 took both data structures and Assembly language, 38 took data structures and foundations and 22 took all of three courses is this information correct? Why?

What is Equivalence relation? Explain properties of binary relations.

Let A={1,2,3,4} and R={(1, 2), (2, 4), (1, 3), (3, 2)}, Find transitive closure of relation R using Warshall’s algorithm.

Let A = {1, 2, 3, 4, 12}=B, and let aRb if a divides b, Write a relation and draw it’s Hasse diagram.

Let f(x)=2x+3, g(x)=3x+4, h(x)=4x find gof, fog, foh, goh

A = {1, 2, 3, 4, 5, 6} = B R = {(i, j) ||i – j| = 2} Find whether R is equivalence relation or not

Find whether above posets are lattices or no?

Let A ={1, 2, 3} and B = {1, 2, 3, 4, 5}. Find i) P(A U B) ii) P(A  B) iii) A – B

By using mathematical induction prove that Sn = 1 + 3 + ... + (2n–1) = n2; for all integers n > 1

Let P : I will study hard and Q: I will get admission in IIT. Statement: If I study hard then I will get admission in IIT. Write the Converse, Inverse & Contrapositive of the above statement.

Suppose 100 Computer Engineering students studies at least one of the following language C, C++ and Python. It is given that 65 students studies C language, 45 studies C++ language and 42 studies Python language. 20 students studies C and C++ language, 25 student studies C and Python language, 15 students studies C++ and Python language. Find students studying : i) Only C and C++ language, not Python language ii) Only C and Python language, not C++ language

Use mathematical induction to prove Sn = 2 + 4 + 6 + 8 + ... + 2n = n(n + 1) for all positive integer n.

What is Logical Equivalence? Show that ~(q  p)  (p  q)  q

Let A = ( 0, 2, 4, 6, 8, 10 } and Relation aRb defined on set A as aRb = {(a,b) | (a–b) % 2 == 0 ; a,b  A}. Find aRb is Equivalence Relation or not?

Write the relation pairs and Draw the Hasse Diagram for the Relation defined on set ‘X’ as aRb = {(a, b) | a divides b ; a,b  X }; where X = { 10, 20, 30, 40, 50, 60, 80, 100 }.

If f(x) = 2x + 5 and g(x) = 5x + 2 find i) fog (5) ii) fog (2) + gof(2)

If X = {10,20,30,40,50} & Relation on set ‘X’ is represented as aRb = { (a, b) | a divides b; a,b  X }. Find a relation aRb is Partial Order Relation or not?

Let A = { 1, 2, 4, 8, 16, 24, 32, 48 }. A relation on set ‘A’ is defined as aRb = { (a, b) || a divides b; a,b  A}. i) Write Relation aRb ii) Write any two Chain of aRb on set ‘A’ iii) Write any two Anti Chain of aRb on set ‘A’

If f(x) = 16x2 + 12. Find Inverse of f(x). Is the inverse of f(x) is function? Justify.

By using mathematical induction show that 1+4+7+...+(3n-2)=n(3n-1)/2 for all natural number values of n.

Explain following terms with example. i) Symmetric difference between set ii) Union of set iii) Intersection of set iv) Subset of a set v) Power of the set

In the survey of 60 people, it was found that 25 read Newsweek magazine, 26 read time, 26 read Fortune. Also 9 read both Newsweek and Fortune, 11 read both Newsweek and Time, 8 read both Time and Fortune and 8 read no magazine at all. i) Find out the total number of people who read all the three magazines ii) Fill in the correct number in all the regions of the Venn diagram iii) Determine the number of people who read exactly one magazine

Express the contrapositive, converse and inverse form of conditional statement given below: “If x is rational, then x is real”

Let p be “Mark is Rich” and q be “Mark is happy” write each of following in symbolic form i) Mark is poor but happy ii) Mark is neither rich nor happy iii) Mark is either rich or happy iv) Mark is Rich and not happy

Explain terms Tautology and Contradiction in truth table with an example

Let f(x)=x+2, g(x)=x-2, h(x)=3x find gof, fog, fof, gog, foh.

For each of these relations on Set A={1,2,3,4} decide whether it is reflexive, symmetric, transitive or anti-symmetric (one relation may satisfy more than one properties) R1={(1,1), (2,2), (3,3), (4,4)} R2={(1,1), (1,2), (2,2), (2,1), (3,3), (4,4)} R3={(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)}

Draw a hasse diagram for (S, ) where S={1,2,3,4,5,6}  is defined as a  b if a divides b, i.e. b is an integer multiple of a.

Let A={1,2,3,4) and R={(1,2),(2,1),(2,3),(3,4)} Find transitive closure of relation R using Warshall’s algorithm.

What is Equivalence relation? Explain properties of binary relations.

Explain the various types of functions.