CS201 Midterm Exam Fall 2023 PDF

‫بسم هللا الرحمن الرحيم‬ University of Prince Mugrin Collage of Computer and Cyber Sciences Computer Science Department CS 201 – Introduction to Discrete Structures...

‫بسم هللا الرحمن الرحيم‬ University of Prince Mugrin Collage of Computer and Cyber Sciences Computer Science Department CS 201 – Introduction to Discrete Structures Fall Semester 2023-2024 14 December 2023, 1:00 PM – 2:30 PM th Midterm Exam Time Allowed: 90 Minutes Student Name: __________________________ Student Number: ___________________ Please read the following instructions carefully before attempting any of the questions: 1. The use of mobile devices (phones or otherwise) is NOT PERMITTED 2. You are NOT allowed to use calculators 3. If you think that there is something wrong with any of the questions, attempt it to the best of your understanding 4. This is a CLOSED BOOK and CLOSED NOTES exam For instructor use only Gained/ CLO Questions Allocated Marks 1.1 Demonstrate knowledge of writing arguments 1, 2, 3, 4, 5 /5 using logical notation and determining its validity 1.2 Express basic properties of mathematical 6, 7, 8, 9, 10 /5 structures 2.1 Utilize notations of mathematical proofs for 16, 17, 18, 19, 20 /10 particular case scenario 2.2 Analyze discrete structures 11, 12 13, 14, 15 /5 2.3 Apply the basics of counting techniques and 21, 22, 23 /5 number theory in problem solving Total: /30 CS201 – Introduction to Discrete Structures Midterm Exam Fall 2023 Section 1: MCQs [15 marks] Answer each of the following questions by choosing the single best answer (1 mark each): 1. x (x-1 < x) is logically equivalent to a. x (x-1 < x) b. x (x-1 < x) c. x (x-1  x) d. x (x-1 > x) 2. Which one is an equivalent expression of the following statement: Sometimes the difference between two integers is not positive a. x y (x-y < 0) b. x y (x-y  0) c. x y (x-y > 0) d. x y (x-y > 0) 3. What is the truth value of xyz (x + y = -z), where domain of x, y and z is all integers? a. True b. False c. No truth value, because it is not a proposition d. Sometimes true, sometimes false 4. Which one is correct? a. -x = -x b. -x = -x c. Both (a) and (b) d. None of (a) or (b) 5. Which one is not a proposition when the domain of x is all integers? a. Is x + 1 > x true or false? b. x + 1 = x c. x + 1  x d. x + 1 > x 6. p  T  p is a. F b. T c. p d. p 7. Which one is a contradiction? a. (p  p) → F b. (p  p) → T c. (p  F) → p d. (p  T) → p Page 2 of 7 CS201 – Introduction to Discrete Structures Midterm Exam Fall 2023 8. ((p→q)  q) → p) is called a. Modus ponens b. Modus tollens c. Simplification d. Conjunction 9. What is wrong in the following deduction of (3) from (1) and (2) (1) If I do exercise, then I feel easy (2) I am feeling easy today (3) I did exercise today a. Nothing wrong, the deduction is correct by Modus Ponens b. There may be other reason for feeling easy, such as eating less c. The deduction (3) should be “I did not do exercise today” d. The deduction (3) should be “I am not feeling easy today” 10. What is the meaning of the area (shown by the arrow) in the following Venn diagram? a. A-B-C b. C-A-B c. B-(AC) d. (AC)-B 11. Which one is not correct? a. If a  b (mod m) holds, then ac  bc (mod m), where c is any integer b. If a  b (mod m) holds, then a+c  b+c (mod m), where c is any integer c. If a  b (mod m) holds, then a/c  b/c (mod m), where c is any integer that is not zero d. None of the above 12. Which of the followings is a correct value of x in the expression: 27  x (mod 6) a. 3 b. 9 c. 15 d. All of the above are correct 13. Which one is a prime number? a. 42 b. 43 c. 44 d. 45 14. If my public key for RSA algorithm is (15, 3), then which one is correct as my private key d? a. d = 1 b. d = 2 c. d = 3 d. d = 4 15. Which one is the encryption function in RSA algorithm? a. C = Me mod n b. M = Cd mod n c. ed  1 (mod (p-1)(q-1)) d. n = pq Page 3 of 7 CS201 – Introduction to Discrete Structures Midterm Exam Fall 2023 Section 2: Short answers. 16. [2 marks] Is the following logic circuit satisfiable? Write yes or no. If yes, then show for which truth value of p, q and r it is satisfiable. If no, then explain why it is not satisfiable. (p  q)  (q  r)  (r  p) Answer: 17. [2 marks] Show by a counterexample (that means, find a value of x) that the proposition x(x + x = 2x ) is False, where the domain of x is all real numbers. Show your calculation. Answer: Page 4 of 7 CS201 – Introduction to Discrete Structures Midterm Exam Fall 2023 18. [2 marks] Show that the following three hypotheses (1) I want to sleep or I want to go Makkah (2) If I sleep, then I do not go to the university (3) I am in the university give the conclusion (4) I go to Makkah inshaAllah Answer: 19. [2 marks] The following paragraph is based on RSA algorithm. Fill out the empty spaces. RSA algorithm uses two keys, which are public key and private key. For some person A, his public key is known to …………………………………., but the private key is known to …………………………………… only. If another person B wants to send a message to A, then B encrypts the message by A’s ……………………………………. key and sends to A. Then A, upon receiving the encrypted message, decrypts it by his ………………………………………. key. RSA algorithm can also be used for sending a digital signature of A to a recipient B, so that B knows that A has actually sent the message. To do that, A applies …………………………………… function with his ……………………………………. key to his signature and sends to B. Upon receiving the result, B applies …………………………………… function with A’s ……………………………………. Key to retrieve the signature of A. Page 5 of 7 CS201 – Introduction to Discrete Structures Midterm Exam Fall 2023 20. [2 marks] Prove by contraposition that "if n2 + 1 is an odd integer, then n is an even integer." Answer: 21. [2 marks] Let {an} be a sequence that satisfies the recurrence relation: an = an-1 - an-2 for n = 2, 3, 4, …., and suppose that a0 = 3 and a1 = 5. Find the value of a2, a3 and a4. Show your calculation? Answer: Page 6 of 7 CS201 – Introduction to Discrete Structures Midterm Exam Fall 2023 22. [2 marks] Find the multiplication of the following two matrices. 1 1 2 1 [ ]  = 2 1 2 1 23. [1 mark] Suppose that F(x, y) means x is the father of y. Write the following statement by using predicate and quantifiers, where the domain of x and y are all persons in this universe. Father-child relation is not symmetric. Answer: ‫هللا يحفظك‬ Page 7 of 7