🏫 National Institute of Technology Silchar

Click to view the Question Paper

Answer any 8 questions
Q No.	Question	Marks	CO
1	(a) Difference between `(i) Vacuous and Trivial proof` `(ii) Equivalence Relations and Partial Orderings set` `(iii) Symmetric and anti-symmetric relation` (b) Find the `greatest lower bound` and the `least upper bound` of the sets {3, 9, 12} and {1, 2, 4, 5, 10}, if they exist, in the poset (Z+, \|).	2 2 2 4	CO-5 CO-2 CO-2 CO-2
2	a) Use `rules of inference` to show that the hypotheses "If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on," "If the sailing race is held, then the trophy will be awarded," and "The trophy was not awarded" imply the conclusion "It rained." b) Use a `proof by contradiction` to show that there is no rational number r for which `r³ + r + 1 = 0.`	5 5	CO-1 CO-5
3	a) Find a recurrence relation for the number of bit strings of length n that do not contain three consecutive 0s. What are the initial conditions? How many bit strings of length seven do not contain three consecutive 0s?	10	CO3
4	a) Show that if n is an integer greater than 1, then n can be written as the `product of prime or primes.` b) Use `mathematical induction` to prove the formula for the sum of a finite number of terms of a geometric progression with the initial term a and common ratio r	5 5	CO5 CO5
5	a) Give a formula for the coefficient of `x^k` in the expansion of `(x + 1/x)¹⁰⁰`, where k is an integer. b) How many paths are there from A(0,0) to B(7,7) in the grid that allows only the top move and right move, with a constrain that the path from A to B should pass through (3,3)?	5 5	CO3 CO3
6	a) How many solutions does `x₁ + x₂ + x₃ = 12` have, where x₁, x₂, and x₃ are nonnegative integers with `x₁ ≤ 3, x₂ ≤ 4, and x₃ ≤ 5?` b) How many different strings can be made from the letters in ACCESS, using four or more of the letters?	5 5	CO3 CO3
7	If p = 13 and q = 19 in `RSA cryptosystem` with public key of the receiver as 133 and the cipher text (112, 83). `Decipher the ciphertext` and convert it into English characters if (A-65, B-66, C-67, . . . , Z-90)?	10
8	(a) Find the smallest positive integer when divided by 3, 11 and 17 gives the remainder 1, 3 and 6 respectively? (b) Solve x. (i) `x = 20⁶² mod 77` (ii) `x = φ(64)`	5 3 2
9	(a) Express each of these statements using `quantifiers`. Then form the negation of the statement, so that no negation is to the left of a quantifier. Next, express the negation in simple English. (i) There is no dog that can talk (ii) No rabbit knows calculus (b) `Prove` that if x is a real number, then `⌊2x⌋ = ⌊x⌋ + ⌊x + ½⌋`	5 5

Q No.	Question	Marks	CO
1	Difference between a) Vacuous and Trivial proof b) Fields and Rings c) Monoid and Semi-group d) Symmetric and anti-symmetric relation e) Equivalence Relations and Partial Orderings set	2 2 2 2 2	CO5 CO2 CO2 CO2 CO2
2	a) Determine whether `{1,3,6,9,12})` is a lattice. b) Give a poset that has a maximal element but no minimal element. c) Define a well-ordered set? d) Suppose that two people play a game taking turns removing one, two, three, or four stones at a time from a pile that begins with 17 stones. The person who removes the last stone wins the game. Show that the first player can win the game no matter what the second player does.	2 2 2 4	CO2 CO2 CO2 CO5
3	a) Find a `recurrence relation`J for the number of bit strings of length n that do not contain three consecutive 0s. b) What are the initial conditions? c) How many bit strings of length seven do not contain three consecutive 0s?	4 2 4	CO3 CO3 CO3
4	a) Prove that there are infinitely many primes b) Prove that if n is a non negative integers. Then `∑ⁿₖ₌₀ (ⁿₖ) = 0` c) How many strings of length five lowercase letters of the English alphabet contain at least two consonants? Repetition allowed. Determine True/False d) Surjective functions are invertible? e) Composition of a function are Commutative?	3 2 3 1 1	CO5 CO5 CO3 CO2 CO2
5	a) How many ways are there to assign five different jobs to four different employees if every employee is assigned at least one job? b) How many paths are there from `A(0,0)` to `C(7,7)` in the grid that allows only the top move and right move, with a constrain that the right move is not allowed when the y-coordinate is 2?	4 6	CO3 CO3
OR
6	a) How many solutions does `x₁ + x₂ + x₃ = 11` have, where `x₁, x₂,` and `x₃` are nonnegative integers with `x₁ ≤ 3, x₂ ≤ 4,` and `x₃ ≤ 6` b) How many different strings can be made from the letters COFFEE, using some or all of the letters?	4 6	CO3 CO3

Q No.	Question	Marks	CO
1	(a) How many ways are there to put five different employees into three indistinguishable offices when each office can contain any number of employees? (b) Proof that if `n` is a non-negative, then `C(2n,n) = ∑ᵏₖ₌₀ C(n,k)²` (c) Difference between Ring and Field along with an example for each?	5 2 3	CO3 CO3 CO2
2	(a) What relevant conclusion or conclusions can be drawn from "If I take the day off, it either rains or snows." "I took Tuesday off or I took Thursday off." "It was sunny on Tuesday." "It did not snow on Thursday." ? Explain the rules of inference used to obtain each conclusion from the premises. (b) Prove that if `n` is a perfect square, then `n + 2` is not a perfect square. (c) Show that at least four of any 22 days must fall on the same day of the week.	3 3 4	CO1 CO5 CO5
3	(a) Given the poset `({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72}, \|)`. i) Find the minimal elements. ii) Is there a greatest element? iii) Find the least upper bound of `{2, 9}`, if it exists? (b) For each of these relations on the set `{1, 2, 3, 4}`, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive. i) `{(2, 4), (4, 2)}` ii) `{(3, 4)}` iii) `{(1, 1), (2, 2), (3, 3), (4, 4)}` (c) Define Equivalence Relations, Partial Orderings, and Linearly ordered set? (d) What is a conjecture?	1 1 1 1 1 1 3 1	CO2 CO2 CO2 CO5
4	(a) How many diagonal avoiding paths are there from `A(0,0)` to `C(5,5)` in the grid if only top move and right move are allowed? (b) How many paths are there from `A(0,0)` to `C(7,7)` in the grid that allows only top move and right move, with a constrain that right move is not allowed when y-coordinate is `1?` (c) Show that if `n` is an integer greater than 1, then `n` can be written as the product of primes. (d) Difference between vacuous proof and trivial proof?	2 4 2 2	CO3 CO3 CO5 CO5
5	(a) A computer system considers a string of decimal digits a valid codeword if it contains an even number of 0 digits. For instance, `1230407896` is valid, whereas `120987045608` is not valid. Let `aₙ` be the number of valid n-digit codewords. Find a recurrence relation for `aₙ`. (b) How many ways are there to assign four different courses to three different students if every student is assigned at least one subject?	6 4	CO3 CO3
OR
6	(a) How many solutions are there to the equation `x₁ + x₂ + x₃ + x₄ + x₅ = 21`, where `xᵢ, i = 1, 2, 3, 4, 5` is a nonnegative integer such that `0 ≤ x₁ ≤ 3, 0 ≤ x₂ <= 4` and `x₃ ≥ 15?` (b) Given a set `{b₁, b₂, b₃, b₄}`, how many derangement are possible?	6 4	CO3 CO3