Discrete Structures - Unit Wise Questions

1. Define disjunction and conjunction with suitable examples.

2. Consider a set U = { 1,2,3,4,5,6,7,8,9,10}. What will be the computer representation for set containing the numbers which are multiple of 3 not exceeding 6? Describe injective, surjective and bijective function with examples.

4. Prove that  by using set builder notation. How sets are represented by using bit string? Why it is preferred over unordered representation of sets?

5. How can you relate domain and co-domain of functions with functions in programming language? Discuss composite and inverse of function with suitable examples.

6. Which of the following are posets?

12. Define ceiling and floor function. Why do we need Inclusion - Exclusion principle? Make it clear withsuitable example.

1. Why breaking down of large integer into set of small integers is preferred while performing integer arithmetic? Find sum of numbers 123,684 and 413,456 by representing the numbers as 4-tuple by using reminders modulo of pair-wise relatively prime numbers less than 100.

2. Find the value of x such that x = 1 (mod 3), x = 1 (mod 4),  x = 1 (mod 5) and x = 0 (mod 7) using Chinese remainder theorem.

6. State Euclidean and extended Euclidean theorem. Write down extended Euclidean algorithm and illustrate it with example.

5. Find the value of x such that x = 1 (mod 5) and x = 2 (mod 7) using Chinese remainder theorem.

11. Define zero-one matrix. Explain the types of function.        [1+4]

9. What does primality testing means? Describe how Fermat's Little Theorem tests for a prime number with suitable example.

1. Show that the implication and its contrapositive are logically equivalent.

1. Define the term converse, contropositive and inverse.

2. Which rule of inference is used in the following argument?

If I work all night on this homework, then I can answer all the exercise. IF answer

all the exercise, I will understand all the material. Therefore, if I work all night on

this homework, then I will understand the material.

2. State division and remainder algorithm. Suppose that the domain of the propositional function P(x) consists of the integers 0, 1, 2, 3 and 4. Write out each of following propositions using disjunctions, conjunctions and negations.        [4+6]

    a. ∃x P(x)

    b. ∀x P(x)

    c. ∃x ¬P(x)

    d. ∀x ¬P(x)

    e. ¬∃x P(x)

    f. ¬∀x P(x)

1. What is conjunction? Discuss with suitable example and truth table.

1. What is negation? Discuss with suitable example and truth table.

1. What is compound proposition? Discuss implication with suitable example.

1. Given propositions p and q, define conjunction and disjunction of p and q.

1. What do you mean by proposition? Give example to justify your answer.

1. Given propositions p and q, define conjunction and disjunction of them.

1. Define proposition and its negation with an example.

2. Is the following argument valid? If Socrates is human, then Socrates is mortal Socrates is human.

 ∴ Socrates is mortal.

2. Define existential quantifications with suitable examples.

2. Show that  and  are logically equivalent.

2. How do you define logically equivalent propositions?

2. Is the following argument valid?

Smoking is healthy.

If smoking is healthy, then cigarettes are prescribed by physicians.

∴Cigarettes are prescribed by physicians

2. Is the following argument valid?

If taxes are lowered, then income rises.

2. Which rule of inference is used in the following argument?

Ram is hard working. If Ram is hard working, then he is intelligent. Therefore Ram is intelligent.

2. Discuss universal quantifier with example.

2. Show that (p∧q ) → p  is a tautology by using truth table.

3. What is valid argument?

3. State the rules for the strong form of mathematical induction with propositions.

3. Define universal instantiation.

3. State which rule of inference is basis of the following argument: “It is below freezing and raining now, therefore, it is below freezing now.”

3. State which rule of inference is the basis of the following argument; “It is below freezing now. Therefore, it is either below freezing or raining now.”

3. Give examples of addition rule and simplification rule of inference.

6. Prove that if n is positive integer, then n is odd if and only if 5n+6 is odd.            [5]

7. Define proposition. Consider the argument "John, a student in this class knows how to write program in C. Everyone who knows how to write program in C can get a high paying job. Therefore, someone in this class can get high paying job." Now, explain which rules of inferences are used for each step.        [1+4]

8. Represent the argument “If it does not rain or if is not foggy then the sailing race will be held and the lifesaving demonstration will go on. If sailing race is held then trophy will be awarded. The trophy was not awarded. Therefore it not rained” in propositional logic and prove the conclusion by using rules of inferences.

9. Discuss common mistakes in proof briefly. Show that n is even if n³+5 is odd by using indirect proof.

5. All over smart people are stupid. Children of stupid people are naughty. John is a children of Jane. Jane is over smart. Represent these statements in FOPL and prove that John is naughty.

7. Let A = "Aldo is Italian" and B = "Bob is English". Formalize the following sentences in proposition.

a. Aldo isn't Italian.

b. Aldo is Italian while Bob is English.

c. If Aldo is Italian then Bob Bob is not English.

d. Aldo is Italian or if Aldo isn't Italian then Bob is English.

e. Either Aldo is Italian and Bob is English, or neither Aldo is Italian nor Bob is English.

11. What is logical equivalence? Show that p→q  and ¬q → ¬q are logically equivalent.

OR

Discuss Modus Ponens with suitable example.

11. Express the statement " Everyone has exactly one best friend " as a logical expression involving predicates, quantifiers with a domain consisiting of all people and logical connectives.

11. Explain the 4 rules of inference for quantified statements.

11. Explain the rules of inference for quantified statements.

11. Explain the 2 rules of inference for quantified statements and give suitable examples.

OR

Show that the propositions pV( p ᴧ r ) and ( rV q) ᴧ ( p V r) are logically equivalent.

11. Differentiate between existential and universal quantifiers with suitable examples.

14. Explain the rules of inference for quantified statements.

12. Prove that the product xy is odd if and only if both x and y are odd integers .

16. Discuss direct =, indirect and vacuous proof with suitable example.

16. Discuss direct proof, indirect proof, and proof by contradiction with suitable example.

16. Construct truth tables to determine whether the given statement is a tautology a contingency or an absurdity.

a) p ⇒ (q ⇒p)

b) q ⇒ (q ⇒p)

c) p ∧ ~ p

OR

Explain the method of proving theorems by direct indirect, controdiction and by cases.

16. Discuss the different rules of inference for quantified statements along with suitable example of each.

16. Explain Tautologies, contradiction and contingencies with suitable examples.

OR

Explain the method of proving theorems by direct, indirect, contradiction and by cases.

16. Discuss the techniques of proofs by contradiction and by cases with suitable examples.

16. Discuss the techniques of direct proof indirect proof and vacuous proof for proving implications with suitable examples.

18. Construct truth tables to determine whether the given statement is a tautology, a contingency, or an absurdity:

a) p ⇒ (q ⇒p)

b) q ⇒ (q ⇒p)

c) p ∧ ~ p

1. Prove that for all integers x and y, if x²+y² is even then x+y is even. Using induction prove that 1³+2³+..........+n³ = n²(n+1)²/4.    [5+5]

3. State the rule for the strong form of mathematical induction with prepositions.

3. Use mathematical induction to prove that 4ⁿ- 1 is divisible by 3.

3.  Compute the following values.

a. 3 mod 4          b. 7 mod 5           c. -5 mod 3           d. 11 mod 5          e. -8  mod 6

Write down the recursive algorithm to find the value of bⁿ and prove its correctness using induction. 

4. Prove that for every positive integer n ≥ 1, n²+n is even integer using mathematical induction.

10. How mathematical induction differs from strong induction? Prove that 1²+2²+3²+........+n² = n(n+1)(2n+1)/6 by using strong induction.

6. Prove that 5ⁿ-1 is divisible by 4 using mathematical induction.

11. Write down recursive algorithm for computing aⁿ. Argue that your algorithm is correct by using induction.

12.  Represent any three set operations using Venn diagram. Give a recursive defined function to find the factorial of any given positive integer.        [3+2]

11. Use mathematical induction to prove that the sum of the first n odd positive integers is n²?

OR

Discuss Modus Ponens with suitable example.

12. Find an explicit formula for the Fibonacci numbers, with recursion relation f_n−1 + f_n−2 and f₀ = 0 , f₁ = 1

12. For the Fibonacci sequence, prove that for n ≥ 2.

f²_n+1 − fn² =  f_n−1 f_n−2

13. Find an explicit formula for the Fibonacci sequence defined by

f_n = f_n−1 + f_n−2 ,  f₁ = f₂ = 1

13. Define explicit formula for the sequence: {a1, a2, a3,....}. Write an explicit formula for the sequence 2, 5, 7, 12, 19, 31.

16. What is mathematical induction? Use mathematical induction to prove that1.1! + 2.2! + ... + n.n! = (n+1)! – 1, wherever n is a positive integer.

17. Find all the solutions of the recurrence relation a_n  = 4a_{n −1}+n² . Also find the solution of the relation with initial condition  a₁ =1.

2. Define linear homogeneous recurrence relation. Solve the recurrence relation a_n=a_n/2+n+1, with a₁=1.Also discuss about probabilistic primility testing with example.

3. Use binomial coefficient in the expansion of (x + y)⁴.

1. State pigeonhole principle. Solve the recurrence relation a_n = 3a_n-1 -  3a_n-2 + a_n-3 with initial conditions a₀=1 ,a₁ = 3, a₂=7.

3. What is the coefficient of x¹² y¹³ in the expansion of (2x – 3y)²⁵ ?

4. Determine whether the sequence {an} is solution of the recurrence relation a_n =2a_n−1 − a_n−2 where a_n = 3n.

4. What is the coefficient of x⁷ in (1+x)¹¹? Describe how relation can be represented using matrix.    [2+3]

4. How many different license plates is available if each plate contains sequence of three letters followed by three digits?

4. Is the sequence {an} a solution of the recurrence relation a_n = -3a_n-1 + 4a_n-2 if a_n = 2n?

4. State and prove “the pigeonhole principle”.

4. State and prove “the extended pigeonhole principle”.

4. State the Pigeonhole principle. How many students must be in class to guarantee that at least two students receive the same score on the final exam is graded on a scale from 0 to 100?

4. State and prove the Pigeonhole principle.

4. State and prove the Pigeonhole principle.

4. State and prove " the extended pigeonhole principle".

5. Define linear nonhomogeneous recurrence relation of degree k with coefficients.

4. In how many ways we can draw a heart or a diamond from an ordinary deck of playing cards?

5. Develop a “general explicit formula” for a nonhomogeneous recurrence relation of the form: a_n = rq_n-1 +s, where s and r are constants.

5. Solve the recurrence relation a_n = 5n_n-1 - 6n_n-2 with initial conditions a₀ =1, a₁ = 4.                [5]

5. Define linear homogeneous recurrence relation.

5. Let {an} be a sequence that satisfies the recursion relation a_n = a_n-1 - a_n-2 for n≥2 and suppose that a₀ = 3 and a₁=5. Find the values a₂ and a₃.

5. How many ways are there to select a first, second and third – prize winners from 10 different people?

5. Define linear homogeneous recurrence relation of degree k with constant coefficients.

5. How many students must be in a class to guarantee that at least two students receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points?

5. What is pigeonhole principle?

6. Define linear homogeneous recurrence relation.

7. State and prove generalized pigeonhole principle? How many cards should be selected from a deck of 52 cards to guarantee at least three cards of same suit?

4. Solve the recurrence relation a_n = 5a_n-1 - 6a_n-2 with initial conditions a₀ = 1 and a₁ = 2.

8. Show that if there are 30 students in a class, then at least two have same names that begin with the same letter. Explain the Pascal's triangle.        [2.5+2.5]

11. State and prove pigeonhole principle. What is the minimum number of student required in a discrete mathematics class to be sure that at least six receive the same grade, if there are five possible grades A, B, C, D, and F?

11. How many bit strings of length eight either start with a 1 bit or end with two bits 00?

12. Discuss the importance of recurrence relation in the analysis pf divide – and – conquer algorithms.

12. Find the solution of the recursion relation a_n = a_n-1 + 2_an-2 with a₀ = 2 and a₁=7?

OR

Find an explicit formula for the Fibonacci numbers.

12. Discuss the principles of inclusion-exclusion. How many bit strings of length eight either start with a 1 bit or end with two bits 00?

12. What is binomial theorem? Use this theorem to find the coefficient of x¹² y¹³ in the expansion of(2x – 3y)²⁵.

12. Discuss the importance of recurrence relations in the analysis of divide-and-conquer algorithms.

9. How many 3 digits numbers can be formed from the digits 1,2,3,4 and 5 assuming that:

a. Repetitions of digits are allowed

b. Repetitions of digits are not allowed 

12. Define the binomial coefficient and give the general term of the binomial coefficient. Show that the sum of the binomial coefficient is 2ⁿ.

10. List any two applications of conditional probability. You have 9 families you would like to invite to a wedding. Unfortunately, you can only invite 6 families. How many different sets of invitations could you write?

17. Find the solution to the recurrence relation an = 6a_n−1 − 11a_n−2 + 6a_n−3 with the initial conditions a₀ = 2, a₁ = 5, and a₂ = 15.

OR

Find the explicit formula for the Fibonacci numbers. Use f_n = f_n−1 + f_n−2 as recursive condition and f₀ = 0 and f₁ = 1 as initial condition.

17. Define linear homogenous recurssion relation of degree k with constant coefficient with suitable examples. What is the solution of recurrence relation a_n = 6 a_n-1 - 9 a_n-2 with a₀ = 1 and a₁ = 6?

17. Define linear homogeneous recursion relation of degree K with constant coefficient with suitable examples. What

is the solution of the recurrence relation a_n = a_n−1 + 2_an−2 with a₀ = 2 and a₁ = 7?

17. Describe linear homogeneous and linear non-homogeneous recurrence relations with suitable examples.

17. Find the solution to the recursion relationan = 6a_n-1 – 11a_n-2 + 6a_n-3 with initial conditions a₀ = 2, a₁ = 5 and a₂ = 15.

OR

Suppose that a person deposits Rs.10,000/- in a fixed account at a bank yielding 11% per year with interest

compounded annually. How much will be in the account after 10 years? Solve the problem with modeling it into

recursion relations.

17. Solve the recurrence relation an = 2a_n-1 + 2a_n-2 + 2a_n-3 for n ≥ 3, a₀ = 3, a₁ = 6 and a₂ = 9.

OR

Find the explicit formula for the Fibonacci numbers. Use f_n = f_n-1 + f_n-2 as recursive condition and

f₀ = 0 and f₁ = 1 as initial condition.

18. Find the recurrence relation to find the number of moves needed to solve the TOH (Tower of Hanoi) problem with n disks. Discuss application of recurrence relation in divide-and-conquer algorithms.

3. How Zero-one matrix and diagraphs can be used to represent a relation? Explain the process of identifying whether the graph is reflexive, symmetric, or anti-symmetric by using matrix or diagraph with suitable example.

1. What is S-D cut? For the following network flow find the maximal flow from S to D.

3. List the necessary conditions for the graphs to be isomorphic with an example. Find the maximal flow from the node SOURCE to SINL in the following network flow.        [5+5]

3. Define Eular circuit with suitable example. Find the maximal flow s to t from the given network flow. 

6. Define cut vertices and cut edges.

6. Show that an undirected graph has an even number of vertices of odd degree.

6. Distinguish between binary tree and spanning tree with suitable examples.

8. What is bipartite graph?

7. What is minimum spanning tree?

7. Consider K_n, the complete graph on n vertices. What is the degree of each vertex?

7. Distinguish between multi graph and pseudo graph with suitable examples.

7. Suppose that a planar simple graph has 20 vertices, each of degree 3. Into how many region does a representation of this planar graph split the plane?

8. How many edges are there in graph with 10 vertices each of degree six?

8. Define the complete graph K_n on n vertices and the complete bipartile graph K_m,n with suitable examples.

8. Distinguish between multigraph and pseudograph with suitable examples. 

9. What is decision tree?

8. Define saturated edge in a transport network.

8. Verify the Handshaking theorem in the figure.

8. What is minimal cut?

8. What is chromatic number of a graph?

9. Which of the undirected graphs in the following figure have an Euler circuit? Explain.

9. Distinguish between undirected and directed graphs with illustrations.

9. What is spanning tree?

10.Define saturated and unsaturated edge?

9. Is the graph K4 planar? How?

9. Which of the undirected graphs in the following have an Euler path?

9. Illustrate the Dijkstra's Algorithm to find the shortest path from source node to destination node with an example.        [5]

10. What is regular graph ?

10. What are the significances of Minimal Spanning Tree? Describe how Kruskal's algorithm can be used to find the MST.        [2+3]

10. What is the chromatic number of the complete bipartile graph K_m,n , where m and n are positive integers?

10. Determine the chromatic number K_n.

10. Determine the chromatic number K_n.

10. What is the chromatic number of the complete bipartite graph, where m and n are positive integers?

10. State max-flow min-cut theorem.

7. Define reflexive closure and symmetric closure. Find the remainder when 4x² - x + 3  is divided by x + 2 using remainder theorem.

8. Define Eular path and Hamilton path with examples. Draw the Hasse diagram for the divisible relation on the set { 1, 2, 5, 8, 16, 32} and find the maximal, minimal, greatest and least element if exist.

8. Define Eular path and Hamilton path. Give examples of both Eular and Hamilton path.

12. What is meant by chromatic number? How can you use graph coloring to schedule exams? Justify by using 10 subjects assuming that the pairs {(1,2), (1,5), (1,8), (2,4), (2,9), (2,7), (3,6), (3,7), (3,10), (4,8), (4,3), (4,10), (5,6), (5,7)} of subjects have common students.

13. What is graph isomorphism? What are the different invariants of graph isomorphism?

14. What is planar graph? Show that K_3,3 is non-planar.

10. What is minimum spannung tree? Explain Kruskal's algorithm for finding minimum spanning tree.

13. Show that K3,3 is not planar?

14. Discuss adjacency matrix representation of graph with example.

15. Prove that “a tree with n vertices has n-1 edges”.

14. Show that a tree with n vertices has n-1 edges.

11. List any two applications of graph coloring theorem. Prove that "A tree with n vertices has n-1 edges"

14. When does the two simple graphs G₁ = m(V₁, E₁) and G₂(V₂, E₂) are isomorphic. Show that the graph G = (V, E) and H = (W, F) displayed in the following figure are isomorphic.

14. Show that the graphs in the following figure are not isomorphic.

What can you say about the complexity of graph isomorphism algorithms in terms of complexity?

14. Discuss adjacency matrix representation of a graph with suitable example.

14. Prove that an undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

14. Determine whether the graphs shown in the following figure are isomorphic.

What can you say about the graph isomorphism algorithms in terms of efficiency?

11. Define spanning tree and minimum spanning tree. Mention the conditions for two graphs for being isomorphic with an example.

15. Prove that an undirected graph is a tree if there is a unique simple path between any two of its vertices.

15. Find a spanning tree of the simple graph in the following graph, if it exists.

Can there be more possibilities?

15. Prove that “a simple graph is connected if and only if it has a spanning tree”.

15. Define isomorphism. Given an example to show that the graphs are not isomorphic.

15. Show that the maximum number of vertices in a binary tree of height n is 2ⁿ⁺¹ − 1.

OR

Draw all possible unordered trees on the set {a, b, c}.

15. Prove that a tree with n-vertices has n-1 edges.

15. Define rooted tree. Show that a full m-ary tree with i internal vertices contains n = mi + 1 vertices.

17. What is shortest path problem? Find the length of a shortest path between a and z in the given weighted

graph.

18. Find a maximum flow in the network shown in figure

18. Find the maximum flow in the network shown in the figure.

19. Describe Dijkstra’s algorithm for finding the shortest path in a weighted graph between two vertices with suitable example.

18. Discuss the algorithm for constructing Euler circuit with suitable example.

19. Discuss Kruskal’s algorithm for constructing a minimum spanning tree. Use this algorithm to find minimum spanning tree in the graph given below.

19. An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

19. A phrase structure grammar g is defined to be a 4-tuple (V, S, v₀ |→ ), where V=(v_o, w, a, b, c}, S={a, b, c}, v_o |→ aw, w |→ bbw, w |→ c. Derive a sentence of L(G), the language of this grammar.

OR

Prove that an undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

19. Prove that a symmetric connected relation has a undirected spanning tree.

OR

Give a simple condition on the weights of a graph that will guarantee that there is a unique maximal spanning tree for the graph.

19. Define an Euler circuit and Euler path in an undirected graph. How can it be determined whether an undirected graph has an Euler circuit and an Euler path? Explain with suitable example.

20. Find all S-D cuts in the following transport network. What is the value of a maximal flow?

19. Explain the concept of network flows and max-flow min-cut theorem with suitable examples.

OR

Define Euler circuit and Euler path with suitable examples. Give the multi-graph model of the two of Koenigsberg state a necessary and sufficient condition for Euler circuit in connection to your definitions and models.

19. State and prove the Max-flow and Min-cut theorem.

OR

Find a maximum flow for the network in the figure below.

19. Explain the concept of network flows and max-flow min-cut theorem with suitable examples.

19. What do you mean by spanning tree? Find a spanning tree of the simple graph G shown in figure.

A graph is connected if and only if it has a spanning tree.

OR

Prove that an undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

20. Explain the concept of network flows and max-flow min-cut theorem with suitable examples.

20. Define Euler and Hamiltonian circuits and paths with examples illustrating the existence and nonexistence of them.

OR

Discuss the shortest path algorithm of Dijkstra for finding the shortest path between two vertices. Use this algorithm to find the length of the shortest path between a and z in the following weighted graph?

Give the idea of travelling salesman problem and the difficulties of solving it.

20. State and prove Max-Flow Min-Cut theorem.

20. Define maximal flow and minimal cut and state and prove min-cut max-flow theorem.

OR

Find a maximal flow for the network shown in the figure below:

20. Explain the concept of network flows and Max-flow Min-cut theorem with suitable examples.

OR

Find a maximum flow in the network shown in the figure.

20. Discuss the Algorithm of Dijkstra for finding the shortest path in a weighted graph between two vertices with suitable example. Moreover, explain the travelling salesman problem and the efficiency of algorithm for solving this problem.

20. Find a maximal flow for the network shown in the figure below:

20. Use Fleury’s algorithm to construct an Euler circuit for the following graph.

OR

Explain the concept of network flows and max-flow min- cut with suitable examples.

20. Define Hamiltonian paths and circuits with suitable examples for the existence and nonexistence. Show that has a Hamilton circuit whenever .

OR

Write the shortest path algorithm of Dijkstra for finding the shortest path between two vertices. What is the length of shortest path between a and z in the weighted graph in the following figure?

Apply the stated algorithm for finding the solution.

5. Define the terms a language over a vocabulary and the phrase – structure grammar.

6. What is context free grammar?