Discrete Structure Important Questions

DISCRETE STRUCTURE IMPORTANT QUESTIONS FOR EXAMS:

Chapter 1: Basic Discrete Structure [5/10 marks]

Topics to get covered: 
- Set operations
- Inclusion-Exclusion Principle
- Computer Representation of sets
- Injective, Surjective & Bijective functions, Inverse and Composite functions
- Ceiling functions and Floor Functions
- Fuzzy sets & membership functions 
1. How can you relate domain and co-domain of functions with function in programming language? Prove that:
by using set builder notation. How sets are represented by using set builder notation.
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 number which are multiple of 3 not exceeding 6? Describe injective, surjective & bijective function with examples.
 3. Define ceiling & floor function. Why do we need inclusion-exclusion principle. Make it clear with examples.

Chapter 2: Integers and Matrix [5/10 marks]

Topics to get covered: 
- Division Algorithm
- Primes & Greatest common divisor (Pairwise)
- Extended Euclidean Algorithm
- Integers & Algorithm
- Chinese Remainder Theorem
- Zero-One 
1. State Chinese Remainder Theorem. Find the value of x such that x = 2 (mod 3), x = 3 (mod 5) using Chinese Remainder Theorem.
 2. State Euclidean & Extended Euclidian theorem and trace it with suitable example.
 3. What do you mean by relative prime. Explain with examples. Express gcd (252, 198) = 18 as a linear combination of 252 and 198.
4. Define zero-one matrix. Explain the types of function. 

Chapter 3: Logic and Proof Method [5/10 marks]

Topics to get covered: 
- Nested Quantifier
- Representing English sentences in predicate logic
- Rules of inference & proof using rules of inference
- Proof Method 
1. Prove that if n is positive integer, then n is odd if and only if 5n + 6 is odd. 
2. Suppose that the domain of the propositional function P(x) consists of the integer 0, 1, 2, 3 and 4. Write out each of the following propositions using disjunctions, conjunctions and negations.
i) ∃x P(x)
ii) ∀x P(x)
iii) ∃x ¬P(x)
iv) ∀x ¬P(x)
v) ¬∃x P(x)
vi) ¬∀x P(x)
3. Show that the hypothesis "If you send me e-mail message, then I will finish writing the program", "If you do not send me an e-mail message, then I will go to sleep early", and "If I go to sleep early, then I will wake up feeling refreshed" lead to the conclusion "If I do not finish writing the program, then I will wake up feeling refreshed."
4. Use rule of inference to show that the hypothesis "Dipen works hard", "If Dipen works hard, then he will not get the job", imply the conclusion "Dipen will not get the job".
5. Show that the hypothesis "It is not sunny this afternoon and it is colder than yesterday", "We will go swimming only if it sunny", "If we do not go swimming, then we will take a canoe trip", and "If we take a canoe trip then we will be home by sunset" lead to the conclusion "We will be home by sunset".

Chapter 4: Induction and Recursion [5/10 marks]

Topics to get covered: 
- Proof by using mathematical induction
- Well ordering (Proof by using well ordering)
- Recursive Algorithm
1. Use mathematical induction to show that 5n-1 is divisible by 4 for all n≥1.
2. State the principle of mathematical induction. Prove by mathematical induction that, 1+2+22+32+.........+2n=2n+1-1, whenever n is a non-negative integer.
 3. Write down recursive algorithm for binary search & trace it for 3, 9, 10, 27, 38, 43.
4.Write down recursive algorithm for computing: i) an ii) factorial iii) Fibonacci number.

Chapter 5: Counting and Discrete Probability [10/15 marks]

Topics to get covered: 
- Recurrence Relation
- Pigeonhole Principle & Generalized Pigeonhole Principle
- Permutations & Combinations
- Probability
- Advance counting: Theorem 1-6
1. 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?
2. State Pigeonhole principle. Find the number of students in a class to be sure that three of them are born in the same month.
3. Solve the recurrence relation an = 3an-1 -3an-2 +an-3 with initial conditions a0=1, a1=8, a2=7.
4. List any two applications of conditional probability. You have a 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?
5. How many 3 digit number can be formed from the digits 1,2,3,4 & 5 assuming that: i)repetition of digits are allowed ii)repetition of digits are not allowed.

Chapter 6: Relation and Graphs [15/20 marks]

Topics to get covered: 
- N-ary relation
- Reflexive, Symmetric, Asymmetric, Antisymmetric, Transitive, Combining Relations
- Complementary relation, Inverse relation, Identity relation, Composition of Relation, Directed graphs, Matrix of relation
- Reflexive closure, symmetric closure, Transitive closure, Equivalence relation
- Hesse Diagram, Lattice
- Total ordering, Well ordering
- Shortest Path Algorithm (Dijkstra's Algorithm)
- Minimum Spanning Trees (Kruskal's Algorithm)
- SD-cut, maximal flow & minimal flow
- Spanning Trees, Hamilton path & circuit
- Euler path & circuit
1. 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? Give the name to other vertices yourself.
Apply the stated algorithm for finding the solution.
2. Let X = { 1, 2, 3, 4, 5, 6} then / is a partial order relation on X. Draw the Hesse Diagram (X, /).
 3. Define spanning tress & minimum spanning tree. What is graph isomerism? Determine whether the graphs shown in the following figure are isomeric or not.
4. Explain the process of identifying whether the graph is reflexive, symmetric or anti-symmetric by using matrix or diagraph with suitable example.
5. Define Euler path & Hamilton path with example. Explain Euler circuit with suitable example.
6. What is S-D cuts? For the following network flow, find the maximal flow from S to D.