CMPS 211 Final, Spring 2010

AUB-CMPS 211: Discrete Structures June 3rd, 2009 Final Exam Instructor: Fatima Abu Salem Name: Duration: 90 minutes This exam is closed notes. Question 1 (On Logic and Rules of inference) (10%) Convert each of the following into a symbolic proof, and justify each step of the proof leading up to the conclusion. (a) (5%) For me to wear my summer clothes it is necessary that it be sunny. When it is sunny I always wear my sunscreen. Today I did not wear my sunscreen. Therefore, it must not be sunny, and so I am not wearing my summer clothes. (b) (5%) For me to wear my summer clothes, it is sufficient that it be sunny. For me to wear my sunscreen, it is necessary that it be sunny. I am wearing my sunscreen. Therefore, it must be sunny, and so I must have been wearing my summer clothes. Question 2 (On Iterative Algorithms) (18%) In this question we examine a sorting algorithm known as Selection sort. Selection sort works iteratively as follows. A list of n integers is initially given in an array A[0, . . . , n − 1]. In the first iteration, the minimum element in the list A[0, . . . , n−1] is found then swapped with the element positioned in A[0]. In the second iteration, the second minimal element in the list A[1, . . . , n − 1] is found then swapped with the element in A[1]. Generally, in the i’th iteration, the i’th minimal element in the list A[i − 1, . . . , n − 1] is found then swapped with the element in A[i − 1]. (a) (5%) Develop the pseudo-code for Selection Sort. (b) (5%) Prove that Selection Sort is correct. (c) (4%) Determine the asymptotic run-time of Selection Sort. (d) (4%) Is Selection Sort asymptotically faster or slower than Merge Sort? Justify your answer. F-1 Question 3 (On Recursive Algorithms) (19%) Given a list of n positive integers in an array A[0, . . . , n − 1], our goal is to find the greatest common divisor of all integers in this list. Assume that n is a power of two. (a) (5%) Suggest and develop the pseudo-code for a divide and conquer algorithm to achieve this goal. (a) (5%) Prove that your algorithm is correct. (a) (5%) Write down the recurrence associated with the run-time of this algorithm. (a) (4%) Use the Master Theorem to determine the run-time of this algorithm. Question 4 (On Recurrences) (14%) A string that contains only the characters 0, 1, and 2 is called a ternary string. (a) (5%) Find a recurrence relation for the number of ternary strings that do not contain two consecutive 2’s. (b) (4%) What are the initial conditions for this recurrence? (c) (5%) How many ternary strings of lenth five do not contain two consecutive 2’s? Question 5 (On Counting) (29%) In how many ways can an organiser of a tournament arrange six players in a row, including the first prize winner and the second prize winner, if (a) (5%) the first prize winner must be next to the second prize winner? (b) (5%) the first prize winner is not next to the second prize winner? (c) (5%) the first prize winner is standing somewhere to the right of the second prize winner? A computer programming class consists of 14 math students and 12 computer science students. The course instructor chooses students randomly to serve on a programming contest. (d) (5%) How many students must the course instructor select to be sure that at least two students of the same major are participating in the contest? (e) (4%) How many students must the course instructor select to be sure that at least two computer science students are participating in the contest? (f) (5%) Suppose there should be six students to participate in this contest. How many ways are there to form a group of contestants if the group must have the same number of math and computer science students? F-2 Question 6 (On Equivalence relations and classes) (10%) Let R denote the relation on the set of all bit strings such that two bit strings s and t are related by R if and only if the difference in absolute value of the number of zeros in s and t respectively is even or is equal to 0. (a) (5%) Show that R is an equivalence relation. (b) (5%) What is the equivalence class under R of the bit string s = 0? F-3 Answer Sheet 1 F-4 Answer Sheet 2 F-5 Answer Sheet 3 F-6 Answer Sheet 4 F-7 Answer Sheet 5 F-8 Answer Sheet 6 F-9 Answer Sheet 7 F-10 Answer Sheet 8 F-11 Answer Sheet 9 F-12 Answer Sheet 10 F-13